カントールの定理 Cantor’s Theorem


|| 冪集合を思い出して

この定理は↓のことを主張しています。

\mathrm{card}\,(S)<\mathrm{card}\,(2^S)

スポンサーリンク



要は、「冪集合」の濃度は、

「元の集合」の濃度よりでかいってことです。

言いたいことの全てはこれだけになります。




これも一見当然に見えるんですが、

これの面白いところは、

「無限集合」でもこれが成立する、というところです。




そう、「無限」にも階層があるってことを、これは表してます。

不思議なもんですよねぇ、いやほんと。




さっそく「証明」してみましょうか。

対角線論法」(背理法の一種)というやり方を使います。







証明までの大雑把な流れ


必要条件「定理の発想のもとになったもの」



方針「冪集合と単射の確認」

   細かな方針「記号の確認」


前提「単なる事実の確認」



対角線論法「後者を使って外側を導く」

   外側の意味「決定された枠の中から、その他を得る」

   都合の良い集合「明らかに外側にある集合」



カントールの定理の証明







必要条件・発想の源


さて、普通に考えて「冪集合」操作を行えば「要素」は増えます。

これは「有限」なら確実に確かめられることです。



なにせ最小の集合となる『空集合』ですら、

その『冪集合』を作れば『 \{∅\}⊂\{∅,\{∅\}\}=2^∅ 』となります。




だとすると、なんとなくこう思えてきます。

「無限」でもそうなるんじゃ?と。




では、確かめていきましょうか。







方針


まずなにか「無限集合」を含む「集合 S_{A} 」を用意しましょう。

そしてこれの『冪集合』を「 2^{S_{A}} 」とします。





『冪集合』の定義から、明らかに『 |S_{A}|≤|2^{S_{A}}| 』が成立します。

なぜなら「一元集合 \{e_i\}⊆S_A 」に着目しても↓は成立します。



∀e_i\,\,\,\{e_i\}∈2^{S_A}




この事実から、簡単に単射を導けるわけです。

f:e_i↦\{e_i\}




つまり確実に「単射が存在する」ので、

『濃度』は必ず「 |S_{A}|≤|2^{S_{A}}| 」です。




ここまでは、定義から分かります。

しかし『全単射の存在』までは、まだ言及できていません。

ここを調べてみたいと思います。




といってもまあ、ないんじゃないか? という感じですね。

となると『存在する』と「仮定」すれば「背理法」が使えそうな感じ。




とまあこんな感じで、ざっと方針は決まりました。

後はやることやるだけです。






細かな方針


定義から『 |S_A|≤|2^{S_A}| 』は確定です。

つまり「 S_A から 2^{S_A} 」への「単射」はあります。




しかし「 S_A から 2^{S_A} 」への「全射」があるかどうかは分かりません。

同時に「全単射」があるかも不明です。




しかしはて、そもそも「全射」はあるんでしょうか。

直観的には、ちょっとありそうにないですよね。

なら「全射」が無い、としても良いかもしれません。



なぜなら「全単射」の定義は『単射かつ全射な写像』です。

「全射」が無いということは、同時に「全単射」もありません。




確認してみましょう。

S_A から 2^{S_A} 」への「全射」があるなら、

S_A 』から『 2^{S_A} 』の要素の全てが得られます。




つまり「全ての要素が得られない」なら、『全射』は存在しません。




という感じで、細かな方針は決まりました。

そのような「得られない要素が存在する」ことを示せば、ゴールです。







前提


ある「集合 S_A 」があって、

その「冪集合 2^{S_A} 」があります。




そして「冪集合 2^{S_A} 」は、定義から、

「集合 S_A 」の部分集合を全て持っています。




そこで「集合 S_A 」の「部分集合」を『 S_{A_{pt}} 』とします。




方針を見るに、これがキーになりそうです。







対角線論法 Diagonal Method


この証明方法の最大の特徴は『冪集合 2^{S_A} 』を考えると、

ある部分集合を「作ることができてしまう」ことにあります。(?)





↑の前提をそのまま使いましょう。

その「部分集合」とは『 S^{Out}_{A_{pt}}=\{e∈S_A\,|\,e∉f(e)\} 』です。

これは『元となった要素と関係のない部分集合』になります。




めっちゃフランクに言うなら、

『像』じゃないものしか持ってないよ、って言ってます。




でも『像』じゃないけどあるよ、って感じのがこれです。

まあ、実際すごくありそうなんですけど、確かめないと分からんです。






一見すると、正直よく分からんと思います。(少なくとも自分は)

そのよく分からなさの原因は、

「なんでこれが良いのかがそもそも分からん」だと思います。




証明のためにいきなり出てきて、

これが「都合が良い」っていきなり言われても、

いや、なんで? ってなりますよね。




なので、実際に作ってみましょう。

方針は単純です。↓みたいな感じ。

写らない漏れ(要素)を作ったろう!(後出しで)






対角線上から得られる外側(だいたい右下)


やり方は「実数と自然数の濃度」でやったのと同じです。

これでなんとなく分かっちゃう人もいるでしょう。

ええ、まあそんな感じです。






