可算集合と濃度

自然数の集合 ℕ と1対1に対応している集合は，ℕ と「同じ個数の元」を持つと考えても良いと思われますが，無限集合の場合は「元をすべて数え上げるということはできない」．ここで登場するのが「濃度」という概念です．

1対1対応と濃度

定義 1 1対1対応

集合 M から集合 N への写像 φ で，次の(1), (2) の性質を満たすものが存在するとき，M, N は1対1対応しているという

a, a^′ ∈ M で a ≠ a^′ ならば φ(a) ≠ φ(a^′)
任意の b̃ ∈ N に対して，ある ã ∈ M が存在して，φ(ã) = b̃

定義 2 濃度

M, N は1対1対応しているとき，M と N は同じ濃度をもつという．

カントールの対関数の全単射性の証明より，自然数の対 (m, n) 全体の作る集合は ℕ と1対1対応している = 同じ濃度であることがわかります．

これを一般的な定理に拡張すると，

M, N を可算集合とすると，直積集合 M × N も可算集合である

ということになります．ただし，可算集合 A_i について Π_i = 1^∞A_i は可算集合とはなりません，

定義 3 可算

自然数の集合 ℕ と同じ濃度を持つ集合を，可算集合と呼ぶ．この可算集合の濃度を 𝔑₀ と表す．

例 1 偶数と奇数の集合

偶数の自然数の全体の集合を E₀ としたとき，写像 f : ℕ → E₀ を

f(n) = 2n

とすると，f は全単射になります．このとき，E₀ ⊂ ℕ であるが，

|E₀| = |ℕ|

という有限集合ではありえない性質が成立します．

また，奇数の自然数の全体の集合を E₁ としたとき，写像 g : ℕ → E₁ を

g(n) = 2(n − 1) + 1

とすると，g も全単射となります．

例 2 整数の集合と可算集合

整数の集合 ℤ について，写像 φ : ℕ → ℤ を

$$ \begin{align} \varphi(n) = \left\{\begin{array}{c} \frac{n}{2} & ( n \in \mathbb E_0 )\\ -\frac{n-1}{2} & ( n \in \mathbb E_1) \end{array}\right. \end{align} $$

とすると，φ は全単射になります．

可算集合の部分集合と無限集合

定理 1

M を可算集合とする，S ⊂ M が無限集合であるとすると，S は可算集合である

Proof

M は可算集合であるので，M は

M = {a₁, a₂, a₃, ⋯, a_n, ⋯}

と表すことができます．S の元で，この並び方の最初に現れるものを a_i₁ とすると，

S = {a_i₁, a_i₂, a_i₃, ⋯, a_{i_n}, ⋯}

となり，また，S は無限集合なのでこの系列が途中で止まることはありません．写像 f : ℕ → S を

f(n) = a_{i_n}

とすると，f は1対1写像となるので，S は可算集合であることがわかります．

例 3 素数集合と可算集合

素数が無限にあることは，背理法を用いると示しやすいです，素数が有限個しかないとして，その総数を n とすると素数全体の集合 ℙ は

ℙ = {2, 3, 5, ⋯, p_n}

このとき自然数 q を

q = 2 ⋅ 3 ⋅ ⋯p_n + 1

は q はどんな素数でも割り切れないものになってしまうので，素数となりますが，これは素数の総数 n という仮定と矛盾．つまり，素数は無限に存在します．

素数集合は

ℙ ⊂ ℕ

であるので，素数集合は可算集合となります．

References

カントールの対関数の全単射性の証明