二進法による実数の表示
$\mathbf{R}$ の非可算性を示すための準備として，まず二進法による実数の表示法を復習しておこう．
実数 $x\in[0,1)$ を二進法で表したときの小数第 $n$ 位 $a_n$ は
$a_n=\left\{\begin{array}{ll}0&\mbox{if $\ 2^{n-1}x-\lfloor 2^{n-1}x \rfloor < \dfrac{1}{2}$}\\[1mm]
1&\mbox{if $\ 2^{n-1}x-\lfloor2^{n-1}x\rfloor\ge \dfrac{1}{2}$}
\end{array}\right.$
により与えられる．ただし，$\lfloor\,\cdot\,\rfloor$は床関数である．
$\dfrac{1}{3}$ を二進法で表すと
$\dfrac{1}{3}-\Big\lfloor\dfrac{1}{3}\Big\rfloor=\dfrac{1}{3}<\dfrac{1}{2}$ より $a_1=0$
$\dfrac{1}{3}\cdot 2-\Big\lfloor\dfrac{1}{3}\cdot 2\Big\rfloor=\dfrac{2}{3}\ge \dfrac{1}{2}$ より $a_2=1$
$\dfrac{1}{3}\cdot 2^2-\Big\lfloor\dfrac{1}{3}\cdot 2^2\Big\rfloor=\dfrac{1}{3}<\dfrac{1}{2}$ より $a_3=0$
$\dfrac{1}{3}\cdot 2^3-\Big\lfloor\dfrac{1}{3}\cdot 2^3\Big\rfloor=\dfrac{2}{3}\ge \dfrac{1}{2}$ より $a_4=1$
以下，$a_5=0,\ a_6=1,\ldots$ とわかるから
$\dfrac{1}{3}=0.010101\cdots$
数列の集合
上で見た通り，
実数の二進法表示とは，要するに実数を $0$ と $1$ の数字の並びで表すことであるから，実数と $0$ と $1$ からなる数列は一対一に対応するであろうことが予想される．
すなわち，
$\{\,0,1\,\}^\infty\stackrel{\mathrm{def}}{=}
\big\{\,(a_n)\ \big|\ a_n=0\ \mathrm{or}\ 1\ (n=1,2,\ldots\ )\,\big\}$
と表すとき
$f:\{\,0,1\,\}^\infty\to [0,1]$，
$\displaystyle (a_n)\mapsto \sum_{n=1}^\infty\dfrac{a_n}{2^n}$
という写像によって，$0$ と $1$ からなる数列に実数を対応させることができる．
$a_n=\left\{\begin{array}{ll}0&\mbox{if $n=2m-1$}\\1&\mbox{if $n=2m$}\end{array}\right.\ (m\in\mathbf{N})$
により定まる数列 $(a_n)\in\{\,0,1\,\}^\infty$ はこの $f$ によって
$\displaystyle f(\,(a_n)\,)= \sum_{m=1}^\infty\dfrac{1}{2^{2m}}=\dfrac{1/4}{1-1/4}=\dfrac{1}{3}$
に移される．
この対応によって $\#\{\,0,1\,\}^\infty=\#[0,1]$ と言いたいのだが，この $f$ は(全射ではあるが)単射ではない
詳しく！
例えば
$(a_n)=(1,0,0,0,\ldots )$
$(a'_n)=(0,1,1,1,\ldots )$
の二つは数列としては異なるが，それぞれ
$0.1000\cdots=\dfrac{1}{2}$
$\displaystyle 0.0111\cdots=\sum_{n=2}^\infty\dfrac{1}{2^n}=\dfrac{1}{2}$
と，同じ実数に対応する(すなわち $f((a_n))=f((a'_n))$ となってしまう)．
このようなことは
$\dfrac{1}{2}=0.1=0.0111\cdots$
$\dfrac{3}{4}=0.11=0.10111\cdots$
のように，分母が $2^n$ $(n\in \mathbf{N})$ の形をしている有理数が二通りの小数表示をもつことに起因している．
ので少し調整が必要である．
$\{0,1\}^\infty$ の部分集合で，$1$ を無限個含む数列全体からなる集合を $\{0,1\}_I^\infty$ で表そう：
$\{0,1\}_I^\infty\stackrel{\mathrm{def}}{=}\{\,(a_n)\,|\,\forall N\in\mathbf{N},\ \exists n\ge N,\ a_n=1\,\}$
このとき，上の $f$ の定義域を $\{0,1\}_I^\infty$ に制限した写像をやはり $f$ と表わすことにすると，この場合は
$f:\{\,0,1\,\}_I^\infty\to (0,1]$，
$\displaystyle (a_n)\mapsto \sum_{n=1}^\infty\dfrac{a_n}{2^n}$
が全単射となり(値域が $0$ を含まないことに注意)，従って
$\#\{0,1\}_I^\infty=\#(0,1]$
が成り立つ
詳しく！．
$x\in(0,1]$ を 二進法で
$x=0.a_1a_2a_3\cdots$
と表わすとき，$\dfrac{1}{2}=0.1=0.0111\cdots$ のように二通りで表される場合は，無限小数のほうで表すことに規約しておくと，この表し方は一意的である．
従って，この規約のもとで
$\displaystyle g:(0,1]\to\{\,0,1\,\}_I^\infty\\[1mm]
\hspace{10pt}\displaystyle 0.a_1a_2\cdots\mapsto (a_1,a_2,\ldots\ )$
という写像が定まり，これは全単射であり
$\displaystyle f:\{\,0,1\,\}_I^\infty\to (0,1]\\[1mm]
\hspace{10pt}\displaystyle (a_1,a_2,\ldots\ )\mapsto \sum_{n=1}^\infty\dfrac{a_n}{2^n}$
の逆写像となっている．
さらに
$\#\{0,1\}_I^\infty=\#\{0,1\}^\infty$
ということも成り立つ
証明
まず，$\{0,1\}_I^\infty\subset\{0,1\}^\infty$ なので
$\#\{0,1\}_I^\infty\le \#\{0,1\}^\infty$
また，写像 $f:\{0,1\}^\infty\to \{0,1\}_I^\infty$ を
$a=(a_n)\in\{\,0,1\,\}_I^\infty$ のときは
$f(a)_n=\left\{\begin{array}{ll}a_n&\mbox{if $n=2m-1$}\\0&\mbox{if $n=2m$}\end{array}\right.\quad(m\in\mathbf{N})$
$a=(a_n)\notin\{\,0,1\,\}_I^\infty$ のときは
$f(a)_n=\left\{\begin{array}{ll}0&\mbox{if $n=2m-1$}\\1-a_n&\mbox{if $n=2m$}\end{array}\right.\quad(m=\in\mathbf{N})$
と定めると，これは単射であり
詳しく！
この $f$ によって，例えば $a=(1,1,1,1,\ldots\ )$ のような $1$ が無限回出てくる数列は
$f(a)=(1,0,1,0,1,0,1,0,\ldots\ )$
と，偶数項がすべて $0$ である数列に移され，
$b=(1,1,0,0,0,0,\ldots\ )$ のような $1$ が有限回しか出てこない数列は
$f(b)=(0,0,0,0,0,1,0,1,0,1,0,1,\ldots\ )$
と，奇数項がすべて $0$ である数列に移される．
$f(b)$ には $1$ が無限回出てくることにも注意しよう．
この様子から，$f$ が単射であることを確かめるのは容易であろう．
$\#\{0,1\}^\infty\le \#\{0,1\}_I^\infty$
となる．よってBernsteinの定理より
$\#\{0,1\}_I^\infty= \#\{0,1\}^\infty$
が成り立つ．
ので
$\#\{0,1\}^\infty=\#(0,1]$
が得られた．
前講で見たように，$\#(0,1]=\#\mathbf{R}$ はBernsteinの定理を用いると容易に示すことができるので，本節の結論として
$\#\{\,0,1\,\}^\infty=\#\mathbf{R}$
が言えたことになる．
冪集合
集合 $X$ のすべての部分集合からなる集合を $X$ の
冪集合と呼び，$\mathcal{P}(X)$ と表す．
$X=\{\,a,b,c\,\}$ とすると
$\mathcal{P}(X)=\{\,\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{c,a\},X\,\}$
$X$ 自身も $X$ の部分集合である．
また，空集合 $\emptyset$ は任意の集合の部分集合という規約であった．
空集合 $\emptyset$ の部分集合は $\emptyset$ のみなので
$\mathcal{P}(\emptyset)=\{\,\emptyset\,\}$
となる．
$\mathcal{P}(\emptyset)\neq \emptyset$
であることに注意しよう．
$X$ が有限集合 $X=\{\,x_1,x_2,\ldots,x_N\,\}$ の場合は
$X$ の部分集合は $N$ 個の $0$ または $1$ からなる有限列と一対一に対応する．
すなわち
$\#\{\,0,1\,\}^N=\#\mathcal{P}(X)$
が成り立つ
詳しく!．
例えば，$X=\{\,z_1,x_2,x_3\,\}$ の場合は
$(0,0,0)\mapsto \emptyset$
$(1,0,0)\mapsto \{x_1\}$
$(0,1,0)\mapsto \{x_2\}$
$(0,0,1)\mapsto \{x_3\}$
$(1,1,0)\mapsto \{x_1,x_2\}$
$(0,1,1)\mapsto \{x_2,x_3\}$
$(1,0,1)\mapsto \{x_3,x_1\}$
$(1,1,1)\mapsto X$
と定めると，この写像は全単射であり，確かに
$\#\{\,0,1\,\}^3=\#\mathcal{P}(X)$
となっている．同様に，
$X=\{\,z_1,x_2,\ldots,x_N\,\}$ のとき，写像 $f$ を
$f：\{\,0,1\,\}^N\to\mathcal{P}(X)$
$(a_1,a_2,\ldots,a_N)\mapsto \{\,x_n\ |\ a_n=1\,\}$
により定めると，これが全単射であることは容易に確かめられる．
$X=\mathbf{N}$ の場合も同様に考えて
$\#\{\,0,1\,\}^\infty=\#\mathcal{P}(\mathbf{N})$
となる
詳しく！．
$(a_n)\in\{0,1\}^\infty$ に対して集合
$\{\,n\,|\,a_n=1\,\}\in\mathcal{P}(\mathbf{N})$
を対応させる写像は全単射である．
実際，
$A\in\mathcal{P}(\mathbf{N})$に対して
$a_n=\left\{\begin{array}{ll}1&\mbox{if $n\in A$}\\0&\mbox{if $n\notin A$}\end{array}\right.\quad(n=1,2,\ldots)$
によって定まる数列 $(a_n)\in\{0,1\}^\infty$ を対応させる写像がその逆写像を与える．
従って，前節の結論と合わせて
$\#\{\,0,1\,\}^\infty=\#\mathcal{P}(\mathbf{N})=\#\mathbf{R}$
ということがわかった．
Cantorの定理
集合 $A$，$B$ について，$A$ から $B$ への単射は存在するが全単射は存在しないとき
$\#A < \# B$ (または$\#B > \#A$)
と表す．
Cantorの定理は，空でない任意の集合 $X$ について
$\# X < \#\mathcal{P}(X)$
が成り立つことを主張する
証明．
有限集合の場合，例えば$X=\{\,a,b,c\,\}$ならば
$\mathcal{P}(X)=\{\,\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{b,c\},\{c,a\},X\,\}$
であり
$\# X < \#\mathcal{P}(X)$
が成り立つのは当然と言える．
だからと言って $X$ が無限集合であっても当然だというのは言い過ぎであろう．
実際，Cantorの定理の証明は簡潔ではあるが極めて巧妙なアイデアに依っている．
今となっては「非可算集合」の存在は常識となってしまっているが，
そもそも「数える」とはどういうことなのかを考えることから出発して，ここに到って「数えられない」集合が出現したという事実の重大さを改めて意識しておきたい．
写像 $x\mapsto \{x\}$ が $X$ から $\mathcal{P}(X)$ への単射であることより $\# X\le \#\mathcal{P}(X)$ は明らかである．
そこで，$\# X= \#\mathcal{P}(X)$，すなわち全単射 $f:X\to\mathcal{P}(X)$ が存在すると仮定する．
このとき，$X$の部分集合
$X_0=\{\,x\in X\,|\,x\notin f(x)\,\}$
を考えると，
$f$ は全射であるから $f(x_0)=X_0$ となる $x_0\in X$ が存在する．この $x_0$ について
$x_0\in X_0$ とすると $x_0\in f(x_0)$ より $x_0\notin X_0$ となり矛盾．
$x_0\notin X_0$ としても $x_0\notin f(x_0)$ より $x_0\in X_0$ となり矛盾．
従って，$X$ から $\mathcal{P}(X)$ への全単射は存在しない．
$\mathbf{R}$ と $\mathbf{C}$ の濃度
ここまでの議論で，既に $\mathbf{R}$ の非可算性は示されている．すなわち，前節のCantorの定理により
$\#\mathbf{N} < \#\mathcal{P}(\mathbf{N})=\#\mathbf{R}$
ということがわかった．最後に
$\#\mathbf{R} =\#\mathbf{C}$
であることも見ておこう．
実際，
$(a_n),(b_n)\in\{\,0,1\,\}^\infty$に対して
$c_n=\left\{\begin{array}{ll}a_n&\mbox{if $n=2m-1$}\\b_n&\mbox{if $n=2m$}\end{array}\right.\quad(m\in\mathbf{N})$
により定まる $(c_n)$ を対応させる写像は $\{\,0,1\,\}^\infty\times\{\,0,1\,\}^\infty$ から $\{\,0,1\,\}^\infty$ への全単射を与える．
$(c_n)\in\{\,0,1\,\}^\infty$に対して
$(\ (c_{2n-1})，(c_{2n})\ )\in\{\,0,1\,\}^\infty\times\{\,0,1\,\}^\infty$ を対応させる写像がその逆写像である．
従って
$\#\mathbf{R}^2=\#(\{\,0,1\,\}^\infty\times\{\,0,1\,\}^\infty)=\#\{\,0,1\,\}^\infty=\#\mathbf{R}$
となる．$\#\mathbf{R}^2=\#\mathbf{C}$ は $(x,y)\mapsto x+yi$ の対応により明らかであろう．
同様の議論により
$\#\mathbf{R}^n=\#\mathbf{R}\ (\forall n\in\mathbf{N})$
であることがわかる．