前提


S_A 」から「 2^{S_A} 」への『写像』があります。

全単射を考えたいんで、とにかくなんか写像があるんです。



また『 S_A 』の『部分集合 S_{A_{pt}} 』は存在します。

それでいて『 S_{A_{pt}} 』は、確実に『冪集合 2^{S_A} 』の要素です。



そして、こいつらの関係は↓

S^{Out}_{A_{pt}}∈2^{S_A}, \,S_{A_{pt}}∈2^{S_A}




この辺は全部決まりやら定義なので当然ですね。






補題


仮定


f(e)=S^{Out}_{A_{pt}} 』となる『 e∈S_A が存在する』



要は「部分集合 S^{Out}_{A_{pt}} 」と「 S_A の要素」との紐づけです。

全単射が欲しいんで、こいつも像として欲しい感じ。



なのでこれは、『 S_A の要素』から、

S^{Out}_{A_{pt}} 」が『像』として得られるって言ってます。




ただし『像』は「写像」と「定義域」から得られることに注意。

また「 S^{Out}_{A_{pt}} 」は「終域の要素」でもあります。

(ここでの終域とは、冪集合のこと)




これは、ただの部分集合なら違和感はありませんが、

↑の「部分集合」を考えるとなんか変ですね。






仮定から得られる事実


これはまあ、当然のように矛盾が出ちゃいます。

というのも、無いんです。どこにも( e が)






\mathrm{Case\,1}


まず、もし『 e∈S^{Out}_{A_{pt}} 』の時、

仮定から、当然ながら『 S^{Out}_{A_{pt}}=f(e) 』です。




しかし「 S^{Out}_{A_{pt}} 」の定義は『 e∉f(e) 』ですから、

e∈S^{Out}_{A_{pt}}=f(e)』とは矛盾します。




じゃあ、これはおかしいです。

例えば「 S^{Out}_{A_{pt}} が要素 1 を持つ」とき、「 S^{Out}_{A_{pt}}=f(1) 」なら、

この「 S^{Out}_{A_{pt}} 」の定義から、「要素 1 」を持ってるはずありません。






\mathrm{Case\,2}


では反対に、もし『 e∉S^{Out}_{A_{pt}} 』の時は、

変わらず、仮定より『 S^{Out}_{A_{pt}}=f(e) 』です。



しかし『 S^{Out}_{A_{pt}} 』の定義『 e∉f(e) 』から、

e 』は『 S^{Out}_{A_{pt}} の要素』のはずです。

あれ?




というわけでこれも矛盾します。

例えば「 S^{Out}_{A_{pt}} が要素 1 を持たない」とき、「 S^{Out}_{A_{pt}}=f(1) 」なら、

S^{Out}_{A_{pt}} 」の定義から、「要素 1 」を持つはずなんです。






え、じゃあこれ満たす『 e∈S_A 』ってどこにあんの?

ってなりますが、まじでどこにもないです。

あるって言ってたのに。(仮定で)






はい、というわけで『仮定』から『矛盾』が得られました。

S^{Out}_{A_{pt}} 』は『定義域 S_A 』からの『像 f(e) 』じゃないんです。

ただし『冪集合 2^{S_A} 』の「要素」ではあります。




ということは『 S^{Out}_{A_{pt}} 』は、

『要素 e∈S_A 』から、『像 f(e) 』としては得られません。



つまりそんな『 S^{Out}_{A_{pt}} を得る写像』は無いってことです。

ということは、「冪集合への全射」は存在しません。






S^{Out}_{A_{pt}} を作ってみる


↑の証明、どうですか? 分かりますか?

自分としては、なんかよく分かりません。

特に、この都合の良い「 S^{Out}_{A_{pt}} 」が、ほんと分かりません。



なので、とりあえずこれを作ってみましょう。

その準備のために、表を作ります。




↓の表が、いわゆる「対角線」を得るための準備になります。

↑のだけじゃ、なんで対角線なの?って話でもありますしね。




というわけで、「軸」として、なにをやれば都合が良いかを考えます。

すると↓みたいな方針が良さそうな感じ。



ともかく『要素と関係の無い部分集合』が得たい。




そう、「写像で得られない」ものが、とにかく欲しいんです。

対角線論法で得たい主張は『全射が存在しない』なんですから。



なので、とりあえず「写像で得られるもの」を全て考えてみます。

いわゆる総当たりです。




そんな『要素と関係のある部分集合』を全部書き表すために、

横軸を「部分集合が持つ要素 e∈s_A⊆S_A 」として、

縦軸を「 S_A要素 e 」としましょう。






これを表にしてみます。

「結びついてる部分集合の要素」なら「 1 」とし、

「部分集合の要素じゃない」なら「 0 」とすると、



このときの「写像 f 」の情報は↓みたいになります。


e_1∈s_A e_2∈s_A e_3∈s_A e_4∈s_A
e_1 1 0 0 1
e_2 0 0 1 0
e_3 1 0 1 0
e_4 0 0 0 0

これの具体例は『 f(e_1)=\{e_1,e_4,...\} 』です。




