次: べき集合の濃度 上: 対角線論法 前: リシャールの逆理

カントールの対角線論法

南海　 ゲーデルの仕事の意味を知るためには，もう少し19世紀末の数学に現れた，数学の基礎に関する諸問題を知らねばならない．これを対角線論法という視点で見ていこう．

集合論におけるカントールの対角線論法と，そのひろがりを見てみよう．

『数学対話』−「高校数学の土台」−「実数とは何か」で，有理数の集合は自然数の集合と一対一の対応を作ることができるが，実数の集合には自然数との一対一対応が存在しないことを示した．これは偉大な発見だった．無限といっても同じではなく，段階があることをはじめて見いだした．

ここで「実数の集合には自然数との一対一対応が存在しない」を改めて考えよう．二つの集合$A$と$B$の間に一対一対応が存在するとき，二つの集合の濃度が等しいといい，$\vert A\vert=\vert B\vert$と書く．有限集合の場合は$\vert A\vert$は集合$A$の要素の個数そのものとする．

集合$A$が集合$B$のなかに埋め込める，つまり$B$の部分集合との間に一対一対応が存在するとき，濃度の関係は$\vert A\vert\le \vert B\vert$であると書く．$\vert A\vert\le \vert B\vert$ではあるが，$A$と$B$の間の一対一対応は存在しないときは$\vert A\vert<\vert B\vert$と書く．

これで濃度の大小，相等は定義された．

拓生　 まってください．「濃度の大小」は確かに定義されましたが，「濃度」そのものは定義されていません．

南海　 確かに．濃度そのものを定義してはいない．濃度を定義するためには，公理的な集合論の準備 や，選択公理などに関する理解が必要である．ここでは，一対一対応がつく集合は，何かが同じであると考え，その同じことにつけられた名前が「濃度」であるとした．

拓生　 問題はあるが，いまそれを解決することはできない，ということですね．また勉強してみます．

南海　 そういうことにしよう．さて， 自然数の集合と一対一の対応が存在する集合の濃度は，自然数の集合の濃度と等しいわけであるが，この濃度を$\aleph_0$と書き「アレフ0」と読む．

$\aleph$は，英語の$A$に相当するヘブライ語の文字である．濃度が$\aleph_0$である集合は可付番である，あるいは可算無限であるという．それに対して実数の集合の濃度を$\aleph$と書く．

カントールが最初に発見した集合論の定理が，次の定理である．この定理は，実数の集合の濃度は自然数の濃度より大きい，つまり実数の集合は可付番ではないことを意味する．カントールは1874年にはこれを発見していたが，1891年に次の証明のような対角線論法でこれを証明した．

定理 1        自然数の濃度$\aleph_0$と実数の濃度$\aleph$に関して不等式

$$\aleph_0<\aleph$$

が成り立つ． ■

証明      区間 $(0,\ 1]$，つまり$0<x\le 1$ を満たす実数の集合を考える．

自然数$n$に対して， $\dfrac{1}{n}\in (0,\ 1]$であるから，自然数から$(0,\ 1]$への埋め込みが存在する．よって

$$\aleph_0\le \left\vert(0,\ 1] \right\vert$$

である．

等号が成立しないことを背理法で証明する．

等号が成立するとする．つまり$0<x\le 1$ を満たす実数の集合が可付番であると仮定する． いいかえると，$0<x\le 1$ を満たす実数全体に番号を付けて次のようにできるとする．

$$\alpha_1,\ \alpha_2,\ \cdots \alpha_n ,\ \cdots$$

このような実数 $\alpha$ はすべて十進小数で

$$\alpha=0.a_1a_2a_3\cdots a_n\cdots$$

と表される．

ここで， $0.25=0.2500000\cdots$のように途中から後はすべて0が並ぶものを有限小数ということにし， $円周率-3=0.14159265358979\cdots$のように途中から0になることはないものを無限小数ということにする．

すると有限小数は

$$0.25=0.2499999\cdots$$

と無限小数に書き換えることができる．このように有限小数を無限小数で書くことに統一すれば，区間 $(0,\ 1]$の各実数は無限小数にただ一通りに書き表される．

$0<x\le 1$ を満たす実数の集合が自然数と一対一に対応すると仮定したので，対応する自然数の順に，$0<x\le 1$にある実数を並べる．それを

$$\begin{eqnarray*} \alpha_1&=&0.a_1^{(1)}a_2^{(1)}a_3^{(1)}\cdots a_n^{(1)}\cdot... ...n)}a_3^{(n)}\cdots a_n^{(n)}\cdots \\ \cdots&\cdots & \cdots \end{eqnarray*}$$

とする．ここに $a_i^{(n)}$ は $n$ 番目の小数の，小数第 $i$ 位の数を表している．

この対角線に並んでいる数$a_n^{(n)}$ に対して，数列$\{b_n\}$を次のように定める．

