次: 数学の基礎 上: 対角線論法 前: カントールの対角線論法

べき集合の濃度

南海　 ここで二つの集合$A$と$B$に対し，集合$A$から集合$B$への写像の集合をべき集合といい

$$B^A$$

と書く．

これは次の例で考えれば，自然な記号だ．$A=\{0,\ 1\}$で $B=\{0,\ 1,\ 2,\ \cdots,\ n\ \}$なら，$A$から$B$への写像は0と1の行き先を決めれば決まるので，その組合せだけあり，個数は$n^2$個ある．

有限集合の場合，$A$から$B$への写像の集合は，集合$B$を集合$A$の分だけ組合わせただけあり，その個数は $\left\vert B \right\vert^{\vert A\vert}$個ある．

これをもとに，べき集合を上のように定義した．

したがって，実数の実数べき集合$R^R$とは，実数から実数への写像の集合である．

定理 3        実数の集合$R$とそのべき集合$R^R$の濃度について，不等式

$$\vert R\vert=\aleph<\vert R^R\vert$$

が成立する． ■

証明      実数$c$と定数写像$f(x)=c$を対応させることで$R$は$R^R$の部分集合と一対一の対応がつけられる．したがって

$$\vert R\vert=\aleph\le \vert R^R\vert$$

である．

次に$R$と$R^R$の間に一対一写像は存在しないことを示す．

集合$R$と$R^R$の間に一対一対応が存在すると仮定する．

この一対一対応で実数$r$に対応する写像を$f_r$とおく．ここで$R$から$R$への写像，つまり$R^R$の要素$g(x)$を次のように定める．

$$g(x)=f_x(x)+1$$

$g(x)$もまた$R^R$の要素であるから，ある実数と対応している．それを$s$とする．つまり

$$g(x)=f_s(x)$$

である． しかしこのとき，値$g(s)$に関して，一方で$g(s)=f_s(s)$であるが，一方$g(s)$の定義から$g(s)=f_s(s)+1$となり矛盾である．

ゆえに集合$R$と$R^R$の間に一対一対応は存在しない．□

拓生　 実数なので対角線に並べるということはできないが，しかし，実数と一対一対応があるとして，自己言及するところで矛盾した写像を作るということは，定理1 の証明の別表現と同じです．

南海　 その通りである．

集合$A$に対し，その部分集合の集合(空集合と$A$自身を含む)を$2^A$と書こう．これは$A$から集合$\{0,\ 1\}$への写像の集合の記号$\{0,\ 1\}^A$から来ている．

集合$A$に対し，その部分集合の集合と，$A$から集合$\{0,\ 1\}$への写像の集合との間に一対一の対応が存在する．

つまり，集合$A$の部分集合$S$が一つ与えられると，$A$から集合$\{0,\ 1\}$への写像$f_S$が

