集合の濃度と可算無限・非可算無限

図のように一対一対応を構成できる。

より正確には，整数全体の集合から正の整数全体の集合への関数 $f$ を以下のように定める：

$$f(x)= \begin{cases} 2x+1 & (x\geq 0)\\ -2{x} & (x < 0) \end{cases}$$

例えば $f(-2)=4$，$f(-1)=2$，$f(0)=1$，$f(1)=3$，$f(2)=5$ などとなり，$f$ は $\mathbb{Z}$ から $\mathbb{N}$ への全単射である。

正の有理数全体の集合 $\mathbb{Q}_+$ と $\mathbb{N}$ の濃度が等しいことを言えばよい。

正の有理数 $\dfrac{q}{p}$ を $p+q$ を小さい順に並べて既約分数のみ残して番号を振っていけば，$\mathbb{Q}_+$ から $\mathbb{N}$ への全単射が構成できる：

$$\begin{aligned} &f \left( \frac{1}{1} \right) =1,\: f \left( \frac{1}{2} \right) =2,\: f \left( \frac{2}{1} \right) =3,\: f \left( \frac{1}{3} \right) =4,\:\\ &f \left( \frac{3}{1} \right) =5,\: f \left( \frac{1}{4} \right) =6,\: f \left( \frac{2}{3} \right) =7, \cdots \end{aligned}$$

全単射 $f(x)$ を以下のように構成できる。

• 基本的には $f(x)=x$
• $x=1$ なら $f(1) = 0$
• $x=\dfrac{1}{n}\:(n=2,\dots)$ なら $f(x)=\dfrac{1}{n-1}$
  つまり，$\cdots \to \dfrac{1}{4} \to \dfrac{1}{3} \to \dfrac{1}{2} \to 1 \to 0$ とうつす

$f(x) = \tan \left( \pi x - \dfrac{\pi}{2} \right)$ と定義すると $f : (0,1) \to \mathbb{R}$ である。

$g(x) = \dfrac{1}{\pi} \arctan x + \dfrac{1}{2}$ が逆写像となるため，$f$ は全単射である。

例7より $|2^{\mathbb{N}}| = |\mathbb{R}|$ を示せばよい。

例5，6より $|\mathbb{R}| = |[0,1)|$ であるため，$|2^{\mathbb{N}}| = |[0,1)|$ を示そう。

$A \in 2^{\mathbb{N}}$ に対して $$f(A) = \sum_{n \in A} \dfrac{1}{2^n}$$ と定める。

例えば $A = \{ 2,3,5,7,8 \}$ ならば $f(A) = \dfrac{107}{256}$ になる。$A = \emptyset$ であれば $f(A) = 0$ である。

小数の2進数展開を考えれば $f$ は全単射である。よって $|2^{\mathbb{N}}| = |[0,1)| = |\mathbb{R}|$ となる。