ほぼ数学科の大学生の備忘録。

都内理系大学生が数学/物理等の解説をあげていくブログです。

非加算無限集合

前回、加算非加算無限 - ほぼ数学科の大学生の備忘録。この記事の最後で実数全体の集合\mathbb{R}は非加算無限集合であるという話をしました。
今回は、対角線論法を用いたその証明をしたいと思います。

まず、区間I=(0,1)から\mathbb{R}には全単射が存在します。例えば、
g(x)=tan\left(\cfrac{2x-1}{2} \pi \right)
とすれば、gは全単射です。

従って、自然数全体の集合\mathbb{N}から区間I=(0,1)全単射がないことを示せばよいことになります(\mathbb{N}からI全単射があれば上の全単射と合成することで\mathbb{N}から\mathbb{R}への全単射が作れますし、\mathbb{N}からI全単射がなければ\mathbb{N}から\mathbb{R}全単射があると上の全単射の逆写像と合成することで\mathbb{N}からI全単射が作れてしまい矛盾するからです)。

ここで、\mathbb{N}からI全単射fが存在するとします。このとき、
\displaystyle I=\{a_i\ |\ i \in \mathbb{N},a_i=f(i)\}=\{a_1,a_2,a_3,\cdots \}
と書けます。この各a_iに対して、2進数展開をします。つまり、
\displaystyle a_i=\sum_{j=1}^{\infty} a_{ij}2^{-j}
となるようなa_{ij}を考えます。ここで、各a_{ij}\in {0,1}です。

このa_{ij}に対し、b_i=\lnot a_{ii}とします。但し\lnotはビット反転を表す記号で、0だったものを1に、1だったものを0にします。つまり、
\displaystyle b_i=
\begin{cases}
1\ (a_{ii}=0のとき) \\
0\ (a_{ii}=1のとき)
\end{cases}
となります。ここで、
\displaystyle b=\sum_{i=1}^{\infty} b_i 2^{-i}
とすれば、たしかにb \in Iですが、どのa_iとも2^{-i}の桁の係数が違うので矛盾します。

以上より\mathbb{N}からIには全単射fが存在しなことが分かり、I\mathbb{R}は非加算無限集合であることが示せました。

このような論法(すべての要素から一つずつ取ってきたものを用いる方法)を対角線論法といいます。