|| 冪集合を思い出して
この定理は↓のことを主張しています。
\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 が）
まず、もし『 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 」を持ってるはずありません。
では反対に、もし『 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。
それでいて、これは一定の手続きによって作られます。
プログラミングをやってる方なら、生成手順も容易に想像できるかと。
簡単に概要を説明するなら、
要は単に「後者関数」で『なかったもの』を生成するだけです。
具体例を挙げると、例えば「 ω より下の自然数」の中で、
「一番大きな自然数」は存在しません。
なぜなら、仮に存在する場合、必ずそれより大きいものが作れるので。
そう、この「なかったもの」も、「生成されればある」わけで。
だから、なんか変に感じるのかもしれません。
ですので、なんか間違ってるみたいにいう人がいるかもしれませんが、
それに関しては真に受けないようにしてください。
これは「一定の手続き」です。
「あるもの全て」から「そこにないもの」を得てます。
決しておかしな手続きではありません。
もしそれでも変に感じるのであれば、是非読み返してみてください。
当たり前のことしか行ってはいませんので。
それにもし「対角線論法」の、
『後者』による手続きを否定するなら、
「無限公理」を認めないのかどうか、という話になります。
認めないというのなら、確かに変なんでしょう。
自分は変だとは感じませんが。
はい、というわけで、お疲れさまでした。
『カントールの定理』の証明は以上で終わりです。
参考になったのなら、幸いに思います。