具体例：可算無限集合の場合

ウィキペディア小見出し辞書

具体例：可算無限集合の場合

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/17 07:25 UTC 版)

「カントールの定理」の記事における「具体例：可算無限集合の場合」の解説

証明を理解するために、元の集合が可算無限集合 X である特別な場合に対して検証しよう。一般性を失うことなく X = N = {1, 2, 3,...} , 自然数の集合、ととれる。 N はその冪集合 P(N) と等濃と仮定する。P(N) がどのように見えるか例を見よう： P ( N ) = { ∅ , { 1 , 2 } , { 1 , 2 , 3 } , { 4 } , { 1 , 5 } , { 3 , 4 , 6 } , { 2 , 4 , 6 , … } , … } . P(N) は、すべての偶数の集合 {2, 4, 6,...} や空集合など、N の無限個の部分集合を含む。 さて P(N) の元がどのように見えるかのアイデアを持っているから、N の元を P(N) の各元に、これらの無限集合が等濃であることを示すために、対になるように試みよう。言い換えると、N の各元が無限集合 P(N) の元と対になるようにしてどちらの無限集合からの元も対にならないまま残ることはないように試みる。元を対にするそのような試みはこのように見えるだろう： N { 1 ⟷ { 4 , 5 } 2 ⟷ { 1 , 2 , 3 } 3 ⟷ { 4 , 5 , 6 } 4 ⟷ { 1 , 3 , 5 } ⋮ ⋮ ⋮ } P ( N ) . そのようなペアリングが与えられると、ある自然数はまさに同じ数を含む部分集合と対にされる。例えば、我々の例において数 2 は元として 2 を含む部分集合 {1, 2, 3} と対にされている。そのような数を利己的と呼ぶことにしよう。他の自然数はそれを含まない部分集合と対にされる。例えば、我々の例において数 1 は元として 1 を含まない部分集合 {4, 5} と対にされている。このような数を非利己的と呼ぶ。同様に、3 と 4 は非利己的である。 このアイデアを用いて、自然数のある特別な集合を作ろう。この集合は求める矛盾（英語版）を提供する。D をすべての非利己的な自然数の集合とする。定義によって冪集合 P(N) は自然数からなるすべての集合を含み、したがってこの集合 D を元として含む。写像が全単射であれば、D は対応するある自然数 d と対にされていなければならない。しかしながら、これは問題を起こす。d が D に入っていれば、d は利己的である。なぜならばそれは対応する集合に入っているからで、D の定義に矛盾する。d が D に入っていなければ、それは非利己的であり代わりに D の元でなければならない。したがって D に写るような元 d は存在しえない。 D と対にできる自然数は存在しないから、我々のもとの仮定、 N と P(N) の間に全単射が存在することに矛盾した。 集合 D は空かもしれないことに注意しよう。これはすべての自然数 x は x を含む自然数の集合に写ることを意味する。すると、すべての自然数は空でない集合に写り、どんな数も空集合に写らない。しかし空集合は P(N) の元であるので、写像はなお P(N) をカバーしない。 この矛盾による証明（英語版）を通して N と P(N) の濃度は等しくはありえないことを示した。 P(N) の濃度は N の濃度よりも小さくなれないことも知っている、なぜならば P(N) は定義によってすべてのシングルトンを含み、これらのシングルトンは P(N) の中で N の「コピー」をなすからである。したがって、唯一つの可能性が残り、それは、P(N) の濃度は N の濃度よりも真に大きいことであり、カントールの定理が証明された。