|| 冪集合を思い出して
この定理は ↓ であることを主張しています。
\begin{array}{llllll} \displaystyle \mathrm{Card}(S)&<&\mathrm{Card}(2^S) \end{array}
スポンサーリンク
そういうのが定義されてる上での話になるんですが、
「元の集合の濃度（要素数） \mathrm{Card}(S) 」より
「冪集合の濃度 \mathrm{Card}(2^S) 」の方がでかい
\begin{array}{llllll} \displaystyle \mathrm{Card}(S)&<&\mathrm{Card}(2^S) \end{array}
これは直感的に分かると思います。
\begin{array}{lllll} \displaystyle S&=&\{ 0,1,2 \} \\ \\ 2^S&=&\Bigl\{ \{\},\{0\},\{1\},\{2\},\{0,1\},\{1,2\},\{2,0\},\{0,1,2\} \Bigr\} \end{array}
実際、これは有限集合だと当然です。
特に疑問は出ないと思われます。
\begin{array}{llllllll} \displaystyle N&=&\{0,1,2,3,4,5,...,n,...\} \\ \\ \mathrm{Card}(N)&=&\aleph_0 \\ \\ 2^N&=&\Bigl\{ \{\},\{0\},\{1\},...,\{0,1\},...,N \Bigr\} \\ \\ \mathrm{Card}(2^N)&=& \,\, ? \end{array}
でも、「無限集合」でこれは成立するのか
これがなんかよく分かんなくないですか？
とまあこれはそんな感じの話で、
この記事では、これを丁寧に証明していきます。
使う方法は「対角線論法」（背理法の一種）
これを解説して、証明は最後に。
証明までの大雑把な流れ
必要条件「定理の発想のもとになったもの」
方針「冪集合と単射の確認」
細かな方針「記号の確認」
前提「単なる事実の確認」
対角線論法「後者を使って外側を導く」
外側の意味「決定された枠の中から、その他を得る」
都合の良い集合「明らかに外側にある集合」
必要条件（発想の源）
普通に考えて
「冪集合」の操作を行えば「要素」は増えます。
これは「有限」なら確実に確かめられることで、
直感的にすぐ理解できる事実です。
実際、最小の集合となる『空集合』ですら
その『冪集合』を作れば『 \{∅\}⊂\{∅,\{∅\}\}=2^∅ 』となる上に
\begin{array}{llllllll} \displaystyle {}_{n}\mathrm{C}_0+{}_{n}\mathrm{C}_1+{}_{n}\mathrm{C}_2+\cdots+{}_{n}\mathrm{C}_n&=&\displaystyle \sum_{k=0}^{n}{}_{n}\mathrm{C}_k \\ \\ &=&(1+1)^n &=&2^n \end{array}
『冪集合の要素の数え上げ』を行えば、
その数がこうなることは「二項定理」より明らか。
\begin{array}{llllllllll} \displaystyle \mathrm{Card}(S)&=&n \\ \\ \mathrm{Card}(2^S)&=&{}_{n}\mathrm{C}_0+{}_n\mathrm{C}_1+{}_{n}\mathrm{C}_2+\cdots+{}_{n}\mathrm{C}_n \\ \\ &=&\displaystyle 1+n+\frac{n(n-1)}{2\cdot 1}+\cdots+\frac{n(n-1)\cdots 2\cdot 1}{n(n-1)\cdots 2\cdot 1} \end{array}
\begin{array}{lllllll} \mathrm{Card}(S)&=&n \\ \\ \mathrm{Card}(2^S)&>&n+1 \end{array}
これが分からなくても大小関係が明らかなので、
当然すぎて論じる意味自体があまりありません。
ただ、これはあくまで有限の範囲の話
要素数が「無限」でどうなるのかは不明です。
\begin{array}{llllllll} \displaystyle \lim_{x→\infty} \frac{2^x}{x} &=&\displaystyle \infty \end{array}
「収束」とか「加速度」とか
そういうのを考えてみると、
「無限」でもそうなるんじゃ？って感じはしますが
\begin{array}{llllll} \displaystyle \mathrm{Card}(S)&<&\mathrm{Card}(2^S) \end{array}
本当にこうなると言えるのか。
この時点では、断言できる根拠がありません。
方針
「無限集合」を含む「集合」を S とします。
『冪集合』は慣例通り 2^{S} で表現
\begin{array}{lllllll} \displaystyle S&&\mathrm{Set} \\ \\ 2^S&&\mathrm{Power \,\, Set} \end{array}
『冪集合』の定義から ↓ も自明とします。
\begin{array}{lllllllll} \displaystyle \mathrm{Card}(S)&≤&\mathrm{Card}(2^S) \\ \\ |S|&≤&|2^{S}| \end{array}
一応、簡単に証明
「一元集合 \{e\}⊆S 」で『単射』を作ります。
\begin{array}{llllllllll} \displaystyle ∀e & \{e\}∈2^{S} \end{array}
\begin{array}{llllllllll} \displaystyle f&:&e&→&\{e\} \end{array}
このように
「単射が存在する」のは直感的に確実なので、
『濃度』は必ず「 \begin{array}{lllll} \displaystyle |S|&≤&|2^{S}| \end{array} 」
ただ『全射の存在』や『全単射の存在』は不明なので、
その辺りについては言及しません。
細かな方針
定義から『 \begin{array}{lllllll} \displaystyle |S|&≤&|2^{S}| \end{array} 』は確定です。
つまり「 S から 2^{S} 」への「単射」は存在します。
しかし「 S から 2^{S} 」への「全射」があるかどうかは
この時点では『無限集合』の場合だと分かりません。
同時に「全単射」があるかも不明です。
とはいっても、直感的には「全射」は無さそう。
同じく「全単射」もなさそうで、
予想では『 2^S の要素数が大きい』ですから、
全射が構成可能かどうかを調べることができれば
この問題は解決できそうです。
確認しておくと、
「 S から 2^{S} 」への「全射」があるということは、
『 S 』から『 2^{S} 』の要素の全てが得られるということ。
つまり「全ての要素が得られない」
これが確定すれば『全射』は存在しません。
つまり
そのような「得られない要素が存在する」なら
「予想 \begin{array}{lllllll} \displaystyle |S|&<&|2^S| \end{array} 」が正しいと言えます。
前提
ある「集合 S 」があって
その「冪集合 2^{S} 」があるとします。
そして「冪集合 2^{S} 」は
定義が『 S の部分集合の全て』ですから
当然「集合 S 」の部分集合は全て持っていて
\begin{array}{lllllll} \displaystyle S_{\mathrm{pt}}&⊂&S \end{array}
その中身に着目するために
「集合 S 」の「部分集合」を
とりあえず『 S_{\mathrm{pt}} 』と表現することにします。
また ↑ で確認したように、
「 S から 2^S への単射」は『存在する』
これも自明のこととしておきます。
対角線論法 Diagonal Method
|| 平面的な情報から導ける背理法
この証明方法の最大の特徴は
『見える範囲』から『見えない範囲』を作る感じで、
『冪集合 2^{S} 』を考えた時に
ある部分集合を「作ることができてしまう」ことから
それを用いて『全射の存在』を否定します。
結論としては、
その「部分集合」は ↓ みたいなやつで
\begin{array}{llllll} \displaystyle S^{\mathrm{Out}}_{\mathrm{pt}}&=&\{e∈S \mid e∉f(e)\} \end{array}
これが全射の存在を否定するんですよ。
証明
まず ↓ を仮定します。
\begin{array}{llllll} \displaystyle f(e)&=&S^{\mathrm{Out}}_{\mathrm{pt}} \end{array}
これを満たす e∈S が存在する
\begin{array}{llllll} \displaystyle ∃e∈S &\Bigl( f(e)&=&S^{\mathrm{Out}}_{\mathrm{pt}} \Bigr) \end{array}
まあつまり
『 S の要素』から「 S^{\mathrm{Out}}_{\mathrm{pt}} 」が
『像』として得られるってことにします。
仮定から得られる事実
こうすると、なぜか矛盾が出る。
不思議なもんで ↑ みたいにする理由はさっぱりですが、
\begin{array}{llllll} \displaystyle S^{\mathrm{Out}}_{\mathrm{pt}}&=&\{e∈S \mid e∉f(e)\} \end{array}
証明の主文となる ↓ の話は
わりと理解しやすかったりします。
\begin{array}{llllll} \displaystyle e&∈&S^{\mathrm{Out}}_{\mathrm{pt}} \\ \\ e&∉&S^{\mathrm{Out}}_{\mathrm{pt}} \end{array}
このどっちであるか調べるだけなので。
\mathrm{Case\,1}
まだ不明なので
e∈S^{\mathrm{Out}}_{\mathrm{pt}} である場合を考えます。
\begin{array}{llllll} \displaystyle S^{\mathrm{Out}}_{\mathrm{pt}}&=&f(e) \end{array}
すると仮定より
こうなる e があるわけですが
S^{\mathrm{Out}}_{\mathrm{pt}} の定義は『 e∉f(e) 』です。
\begin{array}{llllll} &&\displaystyle S^{\mathrm{Out}}_{\mathrm{pt}}&\textcolor{pink}{=}&f(e) \\ \\ e&∈&\displaystyle S^{\mathrm{Out}}_{\mathrm{pt}} \end{array}
これを満たす e はありません。
つまり、矛盾しています。
具体的な感じ
「 S^{\mathrm{Out}}_{\mathrm{pt}} が要素 1 を持つ」
「 S^{\mathrm{Out}}_{\mathrm{pt}}=f(1) 」だと仮定する
「部分集合 S^{\mathrm{Out}}_{\mathrm{pt}} 」の定義から
\begin{array}{llllll} \displaystyle S^{\mathrm{Out}}_{\mathrm{pt}}&=&\{e∈S \mid e∉f(e)\} \end{array}
\begin{array}{llllll} \displaystyle 1&\textcolor{pink}{∈}&f(1) \end{array}
「要素 1 」を持ってるはずがないことが分かる。
\mathrm{Case\,2}
↑ のパターンは違うと分かりました。
\begin{array}{llllll} \displaystyle e&∉&S^{\mathrm{Out}}_{\mathrm{pt}} \end{array}
ということは、これはこのパターンになるはず。
そう考えて話を進めていくわけですが
仮定より
↓ を満たす e は存在します。
\begin{array}{llllll} \displaystyle S^{\mathrm{Out}}_{\mathrm{pt}}&=&f(e) \end{array}
しかし『 S^{\mathrm{Out}}_{\mathrm{pt}} 』の定義『 e∉f(e) 』より
\begin{array}{llllll} \displaystyle e&∈&S^{\mathrm{Out}}_{\mathrm{pt}} \end{array}
間違いなくこういうことになります。あれ？
具体的な感じ
「 S^{\mathrm{Out}}_{\mathrm{pt}} が要素 1 を持たない」
「 S^{\mathrm{Out}}_{\mathrm{pt}}=f(1) 」になると仮定すると
「 S^{\mathrm{Out}}_{\mathrm{pt}} 」の定義『 e∉f(e) 』より
「要素 1 」を持つはずと分かる。
以上、仮定を認めた場合
\begin{array}{llllll} \displaystyle e&∈&S^{\mathrm{Out}}_{\mathrm{pt}} &&→&&e&∉&S^{\mathrm{Out}}_{\mathrm{pt}} \\ \\ e&∉&S^{\mathrm{Out}}_{\mathrm{pt}}&&→&&e&∈&S^{\mathrm{Out}}_{\mathrm{pt}} \end{array}
いずれのパターンも矛盾すると分かったので、
これ満たす『 e∈S 』が存在しないことが分かりました。
ということはつまり
『この部分集合 S^{\mathrm{Out}}_{\mathrm{pt}} 』は
『定義域 S 』からの『像 f(e) 』じゃありません。
しかし『集合 S の部分集合』なのは確実で
つまり『冪集合 2^{S} 』の「要素」でもあります。
ということは
『この部分集合 S^{\mathrm{Out}}_{\mathrm{pt}} 』は
『要素 e∈S 』から『像 f(e) 』として得られないので
つまりそんな『 S^{\mathrm{Out}}_{\mathrm{pt}} を得る写像』は無い。
つまり「冪集合への全射」は存在しない、と言えます。
都合の良い集合
確認しておくと
\begin{array}{llllll} \displaystyle \{e∈S \mid e∉f(e)\} \end{array}
これは『紐づけされた e が要素に無い』
とまあそんな感じのやつなんですが、
初見でこれがどういうものか
理解するのは困難だと思います。
『像の要素』に無いものと紐づけるよ
『像 f(e) 』に「紐づけされた e 」は無いよ
これはそういう感じの集合なんですけど
その役割や導出された経緯については謎だらけ。
なんで矛盾を生じるのか
どうしてそう都合が良いのか
これだけ見てもその辺りのことは分からないと思います。
対角線上から得られる外側（だいたい右下）
とりあえずこの都合の良い集合を作ってみます。
やり方は「実数と自然数の濃度」でやったのと同様
| e_1∈S_{\mathrm{pt}} | e_2∈S_{\mathrm{pt}} | e_3∈S_{\mathrm{pt}} | e_4∈S_{\mathrm{pt}} | … | |
| e_1 | 1 | 0 | 0 | 1 | |
| e_2 | 0 | 0 | 1 | 0 | |
| e_3 | 1 | 0 | 1 | 0 | |
| e_4 | 0 | 0 | 0 | 0 | |
| … |
『平面的な情報』を参考に
『全射を否定するための情報』を導き出します。
前提
しつこいですが、
もう一度記号と事実の確認をしておきます。
\begin{array}{llllllllll} \displaystyle S&&\mathrm{Set} \\ \\ 2^S&&\mathrm{Power \,\, Set} \end{array}
\begin{array}{lllllll} \displaystyle S_{\mathrm{pt}}&⊂&S \end{array}
\begin{array}{llllllll} \displaystyle f_{\mathrm{Injection}} &:&e_i&→&\{e_i\} \end{array}
\begin{array}{llllllll} \displaystyle \mathrm{Card}(S) &≤&\mathrm{Card}(2^S) \end{array}
\begin{array}{lllllllllll} \displaystyle S_{\mathrm{pt}}&∈&2^{S} \\ \\ S^{\mathrm{Out}}_{\mathrm{pt}}&∈&2^{S} \\ \\ \end{array}
最後の行がかなり大事なので
この部分は確実に覚えておいてください。
S^{\mathrm{Out}}_{\mathrm{pt}} を作ってみる
↑ で行った証明はどうでしたか？
まあ、なんとなく分かったとは思うんですが、
\begin{array}{llllll} \displaystyle \{e∈S \mid e∉f(e)\} \end{array}
この都合の良い「 S^{\mathrm{Out}}_{\mathrm{pt}} 」がどこから出てきたのか
ここだけなんかよく分かんなくないですか？
分かるなら ↓ の話は不要なんですが、
分からなかった自分みたいな人のために
以下、この S^{\mathrm{Out}}_{\mathrm{pt}} を作る手順を解説していきます。
対応しないっぽい部分集合
『全射が存在しない』ことを示したい。
つまり『像として写らない 2^S の要素』が欲しい。
\begin{array}{llllll} \displaystyle f&:&e&→&× \end{array}
まあつまり『定義域の要素』とは
『関係の無い部分集合』が欲しい。
\begin{array}{llllll} \displaystyle 2^{S}\setminus f(e) \end{array}
これが大まかなスタートラインで、
これを見つけるために、
\begin{array}{llllll} \displaystyle f(S)&⊂&2^{S} \end{array}
「写像で得られるもの全て」
これをとりあえず考えてみます。
外側を得るためには内側を知る必要がある
仮に『全射が存在する』のであれば
\begin{array}{llllll} \displaystyle f(S)&=&2^S \end{array}
こうなる f があるわけですが、
まだこの時点ではなにもとっかかりがありません。
肝心の f に具体性が何も無いです。
これを解消するには具体的にしていくしかないんですけど、
この時点ではどうすれば良いのかさっぱり。
写像 f の表現方法に何を選べばいいのか。
特に何の指針もありません。
なのでとりあえず
『全ての e を紐づけて』その「外側」を見る
こういうことをしてみることにします。
表で要素と像の関係を見る
横軸を「 S の部分集合が持つ要素 e∈S_{\mathrm{pt}}⊆S 」
縦軸を「 S の要素 e 」とします。
その上で
「結びついてる部分集合の要素」なら「 1 」とし、
「部分集合の要素じゃない」なら「 0 」とすると、
\begin{array}{llclll} \displaystyle f \\ \\ &e_1&→&\{e_1,e_4,...\} \\ \\ &e_2&→&\{e_3,e_5,...\} \\ \\ &e_3&→&\{e_1,e_3,...\} \\ \\ & & \vdots \end{array}
このときの「写像 f 」の情報は↓みたいに。
| e_1∈S_{\mathrm{pt}} | e_2∈S_{\mathrm{pt}} | e_3∈S_{\mathrm{pt}} | e_4∈S_{\mathrm{pt}} | \cdots | |
| e_1 | 1 | 0 | 0 | 1 | |
| e_2 | 0 | 0 | 1 | 0 | |
| e_3 | 1 | 0 | 1 | 0 | |
| e_4 | 0 | 0 | 0 | 0 | |
| \vdots |
写像はこのように、いくつかの表現方法があります。
で、ここからが大事なんですが、
実はこの情報から『 S^{\mathrm{Out}}_{\mathrm{pt}} 』が得られて
そこで「対角線」が利用されます。
定義域の要素と部分集合の要素
「定義域の要素 e 」ごとに
『写像 f(e) 』の対応は決まっています。
\begin{array}{llllll} \displaystyle f(e)&=&S_{\mathrm{pt}} \end{array}
ここから『全射の存在を否定する』ような
そういう「像（冪集合の要素）」を得るには
『 e と紐づけされない部分集合 S_{\mathrm{pt}}^{\mathrm{Out}} 』が必要で
これを一般的に表現するとなると、
『 e と結びついた全ての要素 S_{\mathrm{pt}} 』を考える必要が。
| e_1∈S_{\mathrm{pt}} | e_2∈S_{\mathrm{pt}} | e_3∈S_{\mathrm{pt}} | e_4∈S_{\mathrm{pt}} | … | |
| e_1 | \textcolor{skyblue}{1} | 0 | 0 | 1 | |
| e_2 | 0 | \textcolor{skyblue}{0} | 1 | 0 | |
| e_3 | 1 | 0 | \textcolor{skyblue}{1} | 0 | |
| e_4 | 0 | 0 | 0 | \textcolor{skyblue}{0} | |
| … |
そこで使えるのがこの表で、
『表中の要素の対応』から
「全ての e と S_{\mathrm{pt}} の対応」の情報を取得して
\begin{array}{llllll} \displaystyle f&=&(1,0,1,0,...) \\ \\ f^{\mathrm{Out}}&=&(0,1,0,1,...) \end{array}
その「どれとも違う写像 f^{\mathrm{Out}} 」を定義します。
これが『対角線論法』と呼ばれるやり方で
\begin{array}{llllll} \displaystyle f&=&(1,0,1,0,...) \end{array}
全てから一個ずつとるために「左上から右下」へ
「対角線」にある『含む含まないの情報』を全て得て
『全ての対応 e→ と共通点を持つ対応』を作り
\begin{array}{llllll} f^{\mathrm{Out}}&=&(0,1,0,1,...) \end{array}
その「 0,1 」を入れ替えて、はい出来上がり。
\begin{array}{llllll} \displaystyle f&=&(1,0,1,0,0,...) \\ \\ &↓& \\ \\ S_{f}&=&\{ e_1,e_3,... \} \end{array}
\begin{array}{llllll} \displaystyle f&→&S_{f}&∈&f(e) \\ \\ \displaystyle f^{\mathrm{Out}}&→&S_{f^{\mathrm{Out}}}&∉&f(e) \end{array}
こうして出来上がった「写像 f^{\mathrm{Out}} 」から作れる集合 S_{f^{\mathrm{Out}}}
これはどの「集合 S の要素 e 」からも
確実に『像 f(e) 』として得ることはできません。
なぜならこの「写像 f^{\mathrm{Out}} 」は、
『全ての e からの対応と共通点を持つ f 』
この対応を全て入れ替えた対応ですから
\begin{array}{llllll} \displaystyle e&→&S_{f^{\mathrm{Out}}}&× \end{array}
表中のどの「要素 e からの像 f(e) 」とも異なっていて
その上で『間違いなく部分集合 S_{\mathrm{pt}}^{\mathrm{Out}} を得られる』
まあつまり
これは『像 f(e) じゃない』ので、
『全射の存在を否定する部分集合』になります。
f(e) ではない写像と部分集合 S_{\mathrm{pt}}^{\mathrm{Out}}
一度「全部調べて」それと『違うってことにする』
その上で『 S_{\mathrm{pt}}^{\mathrm{Out}} は S の部分集合』である
\begin{array}{llllll} \displaystyle \overline{f}&=&f^{\mathrm{Out}} \end{array}
この「写像 f^{\mathrm{Out}} 」の情報から
「集合 S の要素」を抜き出して
\begin{array}{llllll} \displaystyle f&=&(1,0,1,0,0,...) \\ \\ \displaystyle f^{\mathrm{Out}}&=&(0,1,0,1,1,...) \\ \\ &↓& \\ \\ S_{f^{\mathrm{Out}}}&=&\{ e_2,e_4,e_5,... \} \\ \\ &=&S_{\mathrm{pt}}^{\mathrm{Out}} \end{array}
「写像 f で e と紐づいていない」
『部分集合 S_{\mathrm{pt}}^{\mathrm{Out}} 』を得る。
これが『全射を否定する 2^S の要素』になって、
結果的に「像として得られる仮定」を否定する。
以上、ここまで分かってからの ↑ の証明に繋がる感じで、
実際のところ、 ↑ で紹介した証明はこの逆
先にこっちがあって、あっちがあります。
これで分かったと思うんですけど
「都合の良い部分集合 S^{\mathrm{Out}}_{\mathrm{pt}} 」は
そもそも最初から『像として得られないもの』だった。
だから都合よく矛盾が生じて
『全射の存在を否定できた』
改めて整理すると当然だよねって話で、
ぶっちゃけよく見られる ↑ の証明より
こっちの方が実感しやすい上に本質的だと思います。
まとめ
「対角線論法」の『対角線』とは
「平面的」に図を見た場合の『情報の位置』
『全てから情報を１つずつ抜き出して』
『全ての情報と共通点を持つものを作る』
その情報から『一切の共通点を持たないものを導く』
対角線論法ってのを短くまとめるなら
たぶんこんな感じの表現になると思います。
\begin{array}{llllll} \displaystyle \{e∈S \mid e∉f(e)\} \end{array}
また、これは ↑ で示したことの具体例で、
\begin{array}{llllll} \displaystyle f(e)&=&S_{\mathrm{pt}} \end{array}
| e_1∈S_{\mathrm{pt}} | e_2∈S_{\mathrm{pt}} | e_3∈S_{\mathrm{pt}} | e_4∈S_{\mathrm{pt}} | … | |
| e_1 | \textcolor{skyblue}{1} | 0 | 0 | 0 | |
| e_2 | 0 | \textcolor{skyblue}{1} | 0 | 0 | |
| e_3 | 0 | 0 | \textcolor{skyblue}{1} | 0 | |
| e_4 | 0 | 0 | 0 | \textcolor{skyblue}{1} | |
| … |
\begin{array}{llllll} \displaystyle f&:&e&→&\{e\} \end{array}
\begin{array}{llllll} \displaystyle f&=&(1,1,1,1,1,...) \\ \\ f^{\mathrm{Out}}&=&(0,0,0,0,0,...) \end{array}
\begin{array}{llllll} \displaystyle e&∈&f(e) \\ \\ e&∉&f^{\mathrm{Out}}(e) \end{array}
『全射の存在を否定する』写像の
「分かりやすいもの」の１つになります。
本題（カントールの定理）
大事な部分は終わったので後は消化試合です。
対角線論法が分かってればすぐに終わります。
証明
仮定
「 S 」から「 2^{S} 」への『全射』がある
矛盾の導出
『対角線論法』より
「集合 S 」から「冪集合 2^{S} 」へは
『像とならない部分集合 S^{\mathrm{Out}}_{\mathrm{pt}} 』が存在する。
これは「仮定」に反する事実
『像』じゃない「部分集合」
これを『冪集合』が持つのなら、
「全射」は存在しないということになります。
結論
冪集合の定義から ↓ は明らか
\begin{array}{lllllll} \displaystyle |S|&≤&|2^{S}| \end{array}
しかし ↑ の事実から、
「 S 」から「 2^{S} 」への『全射』は存在しない。
これが分かっているので、
\begin{array}{lllll} \displaystyle |S|&≠&|2^{S}| \end{array}
こうですから、
\begin{array}{lllll} \displaystyle |S|&<&|2^{S}| \end{array}
こうなることが分かります。
以上、証明終わり
余談
要素数を表現する演算子はいろいろあるんですけど、
個人的には ↓ のやつが好みですね。分かりやすいんで。
\begin{array}{lllllll} \displaystyle \mathrm{Card}(S)&<&\mathrm{Card}(2^S) \\ \\ \mathrm{Cardinal}(S)&<&\mathrm{Cardinal}(2^S) \end{array}
ちなみに「 \mathrm{Cardinal} 」の意味は『基数』です。
これも別記事でまとめてるんで参考にどうぞ。
対角線論法はずるい？
対角線論法なんですけど、
実はこれ、なんか嫌われてたりします。
間違ってるだとか
正しいとは言い切れないだとか
ずるいやり方だとか
なんかそういう意見があって、
認めない、みたいなことを言う人がいたりするんですけど
自分が見た限りですが、
ちゃんと否定できている人はいません。
順番を見落としているというかなんというか
そうなの？ってなる説しかないです。
対角線論法は無限公理の応用
「対角線論法」は連続性と似たような操作を行っています。
逆に言えば、連続性を認めるのなら対角線論法は正しいです。
まあ本質的には『無限公理』
というか『後者関数』なんですけど。
ともかく
「すでにあるもの」から
「その外側」にある新しいものを得られる
この理屈を正しいと思えない
対角線論法を否定している人は
つまりはこういうことを言っています。
一応簡単に紹介しておくと、
否定する理屈はだいたい ↓ みたいな感じで
『対角線論法』で作った「含まないもの」
これは『含めることができるはず』
一見正しいように見えるかもしれませんが
「対角線論法」の手続きの順番を見れば
これが見当違いな意見であることはすぐに分かると思います。
というのも先述の通り
これは連続性みたいな操作ですので
『新たな要素』は『後出し』で出現します。
つまり『元から含まれていた』はずはなくて
「外側に生成されてから」
その後に「内側に含めることが可能」になっただけで
\begin{array}{llllllll} \displaystyle f(e) \\ \\ f^{\mathrm{Out}} \end{array}
仮に『含める』というのなら
その操作自体もまた「後出し」
まあつまり
この写像 f が決まってから f^{\mathrm{Out}} は定義され
その後 f^{\mathrm{Out}} の要素を含めたいのなら
写像 f はそれを紐づけした別のものとして再生成され、
それに伴って f^{\mathrm{Out}} もまた再生成されます。
つまりどうあっても f^{\mathrm{Out}} は生成可能で、
その中身の全てを f で紐づけすることはできません。
ですから『含めることが可能』であっても、
「含めた後に」『含まれない部分が新たに生成』されるので
その理屈では否定できないんです。
まあなので、対角線論法はずるではありません。
明確に手順を構成できる理屈と言えます。
実際、プログラムも書けますしコードも単純。
「内側を定義」→「後者関数で外側を定義」ループ
そのまま無限公理の形を作ればいいだけですから。