1
大学数学基礎解説
文献あり

自然数の大小関係と有限集合の濃度の大小関係の対応について

138
1
$$$$

初めに

鳩の巣原理を知っていますか?

鳩の巣原理

$m,n$を自然数とする。$n$個の箱に$m$個の物を入れるとき、$m>n$ならば二つ以上物が入ってる箱が存在する。

集合論的に述べると以下の定理2ような言い回しになるのではないかと思っています。(実際そうであるかは知らないです。あと定理1と表記されていますが原理1です。)

二つの有限集合$A,B$に対し、$|A|>|B|$ならば$A$から$B$への単射は存在しない。

証明はベルンシュタインの定理を使うだけなので省略します。

今回の記事の本題は、原理1と定理2の対応の妥当性についてのお話です。

本題

集合$A$は、ある自然数$n$が存在して、かつ全単射
$$\{1,2,\cdots,n\}\to A$$
が存在するとき、有限であるといい、このような集合を有限集合という。

有限集合$A$に対して、定義1に対応する自然数$n$はただ一つである。特に、$A,B$に対応する自然数を$m,n$と置くと、$|A|>|B|$$m>n$は同値である。

有限集合の濃度と対応する自然数の大小が一致するというのが上の定理の主張です。原理1と定理2の主張の対応の妥当性についてどこかひっかかるとことがあったのですが、今はこの対応の妥当性は定理3によるのではないかなと思っています。

準備

定理3証明に入る前に、今回使う定義を確認しておきます。

関係

集合$X,Y$および直積集合$X\times Y$の部分集合$G$の組
$$R:=< X,Y,G>$$
$X,Y$における(二項)関係という。
また、$(a,b)\in X\times Y$に対し、$(a,b)\in G$であることを$aRb,R(a,b)$などと書き、$a,b$には関係$R$が成立するなどという。

写像

関係$f:=< X,Y,G>$において、任意の$x\in X$に対しある$y\in Y$がただ一つ存在して$xfy$が成立するとき、$f$$X$から$Y$への写像といい、$f:X\to Y$など書く。また、$(x,y)\in G$であることを$f(x)=y$などと書き、$(x,y)\notin f$であることを$f(x)\neq y$などと書く。また、部分集合$G$を写像$f$のグラフという。

以降、証明に入ります。

証明

まず、証明に使う補題を確認しておきます。

集合$X,Y$に対し、単射$f:X\to Y$が存在すれば、任意の$x\in X,\,y\in Y$に対し、単射$g:X\to Y$$g(x)=y$であるものが存在する。

  1. $f(x)=y$のとき、$g=f$とすればよい。
  2. $f(x)\neq y$かつ$b\in \mathrm{Im} f$のとき、単射性より$f(x^{\prime})=y$となる$x^{\prime}\in X$がただ一つ存在して、$x^{\prime}\neq x$となる。$f(x)=y^{\prime}$として、
    $$G:=\{(a,b)|a\in X-\{x,x^{\prime}\},b=f(a)\}\cup \{(x,y),(x^{\prime},y^{\prime})\} $$
    とすれば$g:=< X,Y,G>$は条件を満たす。
    3.$f(x)\neq y$かつ$b\notin \mathrm{Im} f$のとき、
    $$G:=\{(a,b)|a\in X-\{x\},b=f(a)\}\cup \{(x,y)\} $$
    とすれば$g:=< X,Y,G>$は条件を満たす。

次に、下の命題5を$n$についての数学的帰納法で証明します。

$m,n$を自然数とする。また、$m>n$とする。このとき、単射
$$f:\{1,2,\cdots,m\}\to \{1,2,\cdots,n\}$$
は存在しない。

  • $n=1$のとき、単射$f:\{1,2,\cdots,m\} \to \{1\}$がが存在すると仮定して矛盾を導く。関係$g$
    $$g:=<\{1\},\{1,2,\cdots,m\},\{(1,1)\} >$$
    で定義すると、$g$$\{1\}$から$\{1,2,\cdots,m\}$への単射である。よって、ベルンシュタインの定理より、全単射
    $$h:\{1\}\to\{1,2,\cdots,m\}$$
    が存在する。$h$の全射性より$h(1)=1$かつ$h(1)=2$が成立するが、$h$は写像なのでこれは矛盾する。よって単射$f$は存在しない。
  • $n=k$のときに成立すると仮定すると、$n=k+1$のときに単射$f:\{1,2,\cdots,m\}\to\{1,2,\cdots,k+1\}$が存在しないことを、単射$f:\{1,2,\cdots,m\}\to\{1,2,\cdots,k+1\}$が存在すると仮定して矛盾を導くことで証明する。補題4より、単射$g:\{1,2,\cdots,m\}\to\{1,2,\cdots,k+1\}$$g(m)=k+1$となるものが存在する。よって、
    $$h:=<\{1,2,\cdots,m-1\},\{1,2,\cdots,k\},\{(a,b)|a\in \{1,2,\cdots,m-1\},b=g(a)\}>$$
    として単射
    $$h:\{1,2,\cdots,m-1\}\to\{1,2,\cdots,k\}$$
    が構成できる。しかしこれは$n=k$の仮定に矛盾する。したがって、$n=k+1$のときも成立する。

数学的帰納法により命題5は成立することがわかる。

最後に定理3を証明します。

定理3の証明
  • 前半について
    仮に、対応する数字が2つあるとする。$m,n$と置くと、自然数は大小関係において全順序なので$m>n$または$n>m$のどちらか一方が成立する。$m>n$としても一般性を失わないので以降$m>n$とする。定義1より全単射$f:\{1,2,\cdots,m\}\to A$および全単射$g:\{1,2,\cdots,n\}\to A$が存在する。このとき
    $$g^{-1}\circ f:\{1,2,\cdots,m\}\to \{1,2,\cdots,n\}$$
    は全単射となるがこれは命題5に矛盾する。対応する数字が3つ以上あるときも同様に矛盾することが示せる。
  • 後半について
    $|A|>|B|$のとき、単射$h:B\to A$が存在し、全単射$f:\{1,2,\cdots,m\}\to A$および全単射$g:\{1,2,\cdots,n\}\to B$が存在する。
    $$f^{-1}\circ h \circ g:\{1,2,\cdots,n\}\to \{1,2,\cdots,m\} $$
    は単射なので命題5より$m\geq n$である。$m=n$とすると、
    $g\circ f^{-1}:A\to B$は全単射となるが、これは$|A|>|B|$に矛盾する。よって$m>n$となる。
    逆に、$m>n$のとき、$|A|\leq|B|$と仮定すると、単射$h:B\to A$が存在し、上の$f,g$に対して
    $$f^{-1}\circ h \circ g:\{1,2,\cdots,m\} \to \{1,2,\cdots,n\}$$
    は単射となるから、定理5より$m\leq n$となり矛盾する。よって$|A|>|B|$

参考文献

[1]
森田 茂之, 集合と位相空間
投稿日:2021818

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

-
-
7
789

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中