【集合】9 カントールの対角線論法～実数が非可算無限集合であることの証明～

こんにちは、これが286本目の記事となったすうじょうです。今日は、初めての大学数学の解説記事です。今回の内容は、集合論よりカントールの対角線論法を解説します。

※この記事は2022/2/13に投稿したものを2022/6/2に再編集と加筆をしています。

この記事は、以下の記事の続きです。

集合の濃度

カントールの対角線論法

前回、非可算無限集合であることを示す方法として、カントールの対角線論法を紹介した。今回は、それについて具体的に説明していく。

対角線論法は、数学における証明方法の一つで、その一部に背理法を用いている。非可算無限集合であることの証明の他にも、停止性判定問題を解くアルゴリズム（どんなチューリングマシンが与えられてもそれが停止することを判定できるチューリングマシン）が存在しないことの証明などに用いられている。

その概要としては、ある対象を集合の対角線成分を用いて定義し、その対象の定義から矛盾を導く。その対象の定義が証明において最も重要な部分である。

ここまで抽象的な話で分かりづらいので、具体例をみるとよい。

実数全体が非可算無限集合である

ここからは、カントールの対角線論法を用いて実数全体が非可算無限集合であることを証明していく。

その前に実数とはどういった数なのか確認する。実数とは、小数(有限小数、無限小数)の形で表せる数である。例えば、$${\sqrt{2}=1.4142…,\dfrac{1}{3}=0.3333…, 0.4=0.3999…, 1=0.9999…}$$のように表せる。

実数全体が非可算無限集合である

[証明]
$${S \subseteq \R}$$である集合$${S=\{x|x \in \R, 0\leq x<1\}}$$を考える．
$${S}$$が可算無限集合であると仮定すると,
集合$${S}$$の要素である0以上1未満のすべての実数を自然数と対応させることができる．
つまり, $${S=\{x_1, x_2, x_3, …\}}$$と書くことができる．
ただし, $${\forall i \in \N, x_i=0.a_{i1}a_{i2}a_{i3}…}$$とする．
ここで, $${y=0.b_1b_2b_3…}$$を次のように定義する．
$${b_k = \begin{cases} 1 & a_{kk}\neq 1 \\ 2 & a_{kk}=1\end{cases}}$$
このとき, $${y}$$は0以上1未満の実数より$${y \in S}$$である．
一方, $${b_k}$$の定義より$${\forall i \in \N, y \neq x_i}$$となるので, $${y \notin S}$$となり, 矛盾である．
したがって,　$${S}$$が可算無限集合であるという仮定が誤りで, $${S}$$は非可算無限集合である．
0以上1未満の実数の集合$${S}$$は$${\R}$$の部分集合であるので, 実数全体の集合$${\R}$$は非可算無限集合である．$${\Box}$$

上の証明を見ても、なかなか理解が難しいと思われるので、説明していく。
例えば、集合$${S}$$として、以下の図17のようなものを考える。

図17:集合Sの例

このとき、$${y}$$の値がどのようになるか考える。$${y}$$の各桁$${b_k}$$は、集合$${S}$$の$${k}$$番目の要素$${x_k}$$の小数点以下$${k}$$桁目が1でないとき1となり、1のとき2となるように定義されている。
今回の例の場合、図18のように集合$${S}$$の各要素の対角線の桁に着目して、$${y}$$が決定される。

図18:集合Sの例の対角線

今回の例の場合、$${a_{11}=0,a_{22}=1,a_{33}=3,a_{44}=1,a_{55}=2,…}$$より、$${b_1=1,b_2=2,b_3=1,b_4=2,b_5=1,…}$$となる。つまり、$${y=0.12121…}$$となる。

この$${y}$$は0以上1未満より集合$${S}$$の要素のはずで、$${y=x_i}$$とする。このとき、 $${b_k}$$の定義によれば、$${x_i}$$の小数点以下$${i}$$桁目$${a_{ii}}$$が1でないとき、$${b_i}$$は1となり、$${a_{ii}}$$が1であるとき、$${b_i}$$は2となる。このように、小数点以下$${i}$$桁目の値を考えたときに$${b_k}$$の定義と矛盾なく値を決定することができない。

証明最後の0以上1未満の実数の集合から実数全体の集合への話は、前回書いた「集合$${A}$$の部分集合に非可算無限集合が存在するならば集合$${A}$$も非可算無限集合となる」という性質を用いている。

※0以上1未満の実数を$${0.a_{i1}a_{i2}a_{i3}…}$$とすることについて
この証明において、$${0 < x < 1}$$や$${0 < x \leq 1}$$とする場合もあるがその場合も問題はない。また、有限小数については、上の実数の説明の例に書いたようにすれば表せる。

※$${b_k}$$の定義について
実数全体が非可算無限集合であることの証明において、$${b_k}$$の定義は、矛盾が導けるようなものならば何でもよい。他に以下のような定義でも証明ができる。
$${b_k = \begin{cases} 2 & a_{kk}\neq 2 \\ 3 & a_{kk}=2\end{cases}}$$
$${b_k = \begin{cases} 1 & a_{kk}は偶数 \\ 2 & a_{kk}は奇数\end{cases}}$$

※実数は数え上げることができないことについて
このことは、証明から明らかになったが具体的に考えてみてもわかる。すべての自然数と対応させるような規則を考えようとする。しかし、実数の中には有限の桁数のものだけでなく、無限に小数点以下が続いていくものまであるので、そのすべてを対応させるような規則を考えることはできない。

演習問題9

問題23 自然数全体の集合$${\N}$$のべき集合$${2^\N}$$が非可算無限集合であることを証明せよ。

[証明]
$${2^\N}$$が可算無限集合であると仮定すると,
集合$${2^\N}$$の要素である自然数の集合を自然数と対応させることができる．
つまり, $${2^\N=\{S_1, S_2, S_3, …\}}$$と書くことができる．
ここで, $${S'=\{i|i \notin S_i\}}$$と定義する．
$${S'}$$は$${\N}$$の部分集合より, $${S' \in 2^\N}$$
よって, $${S'=S_k}$$と書ける．
$${k \in S_k}$$のとき, $${S'}$$の定義より$${k \notin S'}$$であることに矛盾する．$${k \notin S_k}$$のとき, $${S'}$$の定義より$${k \in S'}$$であることに矛盾する．よって, $${S'}$$が$${k}$$を含むかどうかを決定できない．
したがって,　$${2^\N}$$が可算無限集合であるという仮定が誤りで, $${2^\N}$$は非可算無限集合である．$${\Box}$$

※$${S'}$$の定義について、$${S_1}$$に$${1}$$が含まれていれば、$${S'}$$は$${1}$$を含まず、$${1}$$が含まれていなければ、$${S'}$$は$${1}$$を含むというものである。

最後に

今回は、大学数学・集合論の解説記事として、カントールの対角線論法について解説しました。一見、難しそうに見える内容ですが、理解できればそこまで難しくありません。注意しなければいけないポイントは、矛盾が導けるように定義するということです。

ここまでの計9回で集合論の一部について解説しました。ただ、一部といっても基礎としては十分な内容だと思います。このシリーズでは、理解の助けとなるように簡単なレベルの演習問題を付けるとともに、ある程度考えないと解けないような演習問題も付けています。これ以上の内容としては、公理的集合論などがあります。また、集合論は他の数学的分野の基礎となっています。今後も別の大学数学の解説記事を書くつもりです。では。