$$b_n= \left\{ \begin{array}{ll} 1 &(a_n^{(n)} \ne 1 )\\ 2 &(a_n^{(n)} = 1 ) \end{array} \right.$$

数列$\{b_n\}$から小数 $\beta$ を次のように定める．

$$\beta=0.b_1b_2\cdots b_n \cdots$$

すると $0<\beta \le 1$ である．

しかし $\beta$ はどの $\alpha_n$ とも一致しない．なぜなら $\alpha_n$ と $\beta$ は第 $n$ 位が必ず異なるからである．これは $\alpha_n\ (n=1,\ 2,\ \cdots)$ が$0<x\le 1$ を満たす実数の全体という仮定と矛盾した．

この矛盾は，集合$(0,\ 1]$と自然数の集合との間に一対一対応が存在するかぎり起こる．

よって$0<x\le 1$を満たす実数の集合は可付番でないことが示された．したがって

$$\aleph_0<\vert(0,\ 1]\vert\le \aleph$$

が示された．□

南海　 この背理法を「カントールの対角線論法」という．

さらに次のことが成り立つ．

$$\vert(0,\ 1)\vert=\aleph$$

$\vert(0,\ 1)\vert\le \vert(0,\ 1]\vert$なので

$$\vert(0,\ 1)\vert=\vert(0,\ 1]\vert=\aleph$$

も成り立つ．

拓生　 つまり，区間$(0,\ 1)$と実数全体とのあいだに一対一対応が存在するということですね．

南海　 次のように一対一対応を構成すればよい．

定理 2        開区間$(0,\ 1)$の濃度は，実数の濃度に等しい．つまり $\vert(0,\ 1)\vert=\aleph$である．

■

証明      区間$(0,\ 1)$を区間の列

$$\left(0,\ \dfrac{1}{2} \right],\ \left(\dfrac{1}{2},\ \df... ...c{2^n-1}{2^n},\ \dfrac{2^{n+1}-1}{2^{n+1}} \right],\ \cdots$$

に分ける．

区間 $\left(0,\ \dfrac{1}{2} \right]$は区間$(0,\ 1]$と一対一対応をつけ，

$n\ge 1$に対しては，

$n=2m$なら区間 $\left(\dfrac{2^n-1}{2^n},\ \dfrac{2^{n+1}-1}{2^{n+1}} \right]$と区間$(m,\ m+1]$に一対一対応をつけ，

$n=2m+1$なら区間 $\left(\dfrac{2^n-1}{2^n},\ \dfrac{2^{n+1}-1}{2^{n+1}} \right]$ と区間$(-m-1,\ -m]$に一対一対応をつけることができる．

こうして区間$(0,\ 1)$と実数の間の一対一対応ができる．□

拓生　 0と1の間に，すべての有理数より多くの実数があるのは不思議でもあります．

南海　 よくたいへん多いことを，「ガンジス川の砂より多い」等というが，それでも，ガンジス川の砂の数は有限だ．

人類が地球上に現れ，言葉を覚えて以来，これまでに生きてきたすべての人間が発した単語の総数，といっても有限だ．

拓生　 確かに．地上のすべての人間の細胞の総数，も有限です．それより0と1の間の実数の濃度の方が大きい！

南海　 対角線論法は次のように書くこともできる．

定理1の証明の別表現
区間 $(0,\ 1]$の実数$\alpha$を一つとる．$\alpha$は十進小数で

$$0.a_1a_2a_3\cdots a_n\cdots$$

のように無限小数でただ一通りに表される．

このとき$a_n$を$f(n)$のように関数形で書くと，$f(n)$は自然数の集合$N$から，$N$と0の集合$N\cup \{0\}$への写像になっている．$\alpha$によって，自然数$n$に対し$\alpha$の小数第$n$位の数を対応させる関数が得られる．

区間 $(0,\ 1]$の実数をひとつとれば，$N$から$N\cup \{0\}$への写像$f$で恒等的に0ではないものがひとつ定まる．逆に，$N$から$N\cup \{0\}$への恒等的に0ではない写像$f$があると，それによって区間 $(0,\ 1]$の実数$\alpha$がひとつ定まる． つまり

$$\alpha=\sum_{1}^{\infty}\dfrac{f(n)}{10^n}$$

である．

この対応によって，集合$(0,\ 1]$と自然数から自然数への写像の集合の間に一対一対応ができる．この対応で二つの集合を同じものとみる．

$$(0,\ 1]=\{\ f \ \vert\ f:N\to N\cup \{0\},\ f\ne 0\ \}$$

恒等的に0な写像を数0に対応させて

$$[0,\ 1]=\{\ f \ \vert\ f:N\to N\cup \{0\}\ \}$$

としてもよい．

さて，集合 $\{\ f \ \vert\ f:N\to N\cup \{0\}\}$と自然数の間に一対一対応が存在すると仮定する．

この一対一対応で自然数$k$に対応する写像を$f_k$とおく． これを用いて$N$から$N\cup \{0\}$への写像$g(n)$を次のように定める．

$$g(n)= \left\{ \begin{array}{ll} 1 &(f_n(n) \ne 1)\\ 2 &(f_n(n)=1) \end{array} \right.$$

$g(n)$もまた$N$から$N\cup \{0\}$への写像であるから，ある自然数と対応している． それを$m$とする．つまり

$$g(n)=f_m(n)$$

である．しかしこのとき値$g(m)$に関して

$$g(m)=f_m(m)= \left\{ \begin{array}{ll} 1 &(f_m(m) \ne 1)\\ 2 &(f_m(m)=1) \end{array} \right.$$

と，矛盾である．

ゆえに集合 $\{\ f \ \vert\ f:N\to N\cup \{0\}\}$と自然数の間に一対一対応は存在しない．□

拓生　 $n$番目の関数に$n$を代入して，その値を否定した値で新たな関数を作る，自己言及関数から新たな関数を作るのですね．

南海　 そういうことだ．これは，先の証明を関数形でいいかえただけだが，関数の形で表すことで，次のように発展していく．

次: べき集合の濃度 上: 対角線論法 前: リシャールの逆理