対角線論法 — 実数は数えきれない

すべての実数に番号は付けられるか

偶数も整数も有理数も、ぜんぶ一列に並んだ（可算だった）。なら実数も並ぶだろう——と思いきや、並ばない。カントールが1891年に示した証明は、背理法（S2）の最高傑作だ。

対角線論法

0と1の間の実数がすべて一列に並べられたと仮定する。たとえば——

1番目： 0.5 1 4 1 5 9 …
2番目： 0.3 3 3 3 3 3 …
3番目： 0.7 1 8 2 8 1 …
4番目： 0.2 2 2 3 6 0 …
　⋮

ここで対角線——1番目の第1位、2番目の第2位、3番目の第3位、…——の数字を取り出す：5、3、8、3、…。

そして、その各桁を別の数字に変えた新しい数 b を作る（たとえば各桁に1をたす。9は0に）：

この b は、リストのどの行ともちがう。1番目とは第1位（5→6）でちがう。2番目とは第2位（3→4）でちがう。n番目とは第n位で必ずちがう——作り方がそうなっているから。

でもリストは「すべての実数」を並べたはずだった。bはどこにもない——矛盾！ ∎

よって、実数を一列に並べる方法は存在しない。実数は非可算——自然数より「本当に多い」無限だ。

無限には階層がある

同じ「無限」でも——

• 自然数・整数・有理数の濃度（可算無限、ℵ₀「アレフ・ゼロ」と書く）
• 実数の濃度（連続体の濃度）——こちらが真に大きい

しかもカントールはさらに示した：どんな集合にも、そのべき集合（部分集合全体——S1）は真に大きい濃度を持つ。つまり無限の階層はどこまでも続く。「無限はひとつ」という素朴な直観は、ここで完全に覆される。

この発見は当時の数学界を二分する大論争を巻き起こした。いまでは集合論は現代数学の土台だ——きみがこの区間で学んでいる「集合と写像の言葉」は、この激動をくぐり抜けて標準装備になったものなんだよ。

対角線の技は生きている

「リストのn番目と第n成分でちがうものを作る」——この対角線の技は、計算機科学の「停止性問題は解けない」（チューリング）や論理学の不完全性定理（ゲーデル）にまで受け継がれている。ハイウェイの遥か先の景色にも、この道はつながっている。

よくあるまちがい

その1：「bもリストに足せばいい」という反論。 足した新しいリストにもまた対角線論法が効いて、別の漏れが作れる。どんなリストにも漏れがある——それが証明の主張だ。

その2：「有理数も同じ論法で非可算になるのでは」という混乱。 対角線で作った数 b は循環小数になる保証がなく、有理数とは限らない（N11：有理数⇔循環小数）。だから有理数のリストには矛盾が生じない。論法の適用条件まで理解してこそ、証明を理解したことになる。

れんしゅう