解答例 1

$n$ 個の元からなる $\mathbb{N}$ の部分集合の全体を $\mathcal{N}_n$ とする.

まず, $\mathcal{N}_0=\{\emptyset\}$ は有限集合であり, $\mathcal{N}_1=\{ \{i\} \mid i\in\mathbb{N} \}$ は明らかに $\mathbb{N}$ と対等であるから可算集合である. 一般に, $n\geq 2$ のとき, $$ \mathcal{N}_n = \{ \{i_1, i_2, \ldots, i_n\} \mid i_1, i_2, \ldots, i_n\in\mathbb{N},\, i_1<i_2<\cdots<i_n \} $$ と表せる. 写像 $$ \mathcal{N}_1\longrightarrow \mathcal{N}_n,\quad \{i\} \longmapsto \{i, i+1, i+2, \ldots, i+(n-1)\} $$ および \begin{align*} & \mathcal{N}_n \longrightarrow \prod_{i=1}^n\mathbb{N},\quad \{i_1, i_2, \ldots, i_n\} \longmapsto (i_1, i_2, \ldots, i_n) \\ & (\mbox{ただし, $i_1<i_2<\ldots<i_n$ とする}) \end{align*} はともに単射であるから, $$ \lvert\mathbb{N}\rvert = \lvert\mathcal{N}_1\rvert \leq \lvert \mathcal{N}_n\rvert \leq \left\lvert\prod_{i=1}^n\mathbb{N}\right\rvert = \lvert\mathbb{N}\rvert. $$ よって, Bernstein の定理より, $\lvert\mathcal{N}_n\rvert = \lvert\mathbb{N}\rvert$ となる. すなわち, $\mathcal{N}_n$ は可算集合である.

したがって, $\mathbb{N}$ の部分集合の全体からなる集合 $\displaystyle \bigcup_{n=0}^{\infty}\mathcal{N}_n$ は可算集合である.

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