カントールの対角線論法とは?「すべての一覧」に必ず抜けができる証明

カントールの対角線論法は、対象をすべて並べたと仮定した一覧から、そのどの行とも違う対象を作る論法です。無限に続く一覧でも、すべてを載せられるとは限らない。ここでは0と1の無限列を使い、抜けを作る仕組みを追ってみます。

まず「全部載った一覧」があると仮定する

0と1を終わりなく並べた列を考えます。全部0の列、010101…と交互になる列、規則が簡単に書けない列も含め、あり得るすべての列が対象です。一覧の行には1、2、3、…と番号を付けるとします。

この対象を全部載せた一覧がある、といったん仮定します。下の表はその仕組みを説明するための先頭部分の作例です。有限の四行だけで証明を済ませるのではなく、同じ手順を任意の行番号nへ定義します。

行1番目2番目3番目4番目続き
10010…
21101…
30100…
41011…

対角線を見て、数字を反転する

1行目の1番目、2行目の2番目、3行目の3番目、…を見ます。表では左上から右下へ斜めに進むので、対角線と呼びます。新しい列Dのn番目は、n行目のn番目が0なら1、1なら0にします。

上の作例なら、Dの先頭は1、0、1、0、…です。Dは0と1だけの無限列なので、最初に「全部集める」と決めた対象の一つです。特別な記号を混ぜて対象外へ逃げたわけではありません。

なぜ、どの行とも一致しないのか

Dは1行目とは1番目で、2行目とは2番目で、3行目とは3番目で違います。一般に、n行目とは必ずn番目が違います。ほかの位置がいくつ一致しても、少なくとも一か所違えば同じ列ではありません。

もしDが一覧のk行目に載っていたなら、Dのk番目は、そのk行目のk番目を反転した数字のはずです。同じ列だと仮定したのに、その位置で異なることになります。したがってDはどの行にも載っていません。「全部載っている」という最初の仮定が崩れます。

抜けた列を、最後に追加すればよい?

新しい列を一覧の先頭へ足して、元の行をずらすことはできます。しかし、その新しい一覧にも同じ反転操作を使えば、また載っていない列を作れます。もとの一覧の並べ方が悪かっただけ、という問題ではありません。

この議論は「何度追加しても作業が遅くて終わらない」という主張より強く、どんな一覧を提案されても、全部を覆えていないと示すものです。無限に行があることと、あり得る無限列を全部載せることは同じではないのです。

実数について話すとき、小数に注意する理由

0.4999…と0.5000…のように、小数表記が異なっても同じ実数を表す場合があります。そのため小数を使って「一桁違うから別の数」とだけ言うと、説明に穴が開きます。たとえば小数部分の各桁を3と4だけに限定すれば、この二重表現を避けた部分集合で同様の議論ができます。

その部分集合さえ自然数の番号では並べられないなら、それを含む実数全体も並べられません。上の0と1の説明では、まず数値への変換をせず「列そのもの」を比較することで、核心の操作に集中しています。

ヒルベルトのホテルとは矛盾しない?

ホテルの客を偶数・奇数の部屋へ振り分ける話は、最初から自然数の番号を付けられる集団を扱います。対角線論法が扱う0と1の無限列全体は、どんな番号付けでも漏れが出る集団です。同じ「無限」という言葉でも、大きさが同じとは限りません。

また、有限の0・1文字列なら、長さの短い順に並べ、その長さの中で順番を決めて一覧にできます。有限の文字列をすべて集めた場合と、一本一本が無限に続く列をすべて集めた場合も区別してください。

参考資料

MIT OpenCourseWare:Cantor’s diagonalization argument(3と4の小数を用いた説明)、MIT:Mathematics for Computer Science 第7章(無限集合と列挙)。本文の表と0・1の作例は説明のために作成しました。

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です