実数の集合や自然数のべき集合が自然数と1対1に対応させることができないことを証明したカントールの対角線論法は有名だ。例えば 0 から 1 未満の実数と自然数の1対1対応を作ることができないことを証明するには次のようにする。
仮に0以上1未満の実数を自然数と1対1対応させることができたとしてそれを a1, a2, a3 ... とする。また、a1 の小数点第1位の数を a11、第２位の数を a12、... 第 n 位の数を a1n と書くことにする。すると自然数 m に対応する実数の小数第 n 位の数は amn で表される。ここで、実数 b を次のように取る。b の小数第1位には、a11 と異なる数をとり b1 とする。同様に b2 には a22 と異なる数、.. と続けていく。そうすると b は小数表記で 0.b1b2b3..... で表わされるはずである。このようにしてできた b は明らかに a1, a2, a3, ... のどれとも一致しない。どのような自然数 n を取っても b は小数第 n 位で異なるからである。これは、仮定の自然数と0以上1未満の実数との1対1対応が成立しているということと矛盾する。故に、自然数と0以上1未満の実数を1対1に対応させることは不可能である。証明終り。
明解な証明であるが、なんとなく腑に落ちないものがある。もともとの1対1対応はこれ以上は洩れがないくらい多く自然数と実数を対応させていたはずである。それなのに、確かに b はこの1対1対応から洩れているが、しかしながら、これを先頭に持って来て新しい数列 b, a1, a2, ... を作るとこれは自然数に1対1に対応させることができるのである。
もちろんこの1対1対応にも対角線論法によってそれから洩れた数 b1 を作ることができるので自然数と実数の1対1対応は存在しないが、これを繰り返していくとどんどん多くの実数に対応する1対1対応が作れるではないかと思ってしまうのである。
有限集合間に全単射の関数が作れるときは、このふたつの集合の要素数は等しくなる。その類推で無限集合間に全単射の関数が存在するときその濃度が等しいと言う。濃度という用語をつかっても無限集合どうしの要素数が等しいのだという印象は拭えない。しかし、有限集合の全単射と、無限集合の全単射では意味がかなり異なると考えた方が良い。
それは、無限集合と有限集合では「全ての要素」の意味が違うからである。有限集合では全ての要素を列挙することができる。しかし、無限集合では全ての要素を列挙することは定義上不可能なのである。無限集合の全ての要素とは、「1は自然数である。n が自然数であるとき n + 1 は自然数である。」というような要素の生成規則を満たす要素のことである。この生成規則を無限に適用することによって無限の要素について考えると言うことになる。
有限集合 A と B の間の関数 f(x) が全単射の場合、B の任意の要素に対応する逆像が存在する。無限集合の場合も同じであるが、無限集合間の全単射があるということは、無限集合の生成規則をみたす任意の要素についてその逆像を定める有限の手続き(アルゴリズム)があるということである。実際、自然数と偶数の全単射や自然数と順序対の全単射はそのようなことが可能である。有理数の場合も既約分数のかたちで分子と分母の組を考えると順序対の場合と似た手法で自然数と１対１対応させることができる。
それでは、自然数と実数の全単射が「できない」ことの証明はどうだろうか。この場合は「どのようなアルゴリズムを持ってきても」自然数を対応づけることができない実数があることを証明できないといけない。問題は「可能な全てのアルゴリズム」をどう表現するかということである。
ここで、自然数と全単射を作ることのできる無限集合の要素の特長を考えてみよう。それらの集合の特長は「その要素を最初の一個からはじめて、もれなく一列にならべて行くことができる」ということである。一列にならべるのは簡単だが、「もれなく」並べることをどう証明したらよいのだろうか。自然数の場合にはそれは数学的帰納法と言う再帰的定義でなされる。1 から n-1 までの数ををもれなく一列に並べたとき、n 以下も全て一列に並べることができれば、全ての n について n 以下の数を全て一列に並べることができる。順序対 (x, y) についても同じことが言える。x < n, y < n を満たす全ての順序対が一列に並べることができるとき x <= n, y <= n, 以下の要素が全て一列に並べることができれば、全ての n について x <= n, y <= n 以下の順序対は一列に並べることができるので、順序対と自然数との全単射を考えることができる。
この観点から上で述べた対角線論法をみなおすと、どのような並べ方で実数を一列に並べていったとしても必ずその並べ方に含まれない実数が存在することが分かる。対角線論法の驚くべき結果である。しかし、どうしてそのようなことになってしまうのだろうか。
それは、実数の要素はどうやっても再帰的に全て列挙することはできないことを意味しているのではないだろうか。たとえば、自然数の順序対は (m, n) のように２個の整数で特定することができる。したがって、1 <= i <= n, 1 <= j <= n のとき順序対 (i, j) は全て列挙して一列に整列することが可能である。しかし、0 以上 1 未満の実数を２進数の小数点表記した a = 0.11010001... のような数は a = f(n1, n2, n3, n4, n5, ... ) のようにその数を特定するのに無限個の(0または1の値をとる)整数の組が必要になってくる。従って a1, a2, a3, ... と無限に一列に並べていっても、b = f(~a11, ~a22, ~a33, ... ) と a1, a2, a3, ... のどれとも違う実数を作ることができて、列挙する実数 an の数をどこまで増やしていっても実数を全て列挙する方法はないのである。
ところで、この b の作り方を良く見ると、実は、b は一個の数ではないのである。b は実数の集合を表していて、この手続をどこまで続けて行っても b が１つの実数として特定できないのだ。
すなわち上の例のように b = 0.b1b2b3... であるとすると、b は小数点下第１位が b1 となる実数の集合のうちの、第２位が b2 の集合のうちの、第３位が b3 の集合のうちの、... と続く実数の集合を表している。しかし、小数点下の n をどのように大きくしてもこの集合はつねに無限の要素を含んでおり、１つの数として特定することはできない。したがって、どのように an を１つずつ追加して並べて行っても、どんな n についても 集合 b の中には常に無限の数があり、いつでも a1, ..., an と異なる数を取りだすことができるのである。
このように対角線論法では無限小数では実数一個を特定することは不可能であることを利用して実数と自然数間の全単射がないことを証明しているのではないだろうか。つまり、自然数と実数との関係は、数と数との関係というよりも数と数の集合との関係と考えるべきなのだろう。対角線論法にあらわれているのは、自然数と実数の要素の数の問題と言うよりは、自然数の一個と実数の部分集合との対比ではないかと思う。
そうであるとして、実数の無限と自然数の無限とどれくらい違うのだろうか。b 一個だけなのだろうかそれとも無限に違うのだろうか。そこのところが、対角線論法ではよく分からない。そこで自然数に対応できた実数の集合を A とする。A の要素は大小関係がはっきりしているので小さい順に整列させることができる。そうすると整列した後の隣り合う実数を am と a(m+1) とすると {am + a(m+1)}/2 は am と a(m+1) の間の数であるがこれは A の要素ではない。集合 A のどの隣り合った実数の間にも集合 A に属さない要素があるとすれば、0から1までの区間内で集合Aに属さない実数は無限にあるのである。
A に含まれる数の隣り合う数の間隔がどんなに狭くても、その間に A に含まれない実数が存在する。そうして自然数から実数の集合 A への写像 f(x) が単射の場合、A の要素が一致することはない。
実数と自然数の根本的な違いはなんだろうか。自然数には間に数を取ることのできない隣の数(例えば 2 にたいする 1 と 3)があるが、実数の場合は隣の数というものはない。このために、無限に多くの自然数を持って来ても自然数と実数の1対1対応を作ることができないのである。
しかし、「自然数には隣の数があるが、実数は a と b が異なれば必ずその間に数が存在すると言う議論では、有理数も非可算と言うことになってしまうが、有理数は可算だ」という投稿があった。まったくその通りで、上の議論はもう少し考えなおさないといけない。
それでは、有理数と実数の違いは一体どこにあるのだろうか。有理数をそのものを扱うのはちょっとめんどうなので、自然数の順序対 (i, j) について考えてみよう。あきらかに正の有理数と順序対の部分集合とは全単射を作ることができる。従って順序対と自然数との全単射ができれば、有理数と自然数との全単射も可能になることがわかる。そこで、次のように順序対を並べて行くと順序対をどこまでももれなく列挙することができる。
(1,1)
(2,1),(1,2)
(3,1),(2,2),(1,3)
(4,1),(3,2),(2,3),(1,4)
...........................
また、この表示を自動的に延々と実行するプログラムも作ることができる。そのプログラムはメモリの許す限り順序対を表示し続けるだろう。
ところで、小数点下 n 桁までに制限した 0 から 1 までの小数を２進数で作る方法は次のような二分木になる。
.
0 1
0 1 0 1
0 1 0 1 0 1 0 1
....................................
この二分木をたどって小数点 n 桁までの全ての数をしらべて表示するプログラムも、簡単な再帰的プログラムで作ることができる。しかし、上の二分木の深さが無限大になったとき、この小数をもれなく表示するプログラムは無限の再帰を引き起こすためにコンピュータは沈黙してしまうのである。つまり、無限小数を含む実数の要素を全て表記するプログラムを書くことは不可能なのである。言葉を換えると、実数の要素を全て表示する再帰的なアルゴリズムは存在しないのである。
これが自然数と実数の全単射を作ることができない本当の理由なのではないだろうか。つまり、実数をもれなく並べるためにその要素である無限小数を１つだけ取りだすことすら不可能であるということである。
この二分木は有理数と実数の関係を考えるのにも便利である。0 から 1 までの実数の全体はこの二分木で表現でき、ひとつの枝のルートが１つの実数を表す。もちろん有理数もその枝の１つである。しかし、有理数の場合はある桁数以下は循環小数になるので、その枝を特定することができる。すなわち、任意の n についてこの小数の第 n 桁が何になるか正確に知ることができる。そこで、循環小数になる枝は色をつけてマーキングする。そうすると、枝わかれの階層が深くなる度にそのマーキングは増えて行くが、ある階層までに現れたマーキングの数は有限である。つまりある枝分かれの階層までに有理数であると判明した枝は列挙できる。そこで、階層が深くなる度に新に現れるマーキングに自然数を対応させて行けば、有理数を数えあげることができる。しかし、無限小数の場合は枝わかれの階層のどの深さについても取り得る可能性が無限なので列挙することができないのである。
つまり、ある枝わかれの階層以下に判明する有理数は有限個しかないが、実数はどの階層についても無限の可能性があるのである。これが、大きさで整列したときは、有理数も実数もどんなに接近した二つの数の間にも別の数が存在するのに、有理数の濃度は自然数と同じになり、実数はそうならない理由である。