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

まず，$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$ が存在すると仮定して矛盾を示す。

「各 $n$ について $f(n)$ の小数第 $n$ 位が偶数なら $1$，奇数なら $2$ としてできる実数」を $x$ とする。例えば，

• $f(1)=0.123\cdots$
• $f(2)=0.345\cdots$
• $f(3)=0.789\cdots$
• $\vdots$

のように，$f(1)$ から順番に無限小数の形で並べて（→補足），対角成分 $1,4,9$ の偶奇を見て $x=0.212\cdots$ とする。これはすべての $f(n)$ と異なるので $f$ は全射にならない！