対角線論法による3つの証明
リストの各項目と必ず異なるオブジェクトを構築する証明技法の一族 Lex Fridmanのポッドキャスト #488から始まった沼は続いている。今回は対角線論法（diagonalization）について掘り下げてみたい。基礎数学に繰り返し登場する証明技法だ。 核心となるアイデア：与えられたリストの各オブジェクトと「対角」のエントリを変えることで必ず異なるオブジェクトを構築する。この技法の3つのバリエーションを紹介するが、すべて同じ論理構造を共有している（いずれもポッドキャストで取り上げられている）。 ゲオルク・カントールは1891年に対角線論法を導入し、実数が自然数より真に大きな無限を形成することを証明した。 背理法のために、0と1の間のすべての実数をリストアップできると仮定しよう。各実数は無限小数として書ける： $$ \begin{array}{c|cccccc} & d_1 & d_2 & d_3 & d_4 & d_5 & \cdots \\ \hline r_1 & \mathbf{5} & 1 & 4 & 1 & 5 & \cdots \\ r_2 & 3 & \mathbf{3} & 3 & 3 & 3 & \cdots \\ r_3 & 7 & 1 & \mathbf{8} & 2 & 8 & \cdots \\ r_4 & 0 & 0 & 0 & \mathbf{0} & 0 & \cdots \\ r_5 & 9 & 9 & 9 & 9 & \mathbf{9} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array} $$ ここで対角線（$n$番目の数の$n$番目の桁）を見て、各桁を変更することで新しい数 $d$ を構築する。対角線の桁が5なら6に、そうでなければ5にする： $$d = 0.\mathbf{6}\mathbf{5}\mathbf{5}\mathbf{5}\mathbf{5}\ldots$$ この数 $d$ は、$r_1$ とは1桁目で、$r_2$ とは2桁目で、$r_3$ とは3桁目で、というように異なる。リストのすべての数と異なっている。 しかし、リストには0と1の間のすべての実数が含まれると仮定した。矛盾。したがってそのようなリストは存在しえない。実数は非可算なのだ。 カントールはさらに一般的なことを証明した。任意の集合 $X$ に対して、その冪集合 $\mathcal{P}(X)$（すべての部分集合の集合）は $X$ 自身より真に大きい。無限集合に対してもだ。 これは「最大の」無限が存在しないことを意味する。任意の無限集合が与えられたら、その冪集合を取ることでいつでもより大きなものを構築できる。 $X$ を任意の集合とする。部分集合は明らかに要素と同じ数以上ある（各要素 $x$ は単集合 $\lbrace x \rbrace$ に対応する）。問題は真に多いかどうかだ。 背理法のために、$X$ と $\mathcal{P}(X)$ が同じサイズだと仮定しよう。すると全単射 $f: X \to \mathcal{P}(X)$ が存在し、各要素を一意の部分集合に対応させる。 新しい部分集合を定義する： $$D = \lbrace x \in X : x \notin f(x) \rbrace$$ 言葉で言えば：$D$ は、対応する部分集合に入っていないすべての要素を含む。 $D$ は $X$ の部分集合なので、$D \in \mathcal{P}(X)$ である。そして $f$ は全単射なので、ある要素が $D$ に対応する。その要素をダイアナと呼ぼう。つまり $f(\text{ダイアナ}) = D$ である。 さて問う：ダイアナは $D$ に入っているか？ ダイアナ $\in D$ の場合： $D$ の定義により、ダイアナは対応する部分集合に入っていない要素ということになる。しかし彼女の対応する部分集合は $D$ なので、ダイアナ $\notin D$ となる。矛盾。 ダイアナ $\notin D$ の場合： するとダイアナは対応する部分集合に入っていない。それはまさに $D$ への所属条件である。だからダイアナ $\in D$ となる。矛盾。 どちらの場合も破綻する。したがって全単射は存在せず、$|\mathcal{P}(X)| > |X|$ である。 Joel David Hamkinsによる身近なたとえ話がある。任意の人々の集まりに対して、人数より多くの委員会を作ることができる。無限に多くの人がいてもだ。 委員会は単に人々の部分集合だ。主張は $|\mathcal{P}(\text{人々})| > |\text{人々}|$ である。 そうでないと仮定しよう。すると、すべての委員会を一人の人間にちなんで一対一対応で命名できることになる。（その人が自分の名前を冠した委員会に所属している必要はない。単なる命名だ。） 委員会Dを作る：自分の名前を冠した委員会に所属していない人すべて。 これは有効な委員会だ。誰かの名前を冠しているはずで、彼女をダニエラと呼ぼう。 ダニエラは自分の名前を冠した委員会に所属しているか？ 委員会の数は人数より多い。 Hamkinsのオックスフォードの学生による別のたとえ話。任意の果物の集まりに対して、果物の数より多くのフルーツサラダが可能だ。 フルーツサラダは単に果物の部分集合だ。もしサラダの数が果物と同じだけなら、各サラダを果物にちなんで命名できることになる。 対角線サラダを作る：自分の名前を冠したサラダに入っていない果物すべて。 このサラダは何かの果物の名前を冠しているはずで、例えばドリアンとしよう。 ドリアンは自分の名前を冠したサラダに入っているか？ 矛盾。サラダの数は果物より多い。 以前の記事で、ラッセルのパラドックスとそれがいかに素朴集合論を破綻させたかを探求した。そのとき強調しなかったのは、ラッセルの議論が同じ対角線技法だということだ。 並行する構造を見てみよう： 対応の仮定： すべての集合のクラス $V$ がそれ自体集合だと仮定する。するとすべての集合は「リストに入っている」ことになる。$V$ は自分自身を含むすべての集合をインデックスする。各集合 $x$ について問うことができる：$x$ は自分自身を含むか？ 対角線構築： 答えが「いいえ」であるすべての集合の集まり $R$ を作る： $$R = \lbrace x \in V : x \notin x \rbrace$$ これはカントールの構築を正確に反映している。カントールが「$x$ は対応する部分集合 $f(x)$ に入っているか？」と問うたところで、ラッセルは「$x$ は自分自身に入っているか？」と問う。集合 $R$ はすべての「いいえ」の答え（自分自身のメンバーでない集合）を集める。 矛盾： $R$ は集合の集まりであり、$V$ はすべての集合を含むので、$R \in V$ である。さて問う：$R \in R$ か？ 構造はダイアナ、ダニエラ、ドリアンと同一だ。仮定された対応（$V$ によってインデックスされたすべての集合）が対角線集合の形成を可能にし、それが存在しえないことが示される。 ラッセルが証明したのは、Hamkinsの言葉を借りれば：「普遍集合は存在しない。」$V$ が集合であるという仮定は矛盾に至るので、集合の宇宙それ自体は集合にはなりえない。 3つの証明すべてが同じ骨格を共有している： 対角線論法は、特定の集まりがいかなるリストやいかなる集合によっても捕捉できないほど大きいことを明らかにする。これは数学の構造そのものに組み込まれた根本的な限界だ。 この記事はClaude（Opus 4.5）と協力して書きました。1. カントールの証明：実数は非可算である
2. 冪集合は常により大きい
形式的な証明
人々と委員会
果物とフルーツサラダ
3. ラッセルのパラドックス：普遍集合は存在しない
共通の糸