自然数、整数、有理数の濃度

Proposition

Statement

整数の濃度は $\aleph _0$ である.

Proof

$f:\mathbb{N} \rightarrow \mathbb{Z}$
を以下のように定義する.
$1 \mapsto 0$
$2 \mapsto 1$
$3 \mapsto -1$
$4 \mapsto 2$
$5 \mapsto -2$
$\vdots$
$n \mapsto n/2 \quad (n:偶数)$
$n' \mapsto -(n'-1)/2 \quad (n':奇数,n' \gt 1)$
$\vdots$
$f$は全単射となる. (proof of 全射)
$z \in \mathbb{Z}$
(i) $z = 0$の時
$n = 1$とすると$f(1) = 0$
(ii) $z \gt 0$の時
$n = 2z$とすると$f(n) = f(2z) = 2z/2 = z$
(iii) $z \lt 0$の時
$n' = 2(-z) + 1 = -2z + 1$とすると
$f(n') = f(-2z+1)$
$= -((-2z+1) - 1)/2$
$= -(-2z)/2$
$= z$

(proof of 単射)
$f(m) = f(n) \quad m,n \in \mathbb{N}$ と仮定する
(i) $m,n$:偶数
$f(m) = m/2$
$f(n) = n/2$
$\therefore m/2 = n/2$
$\therefore m = n$
(ii) $m,n$:奇数
$f(m) = -(m-1)/2$
$f(n) = -(n-1)/2$
$\therefore -(m-1)/2 = -(n-1)/2$
$\therefore m = n$
(iii) $m$:奇数,$n$:偶数
$m = 2k -1 \quad k \in \mathbb{N}$
$n = 2l \quad l \in \mathbb{N}$
$f(m) = -(m-1)/2 = -(2k - 1 - 1)/2 = -k + 1$
$f(n) = n/2 = 2l/2 = l$
$\therefore -k+1 = l$
$\therefore 1 = k + l$となり矛盾

Proposition

Statement

有理数の濃度は $\aleph _0$ である.

Proof

$f:\mathbb{N} \rightarrow \mathbb{Q}$
を以下のように定義する.
$1 \mapsto 1/1$
$2 \mapsto 1/2$
$3 \mapsto 2/1$
$4 \mapsto 1/3$
$5 \mapsto 2/2$
$6 \mapsto 3/1$