非加算無限集合 - ほぼ数学科の大学生の備忘録。

前回、加算非加算無限 - ほぼ数学科の大学生の備忘録。この記事の最後で実数全体の集合 $\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}$ の桁の係数が違うので矛盾します。