そしてこの情報から『 S^{Out}_{A_{pt}} 』が得られるわけですね。

どうやって? って感じなので、さっそく作っていきましょうか。




ともかく「要素 e 」ごとに『写像』の対応は決まってます。

つまりその「要素 e 」からの『像』もまた決まってるわけです。



ここから『 e∉f(e) 』を満たす「部分集合」を得ます。

つまりは「表中の対応ではない写像」を作れば良いわけです。




そこで『対角線論法』と呼ばれるやり方が登場します。

全てから一個ずつとるために「左上から右下」へ、

「対角線」にある、『含む含まないの情報』を全て得ます。



そしてそれの「 0,1 」を入れ替えれば、はい出来上がり。



こうして出来上がった「写像 f^{Out} 」は、

どの「集合 S_A の要素」からも『像』を得ません。



なぜなら、この「写像 f^{Out} 」は、

表中のどの「要素 e からの写像」とも異なるからです。



なにせ一度全部調べて、それと違うってことにしたわけなので。

(欲しい結果から得てる)




そして、その「写像 f^{Out} 」の情報からは『部分集合』が得られます。

その部分集合こそが『 S^{Out}_{A_{pt}} 』なわけです。






そしてこれが最も重要ですが、

この部分集合は『冪集合 2^{S_A} 』に含まれます。



なぜなら「写像 f^{Out} 」から得られた情報にある、

『部分集合の要素』は、全て『 S_A の要素』だからです。




再度確認しますが『 f^{Out} の情報』から得られた「部分集合」は、

『表中から得られる全ての部分集合』と異なります。



つまり『 f^{Out} の情報』から得られた「部分集合」は、

『表中からは得られない部分集合』なわけです。






ここまで分かってからの↑の矛盾なわけですね。

そりゃあ矛盾も生じますよ。

そのために作られたんですから。






とまあ、対角線論法はこんな感じになります。

はい、「都合の良い部分集合 S^{Out}_{A_{pt}} 」は、

端から『像として得られないもの』だったわけですね。



これを「図形的」に見て、作る。

この感じが、対角線論法なわけです。




つまるところ『対角線論法』の本質とは、

『平面的に情報を得て、対角線から外側を導く』

ということになります。







本題(カントールの定理)


大事な部分は終わったので、後は消化試合です。

忘れているかもしれませんが、

本題となるカントールの定理の証明を行っていきます。




証明


仮定


S_A 」から「 2^{S_A} 」への『全射』があるとします。






矛盾の導出


『対角線論法』より、

「集合 S_A 」から「冪集合 2^{S_A} 」へは、

『像とならない部分集合 S^{Out}_{A_{pt}} 』が存在します。




これは「仮定」に反する事実です。

『像』じゃない「部分集合」を『冪集合』が持つのなら、

「全射」は存在しません。






結論


冪集合の定義から、

|S_A|≤|2^{S_A}| 』は明らかです。




しかし↑の事実から、

S_A 」から「 2^{S_A} 」への『全射』は存在しません。

つまり『 |S_A|≠|2^{S_A}| 』です。



以上から『 |S_A|<|2^{S_A}| 』が得られます



証明終わり






余談


個人的には↓の書き方の方が好きです。

分かりやすいんで。



card\,(S)<card\,(2^{S})






それと『対角線論法』についての諸注意をしておきます。

これはなんか嫌う人がいますが、

たぶんその人たちは順番を見落としています。




いわゆる手順の問題です。

「対角線論法」では、連続性と似たような操作を行います。

なので、すでにあるものから、新しいものを得られるわけですね。




ちょっとふわっとした説明で申し訳ないですが、



要は『対角線論法』で作った「含まないもの」を、

またひっくり返したりして『もとあった場所に含める』としても、

「対角線論法」の手続きの順番から、また新たなものが生成されます。




先述の通り、いわゆる連続性みたいなものです。後出しOK。

それでいて、これは一定の手続きによって作られます。

プログラミングをやってる方なら、生成手順も容易に想像できるかと。




簡単に概要を説明するなら、

要は単に「後者関数」で『なかったもの』を生成するだけです。




具体例を挙げると、例えば「 ω より下の自然数」の中で、

「一番大きな自然数」は存在しません。

なぜなら、仮に存在する場合、必ずそれより大きいものが作れるので。



そう、この「なかったもの」も、「生成されればある」わけで。

だから、なんか変に感じるのかもしれません。




ですので、なんか間違ってるみたいにいう人がいるかもしれませんが、

それに関しては真に受けないようにしてください。




これは「一定の手続き」です。

「あるもの全て」から「そこにないもの」を得てます。

決しておかしな手続きではありません。




もしそれでも変に感じるのであれば、是非読み返してみてください。

当たり前のことしか行ってはいませんので。




それにもし「対角線論法」の、

『後者』による手続きを否定するなら、

「無限公理」を認めないのかどうか、という話になります。



認めないというのなら、確かに変なんでしょう。

自分は変だとは感じませんが。




はい、というわけで、お疲れさまでした。

『カントールの定理』の証明は以上で終わりです。

参考になったのなら、幸いに思います。