カントールの定理の証明と対角線論法

まず，$A$ の要素 $a$ が与えられたときに，集合 $\{a\}$ を対応させる写像を考えると，これは単射である，よって $|A|\leq |2^A|$

あとは，$|A|\neq |2^A|$ であること，つまり $A$ と $2^A$ の間に全単射が存在しないことを言えばよい。これを背理法で証明する。全単射 $f$ が存在すると仮定する。

このとき，$a\not\in f(a)$ となる $A$ の要素 $a$ を全て集めた集合を $B$ とする。ここで，$f$ は全射なので，行き先が $B$ となるものが存在する。つまり，ある $b\in A$ が存在して，$f(b)=B$ となる。

• $b\in B$ のとき，$B$ の定義より $b\not\in f(b)$ である。$f(b)=B$ と合わせて $b\not\in B$ となり矛盾。

• $b\not \in B$ のとき，$B$ の定義より $b\in f(b)$ である。$f(b)=B$ と合わせて $b\in B$ となり矛盾。

全単射 $f$ が存在すると仮定する。

各行，各列がそれぞれ $A$ の要素に対応した（無限のサイズの）行列を考える。行が $a$，列が $a'$ に対応する部分には $a'\in f(a)$ なら $1$ を格納し，そうでないなら $0$ を格納する。

対角成分の $0$ と $1$ とを反転させたものを並べたベクトル $\overrightarrow{B}$ に対応する集合を $B$ とする。すると，$\overrightarrow{B}$ は行列のどの行とも一致しないので，いかなる $a\in A$ に対しても $f(a)\neq B$ である。

一方，背理法の仮定より，$f$ は $A$ から $2^A$ への全単射なので $f(b)=B$ となる $b\in A$ が存在しなくてはならない。

これは矛盾である。よって，背理法により全単射が存在しないことが証明された。

$\mathbb{N}<|[0,1)|$ を示す。背理法で示す。

つまり「正の整数全体」から「$0$ 以上 $1$ 未満の実数全体」への全単射 $f$ が存在すると仮定する。

$f(n)$ の小数点以下 $n$ 桁目の数を $a_n$ とおく。

$b_n$ を $$b_n = \begin{cases} a_n + 1 &(a_n \neq 9)\\ 0 &(a_n = 9) \end{cases}$$ とおく。つまり，$a_n$ の次に来る数の1の位とする。（例：$a_n = 4$ なら $b_n = 5$）

実数 $x$ を $$x = 0. b_1 b_2 b_3 \cdots$$ とすると $x \in [0,1)$ であるため，ある自然数 $m$ があって $f(m) = x$ となる。

$a_m$ の定義を振り返ると，$x$ の小数点以下 $m$ 桁目は $a_m$ になるはずである。

一方，$x$ の定め方より $x$ の小数点以下 $m$ 桁目は $b_m$ である。

$b_m$ の定義より $a_m \neq b_m$ である。

こうして矛盾が生じる。ゆえに全単射 $f$ は存在せず $|\mathbb{N}| < |[0,1)$ である。