$$f_S(x)= \left\{ \begin{array}{ll} 0&x \in S\\ 1&x \not\in S \end{array} \right.$$

で定まる．逆に$A$から集合$\{0,\ 1\}$への写像$f$に対し，$A$の部分集合$S$を

$$S=\{\ x \ \vert\ f(x)=0,\ x \in A\ \}$$

とすればよい．このとき，$x\not\in S$なら$f(x)=1$である．

$A$が$n$個の要素からなる有限集合の場合，部分集合は各要素を含むか含まないかで決まるので，部分集合の個数は$2^n$個ある．つまり有限集合の場合は

$$\vert 2^A\vert=2^{\vert A\vert}$$

が成り立っている．

だから，$A$から集合$\{0,\ 1\}$への写像の集合を，$A$のべき集合といい，$2^A$と記すことにする．

定理 4  

$$\vert A\vert<\vert 2^A\vert$$

である． ■

証明      $A$の要素$a$に対して，$A$から集合$\{0,\ 1\}$への写像$f_a$を

$$f_a(x)= \left\{ \begin{array}{ll} 0&x=a\\ 1&x\not=a \end{array} \right.$$

で定めることで，$A$は$2^A$の部分集合と一対一に対応する． ゆえに

$$\vert A\vert\le \vert 2^A\vert$$

である．次に$A$と$2^A$の間に一対一写像は存在しないことを示す．

集合$A$と$2^A$の間に一対一対応が存在すると仮定する．

この一対一対応で集合$A$の要素$a$に対応する$A$の部分集合を$S_a$とする． $A$の部分集合$T$を次のように定める．

$$T=\{\ t\ \vert\ t \not\in S_t\ \}$$

$T$もまた$A$の部分集合なので，$A$のある要素$u$と対応している．つまり

$$T=S_u$$

である．

しかしこのとき，もし$u\in T$なら$T$の定義から $u\not\in S_u=T$なので矛盾， もし$u\not\in T$，つまり$u$が$T$の補集合の要素なら$T$の定義から$u\in S_u=T$なので矛盾，

いずれも矛盾となる．ゆえに集合$A$と$2^A$の間に一対一対応は存在しない．つまり

$$\vert A\vert<\vert 2^A\vert$$

である．□

南海　 $A$が$N$つまり自然数の集合のとき

$$\aleph_0=\vert N\vert<\vert 2^N\vert$$

となる．

拓生　 定理1から $\aleph_0<\aleph$ですが，$\aleph$と$\vert 2^N\vert$はどちらが大きいのだろう．

南海　

$$\vert 2^N\vert=\aleph$$

だ．

拓生　 $2^N$とは自然数から$\{0,\ 1\}$への写像の集合です．これはつまり$f(n)$が0か1の値をとるような写像なので，一つの写像$f$に対して

$$f(1)=1,\ f(2)=0,\ \cdots$$

のような0と1の列ができる．

あっ．これを

$$0.10\cdots$$

のような，2進小数と考えれば，区間$(0,\ 1]$の小数を2進数で表したものと一対一に対応する．

これで$2^N$と区間$(0,\ 1]$の間の一対一対応ができる．

南海　 その通りである．

カントールは，数直線$R$と平面$R^2$の間に一対一対応があるかという問題にも取り組んだ．おそらくないだろうと見込みを付け，それを証明しようと3年にわたって研究を続ける．その結果，彼が得た結論は一対一対応が存在するというものであった．彼はその証明を伝えたデーデキントへのドイツ語で書かれた書簡の中で、有名な

”Je le vois, mais je ne le crois pas”「私は見る、しかし信じられない」

という言葉をそこだけフランス語で書き残している．

数直線全体と，平面全体の一対一対応は演習とする．ここでは次のことを示そう．

定理 5        平面の領域$D$を

$$0<x\le 1,\ 0<y\le 1$$

とする．このとき区間$(0,\ 1]$と領域$D$の間に一対一対応が存在する． ■

証明      区間$(0,\ 1]$の数を無限小数で表し

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

とする．

これを偶数番目と奇数番目に分けて領域$D$の点

$$(0.a_1a_3a_5\cdots a_{2m-1}\cdots,\ 0.a_2a_4a_6\cdots a_{2m}\cdots)$$

を対応させる．逆に領域$D$の点

$$(0.a_1a_2a_3\cdots,\ 0.b_1b_2b_3\cdots)$$

に対して，区間$(0,\ 1]$の数

$$0.a_1b_1a_2b_2a_3b_3\cdots$$

を対応させる．

これは明らかに区間$(0,\ 1]$と領域$D$のあいだの一対一対応である．□

南海　 ここで大問題が生まれる．

濃度$\aleph_0$と濃度$\aleph$に対し，

$$\aleph_0<\alpha<\aleph$$

となる濃度$\alpha$は存在するか．

拓生　 これまで出てきた，$\aleph_0$より大きい濃度は，すべて$\aleph$かまたはそれより大きいものばかりでした．あいだの濃度があるか，ということですね．

南海　 カントールは，$\aleph_0$の次の濃度は$\aleph$であって，あいだの濃度はないと予想した．これを連続体仮説という．

さらにこれを一般化する．

無限集合$A$に対して，

$$\left\vert A \right\vert<\left\vert B \right\vert<\left\vert 2^A \right\vert$$

となる集合$B$は存在しない．

これは一般連続体仮説と呼ばれている．集合論の深化はこのような大問題を提起した．

それだけではない．次にもう一つの問題が生まれた．「クレタ人の逆理」のような逆理が生じることが発見されたのだ．それがラッセルの逆理といわれる集合論の逆理だ．集合論を土台に数学を考えていくことが20世紀初頭には一般的になっていた． 集合論はそれ自体数学的対象であるが，同時にあらゆる分野で，集合論的に考え，集合を用いて定義し，また証明するようになってきていた．

そこに逆理が発見された．これは数学の危機である！

後半はここから入り，さまざまの対角線論法がゲーデルの対角線論法に流れ込み， そこから新しい世界が開かれていくことを学ぼう．

次: 数学の基礎 上: 対角線論法 前: カントールの対角線論法