集合.17　集合の濃度.2　可算集合

ホーム
大学数学, 集合と位相
集合.17　集合の濃度.2　可算集合

2018.06.21

どこまでが高々可算集合なのか？

自然数全体の集合 $\mathbb{N}$ の濃度を $\aleph_0$ と表し、濃度が $\aleph_0$ 以下の集合を高々可算集合と言うのでした。

可算の濃度 $\aleph_0$ は、実は最小の無限の濃度です。

なぜなら、もし $X$ が無限集合ならば、相異なる元 $x_1,x_2, \dots , x_n , \dots$ を無限に取ることができて、写像 $f \colon \mathbb{N} \rightarrow X$ を $f(n)= x_n, n \in \mathbb{N}$ で定めれば、 $f$ は単射となるので、

$\aleph_0 = \mathbf{card}(\mathbb{N}) \leq \mathbf{card}(X)$

となるからです。

では、果たしてどこまで大きな集合が高々可算集合となるのでしょうか。

まずは一般的事実を示し、さらに例を見ていきましょう。

高々可算集合に関する一般的事実

次が成り立ちます。

◆Prop.Set&Top.2.16.1

(ⅰ) $A_1,A_2, \dots , A_n$ を高々可算集合とする。このとき、 $A_1 \times A_2 \times \dots \times A_n$ は高々可算集合である。
(ⅱ) $I$ は高々可算集合であり、 $(A_i)_{i \in I }$ は高々可算集合の族とする。このとき、 $\bigcup_{ i \in I } A_i$ は高々可算集合である。

■Prf.

(ⅰ)

数学的帰納法より、 $n=2$ の場合に示せば十分である。
（一般の場合は、 $A_1 \times A_2 \times \dots \times A_n = (A_1 \times A_2 \times \dots A_{n-1}) \times A_n$ と見て、 $n=2$ の場合の結果を適用すれば示せる）

高々可算集合の定義より、 $A_1, A_2$ から $\mathbb{N}$ への単射 $f_i \colon A_i \rightarrow \mathbb{N},i=1,2$ が存在する。
そこで、次の写像

$f_1 \times f_2 \colon A_1 \times A_2 \rightarrow \mathbb{N}^2$
$f_1 \times f_2 (( a_1,a_2))=( f_1(a_1),f_2(a_2))$
$a_i \in A_i, i=1,2$

は単射である。

したがって、 $\mathbf{card}( A_1 \times A_2) \leq \mathbf{card}(\mathbb{N}^{2})$ であるから、 $\mathbb{N}^2$ が可算集合であることを示せばよい。

ここに、次のような写像 $g \colon \mathbb{N} \rightarrow \mathbb{N}^2$ を考える。

$g(0) = (0,0),g(1)=(1,0),g(2)=(0,1),g(3)=(2,0),g(4)=(1,1),g(5)=(0,2), \dots$

図式すると以下のような対応である。

$0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 7 \rightarrow 8 \rightarrow \cdots$
$(0,0) \rightarrow (1,0) \rightarrow (0,1) \rightarrow (2,0) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (3,0) \rightarrow (2,1) \rightarrow \cdots$

すなわち、 $\mathbb{N}^2$ の元を $(p,q), p+q=m$ で $m$ の値が小さい順に並べて、それぞれに自然数が対応しているような写像が $g$ である。 $g$ は全単射となる。

したがって、 $\mathbf{card}(\mathbb{N}) = \mathbf{card}(\mathbb{N}^{2})$ であるから、示された。

Rem.

$g$ をきちんと式で表すと、

$g( \frac{(p+q)(p+q+1)}{2} + q +1 )=(p,q)$ となるような写像である。

考え方は、 $a+b = i$ となる $(a,b)$ が $(i,0),(i-1,1), \dots , (0,i)$ の $i +1$ 個あるので、 $g$ を定義する際の $\mathbb{N}^2$ の元で、 $(0,p+q-1)$ が何番目に来るかを考えれば、

$\sum_{i=0}^{p+q-1} (i+1) = \frac{(p+q)(p+q+1)}{2}$

番目に来るから、 $g(\frac{(p+q)(p+q+1)}{2})=(0,p+q-1)$

$(p,q)$ は並び順で $(0,p+q-1)$ の $q+1$ 個後になるので、このように定義される。

さて、一般の $n \in \mathbb{N}$ に対して $g(n)$ を求める。

$p+q=m \in \mathbb{N}$ とすると、 $\frac{(p+q)(p+q+1)}{2} + q +1 =n$ のとき、 $\frac{m(m+1)}{2} + q +1 =n$ である。

ここで、 $\frac{m(m+1)}{2} \leq n < \frac{(m+1)(m+2)}{2}$ となるような自然数 $m$ を求めると、

$\frac{-3+ \sqrt{8n+1}}{2} < m \leq \frac{-3+ \sqrt{8n+1}}{2}+1$

この区間の幅は $1$ なので、この不等式を満たす自然数 $m$ はただ一つ存在する。その自然数を $m_n$ として、 $\frac{m(m+1)}{2} + q +1 =n$ に代入して、

$q= n- \frac{m_n(m_n+1)}{2} -1$

$p+q =m_n$ より、

$p= \frac{(m_n+1)(m_n+2)}{2} - n$

よって、

$g(n) =(\frac{(m_n+1)(m_n+2)}{2} - n,n- \frac{m_n(m_n+1)}{2} -1)$
ただし、 $m_n$ は $\frac{-3+ \sqrt{8n+1}}{2} < m_n \leq \frac{-3+ \sqrt{8n+1}}{2}+1$ を満たすただ一つの自然数

(ⅱ)

(ⅰ) の結果より、 $I \times \mathbb{N}$ は高々可算集合である。ここで、各 $A_i$ は高々可算集合であるから、全射 $f_i \colon \mathbb{N} \rightarrow A_i$ が存在する。

写像 $h \colon I \times \mathbb{N} \rightarrow \bigcup_{ i \in I } A_i$ を $h(i,n) = f_i(n), i \in I,n \in \mathbb{N}$ と定めると、各 $f_i$ が全射であることから、 $h$ は全射である。