カントールの対角線論法は何を証明しているのですか？

0と1の間の実数は非可算であること：どんなに巧みに構成したリストも、その区間のすべての実数を含むことはできないということを証明しています。リスト上のどの位置よりも、実数のほうが単純に多いのです。

「非可算」とはどういう意味ですか？

集合が可算であるとは、その要素のそれぞれに自然数のラベル（1、2、3、…）を対応させて、何も残らないようにできることです。自然数、整数、有理数はすべて可算です。実数はそうではありません：どのような一対一対応も作れないほど数が多すぎるのです。

漏れた数をリストに追加してはいけないのですか？

追加することはできます。しかしそうすると、対角線論法がその新しい長くなったリストに対しても適用され、また別の漏れた数が生み出されます。この論法は、どれほど長く巧みに作られたリストにも有効なので、リストを完全にする方法はありません。

数字を変えるときに0と9を避けるのはなぜですか？

一部の実数は小数展開を二通り持ちます：0.4999…と0.5000…は同じ数です。数字を0か9に変えると、すでにリストにある数の「別名」に偶然たどり着いてしまうかもしれません。0と9を避けることでこの技術的な問題を回避し、証明をクリーンに保てます。

有理数も非可算ですか？

いいえ。有理数は可算です：すべての分数p/qを体系的に列挙して、それぞれに自然数の番号を割り当て、何も漏らさないようにできます。カントールの対角線論法が対象とするのは実数であり、有理数ではありません。

カントールの対角線論法：実数が列挙できない理由

誰かがあなたにリストを手渡したとします。それは無限のリストで、0と1の間のすべての実数が含まれていると主張されています。サンプルでも抜粋でもなく：r1、r2、r3、というようにきれいに番号を振られて、永遠に続く、すべての実数が。

1891年、ゲオルク・カントールの答えはこうでした：どんなリストを渡されても、私はそこに載っていない数を読み取ってみせる。その構成は説明するのに約30秒かかります。その結果を数学者たちが吸収するのには数十年かかりました。なぜなら、それは無限が一種類以上あることを意味するからです。

数えることとリスト化すること

対角線の操作に入る前に、「可算」とは何かを正確にしておくと役立ちます。集合が可算であるとは、各要素に一意の自然数のラベルを割り当てられること：第1の要素、第2の要素、第3の要素、というように、何も余らせずに。自然数自身は定義上可算です。整数も（0、1、-1、2、-2、…と列挙できます）、有理数も、分数を列挙するには巧みなジグザグパターンが必要ではありますが、可算です。

カントールの論法は、0と1の間の実数が本当に異なることを示します：どのようなラベル付けも存在しない、どんなに試みても。これは想像力の欠如ではありません。その作業が不可能であることの証明です。

リストが存在すると仮定する

この論法は背理法による証明です。まず相手にすべてを与えることから始めます：(0, 1) のすべての実数の完全なリストが実際に存在すると仮定します。各数を無限の小数展開で書きます。

リストはこのように始まるかもしれません：

r1 = 0.14159265...
r2 = 0.73205080...
r3 = 0.00000000...
r4 = 0.27182818...
r5 = 0.91415926...
...

各エントリは永遠に続きます。リストも永遠に続きます。そして、仮定により、0と1の間のすべての実数がどこかに現れます。

では、対角線を読み下したときに何が起きるか見てみましょう。

対角線を読む

r1の小数第1位、r2の小数第2位、r3の小数第3位、というように読んでいきます。上の例では、これらの対角成分は：1、3、0、2、9、… です。

次に、新しい数dをひとつずつ構成します。ルールは：各対角成分について、意図的に0と9を避けながら、別の数字を選ぶ。

r₁	.	1	4	1	5	9
r₂	.	3	3	3	3	3
r₃	.	5	0	0	0	0
r₄	.	7	1	8	2	8
r₅	.	6	0	2	5	9
new	.	2	4	1	3	8	…

Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.

対角成分は 1、3、0、2、9 です。ルールを適用すると 2、4、1、3、8 が得られます。したがって d = 0.24138…

