【世界のパラドックス】カンターの対角線論法 ─ 無限にも「大きさ」の違いがある？

当サイトを閲覧いただきありがとうございます。本記事は「カンターの対角線論法」について解説します。

無限は無限。それ以上も以下もない、と思いきや、19世紀のドイツの数学者ゲオルク・カンターは、無限にも大小関係があることを証明してしまいましたし、その証明方法は、一度理解すると思わず膝を打つほどエレガントなものです。

無限は全部同じ大きさ？

まず、自然数（1、2、3、4…）は無限にあります。偶数（2、4、6、8…）も無限にあります。

直感的には自然数の方が偶数より多い気がしますが、実はこの二つは「同じ大きさの無限」です。なぜなら、自然数nに対して偶数2nを対応させれば、1対1で過不足なく対応がつくからです。

1↔2、2↔4、3↔6、4↔8…という具合に、全ての自然数に偶数を一つずつ割り当てることができ、余りもダブりもありません。

では、「実数」（小数を含む全ての数、例えば0.1415926…のような数）はどうでしょうか。実数も無限にあります。自然数と実数は同じ大きさの無限なのでしょうか？

カンターは対角線論法という手法で、実数は自然数より「真に多い」ことを証明しました。

証明は背理法で行います。「0から1の間の実数は全て自然数と1対1に対応がつく」と仮定して、矛盾を導きます。

仮に、0から1の間の全ての実数をリストにできたとします。

ここで、「対角線上の数字」に注目します。1番目の実数の1桁目、2番目の実数の2桁目、3番目の実数の3桁目…と拾っていくと、5、3、0、2、5… という数列が得られます（太字の部分）。

次に、この対角線の各数字を別の数字に置き換えた新しい小数を作ります。例えば、各桁に1を足す（9の場合は0にする）ルールにすると、6、4、1、3、6… となり、新しい実数 0.64136… ができます。

この新しい実数は、リストのどこにも載っていません。

結局のところ、リストに全ての実数を載せたはずなのに、リストに載っていない実数が作れてしまいました。これは「全ての実数をリストにできた」という仮定に矛盾します。

したがって、0から1の間の実数を自然数で番号付けすることは不可能であり、実数は自然数よりも「多い」のだと思います。

カンターの発見は衝撃的でした。無限は一つではなく、無限にも大きさの違いがあるのではないでしょうか。

自然数のような「数え上げられる無限」は「可算無限（アレフ・ゼロ）」と呼ばれ、実数のような「数え上げられない無限」は「非可算無限」と呼ばれます。

さらに驚くべきことに、この階層は終わりません。実数の集合よりもさらに大きな無限が存在し、その上にもさらに大きな無限が…と、無限のレベルが無限に続くのだと思います。

カンターの対角線論法は1891年に発表されましたが、当時の数学界では激しい批判を受けました。

特に影響力のある数学者レオポルト・クロネッカーはカンターを「若者の堕落者」と呼んで攻撃しました。クロネッカーは「神は自然数を作った。それ以外は人間の仕事だ」という立場で、無限に大小があるなどという考えは受け入れられなかったのです。

ただ、カンターの証明は論理的に完璧であり、時間とともに数学界に受け入れられていきました。今日では対角線論法は数学の最も美しい証明の一つとして広く認められています。

この証明手法の価値は、実数の非可算性を示したことだけではありません。同じ型の議論が、20世紀の重要な定理をいくつも生み出しました。

定理	発表	対角線論法の使われ方
ラッセルのパラドックス	1901年	自分自身を含まない集合を対角線的に構成
ゲーデルの不完全性定理	1931年	「この命題は証明できない」を対角線的に作る
チューリングの停止問題	1936年	判定結果の逆を返すプログラムを対角線的に作る
計算量の階層定理	1965年	より多くの時間を使えば解ける問題が増えることを示す