可算集合と濃度

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

1対1対応と濃度

Definition 1 1対1対応

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

\(a, a^\prime \in M\) で \(a\neq a^\prime\) ならば \(\varphi(a)\neq \varphi(a^\prime)\)
任意の \(\tilde b \in N\) に対して，ある \(\tilde a\in M\) が存在して，\(\varphi(\tilde a) = \tilde b\)

Definition 2 濃度

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

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

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

\(M, N\) を可算集合とすると，直積集合 \(M\times N\) も可算集合である

ということになります．ただし，可算集合 \(A_i\) について \(\displaystyle\Pi_{i=1}^\infty A_i\) は可算集合とはなりません，

Definition 3 可算

自然数の集合 \(\mathbb N\) と同じ濃度を持つ集合を，可算集合と呼ぶ．この可算集合の濃度を \(\mathfrak{N}_0\) と表す．

Example 1 偶数と奇数の集合

偶数の自然数の全体の集合を \(\pmb{E}_0\) としたとき，写像 \(f: \mathbb N \to \pmb{E}_0\) を

\[ f(n) = 2n \]

とすると，\(f\) は全単射になります．このとき，\(\pmb{E}_0 \subset \mathbb N\) であるが，

\[ |\pmb{E}_0| = |\mathbb N| \]

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

また，奇数の自然数の全体の集合を \(\pmb{E}_1\) としたとき，写像 \(g: \mathbb N \to \pmb{E}_1\) を

\[ g(n) = 2(n - 1) + 1 \]

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

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

整数の集合 \(\mathbb Z\) について，写像 \(\varphi: \mathbb N \to \mathbb Z\) を

\[ \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} \]

とすると，\(\varphi\) は全単射になります．

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

Theorem 1

\(M\) を可算集合とする，\(S\subset M\) が無限集合であるとすると，\(S\) は可算集合である

Proof

\(M\) は可算集合であるので，\(M\) は

\[ M = \{a_1, a_2, a_3, \cdots, a_n, \cdots\} \]

と表すことができます．\(S\) の元で，この並び方の最初に現れるものを \(a_{i_1}\) とすると，

\[ S = \{a_{i_1}, a_{i_2}, a_{i_3}, \cdots, a_{i_n}, \cdots\} \]

となり，また，\(S\) は無限集合なのでこの系列が途中で止まることはありません．写像 \(f: \mathbb N\to S\) を

\[ f(n) = a_{i_n} \]

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

Example 3 素数集合と可算集合

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

\[ \mathbb P = \{2, 3, 5, \cdots, p_n\} \]

このとき自然数 \(q\) を

\[ q = 2 \cdot 3 \cdot \cdots p_n + 1 \]

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

素数集合は

\[ \mathbb P \subset \mathbb N \]

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

References

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