0と9を避けることは小さいながらも必要な配慮です。一部の実数は小数展開を二通り持ちます：0.4999…と0.5000…は数直線上の同じ点を指しています。数字を0か9に変えると、すでにリストにある数の「別名」に偶然たどり着き、論法が濁ってしまうかもしれません。すべての変更後の数字を1から8の範囲に収めることで、dがただひとつの小数展開を持つことが保証され、以下の比較がクリーンになります。

新しい数はすべてのエントリと異なる

ここが核心です。

dはr1と小数第1位が異なる

dの第1位はr1の第1位と異なるよう選ばれました。したがってdはr1と等しくありません。第1位で異なります。

dはr2と小数第2位が異なる

dの第2位はr2の第2位と異なるよう選ばれました。したがってdはr2と等しくありません。第2位で異なります。

dはrnと小数第n位が異なる（すべてのnについて）

構成により、dの第n位はrnの第n位と異なります。どこかの位が異なる二つの数は等しくないため、dはどんなnを選んでもrnと等しくありません。

これが対角線の操作です：dはリスト上の各エントリが最も露出しているひとつの点、すなわちそれ自身の対角位置で、意図的にすべてのエントリと食い違うよう設計されました。

dは0と1の間の実数だが、リストに載っていない

数d = 0.24138…は明らかに区間(0, 1)内の実数です。しかし今示したように、dはr1とも、r2とも、r3とも、すべてのエントリと異なります。リストが完全であれば、dはどこかに現れるはずです。現れません。つまり、リストは完全ではありません。

矛盾は鮮明です：リストが完全だと仮定し、そこに載っていない実数を生み出しました。仮定は誤りです。0と1の間の実数の完全なリストは存在しません。

これが実際に意味すること

数学者は、自然数の濃度をアレフ・ヌル（ヘブライ文字アレフで書く：最初の超限基数）と呼びます。実数はそれより厳密に大きい濃度を持ち、cまたは2のアレフ・ヌル乗と書かれることもあります。カントールの論法こそが、これら二つの無限が同じ大きさではないことを確立するものです。

これはカントールが発表した当初、深く論争を呼びました。一部の同僚はこの結果を珍奇なものか誤りとして退けました。どちらでもありません。集合、濃度、実数直線の構造について数学者がどう考えるかの基盤に置かれており、何が計算できて何が計算できないかという問いにも直接つながっています（形式体系の限界に真なる命題が突き当たる別の事例として、グッドスタインの定理の証明もご参照ください）。

対角線はなぜ機能するのか

この論法が美しいのはその具体性です。漏れた数を推測したり、実数の大きさについての漠然とした直感に訴えたりしていません。リスト上の各エントリが制御している位置を正確に読み取り、各エントリをその位置で回避する数を構成しています。

リスト自身があなたにどこを見ればいいか教えてくれます。リスト上の各エントリが、そのリストが含むことのできない数を作るための座標、すなわち自分自身の対角成分を、ひとつずつ手渡してくれます。

その単純さは惑わせます。リスト上のエントリについて何も知る必要がありません。どんな数が載っているか、どんな順序か、どのように選ばれたかは問いません。論法は普遍的です：どんな実数のリストを選んでも、対角線の構成はそのリストに載っていない実数を生み出します。

その禅的な本質

カントールの対角線論法は、機能しないはずに見える数学的結果という長い系譜の中にあります。証明を眺めながら、トリックを、隠れた仮定を、論理が滑る場所を待ちます。ありません。証明は見た目の通りに単純です。

受け入れることを求められる内容は、証明そのものより奇妙です：「無限」はひとつの目的地ではない、ということ。整数も実数も両方無限ですが、根本的に異なる仕方で無限です。対角線論法はその分割線です。

無限の集合がどれほど奇妙にふるまえるかをより深く感じたければ、無限小数の構造を次に見るのがよいでしょう。あるいは、数列が値に永遠に近づきながら到達しない極限の働きも。対角線論法はその同じ家族に属しています：無限の縁で何が起きているかを、直感が正直であり続けるために証明を必要とする場所で、精確に、辛抱強く見つめること。

無限はひとつではない。それがこのニュースです。それを届ける論法は、半ページに収まります。