解答例 1

対角線論法による証明.

$\mathbb{N}$ を自然数全体の集合とする. $0$ は自然数に含まれるものとする.

$\mathbb{R}$ が可算集合であると仮定する. $\mathbb{R}$ の開区間 $(0, 1)$ が $\mathbb{R}$ に集合として対等であることを用いると, $(0, 1)$ も可算集合である. したがって, 全単射 $f:\mathbb{N}\rightarrow (0, 1)$ が存在する. \begin{align*} f(0) &= 0.a_{00}a_{01}a_{02}\cdots \\ f(1) &= 0.a_{10}a_{11}a_{12}\cdots \\ f(2) &= 0.a_{20}a_{21}a_{22}\cdots \\ & \vdots \end{align*} のように, 各実数 $f(n)$ は $10$ 進数による無限小数で表すことができる. $a_{ij}$ は $0$ から $9$ までの整数である. ただし, 有限小数については, 例えば $$ 0.2 = 0.1999\cdots $$ のように $9$ が無限に続く無限小数で表すものとする. こうして, すべての $f(n)$ は無限小数によって一意的に表される.

各 $n\in\mathbb{N}$ に対して, $$ b_n = \begin{cases} 1, & \mbox{$a_{nn}$ が偶数のとき} \\ 2, & \mbox{$a_{nn}$ が奇数のとき} \end{cases} $$ とおくと, $1$ つの無限小数 $$ b = 0.b_0b_1b_2\cdots $$ が定まる. $b\in (0, 1)$ であり, 写像 $f$ は全射であるから, ある $n\in\mathbb{N}$ が存在して, $b=a(n)$ となる. 一方, 各 $n=0$, $1$, $2$, $\ldots$ に対して, $a(n)$ と $b$ とは小数第 $n$ 位の数が等しくないので, $a(n)\neq b$. これは矛盾である.

解答例 2

$\mathbb{N}$ を自然数全体の集合とし, $\mathfrak{P}(\mathbb{N})$ を $\mathbb{N}$ の冪集合とする. 集合の濃度について, 不等式 $$ \lvert\mathbb{N}\rvert < \lvert\mathfrak{P}(\mathbb{N})\rvert = \lvert\mathbb{R}\rvert $$ が成り立つ. ゆえに, $\mathbb{R}$ は可算集合ではない.

最終更新日：2011年11月02日