大学数学

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

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

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

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

なぜなら、もし X が無限集合ならば、相異なる元 x_1,x_2, \dots , x_n , \dots を無限に取ることができて、写像 f \colon \mathbb{N} \rightarrow Xf(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=mm の値が小さい順に並べて、それぞれに自然数が対応しているような写像が 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_ih(i,n) = f_i(n), i \in I,n \in \mathbb{N} と定めると、各 f_i が全射であることから、h は全射である。

したがって、 \mathbf{card}( I \times \mathbb{N}) \geq \mathbf{card}(\bigcup_{ i \in I } A_i) となるから、示された。 □


この事実を使って、いくつか集合を見ていきましょう。


◇Ex.Set&Top.2.16.2

整数全体の集合 \mathbb{Z}可算であることは既に見ました。

有理数全体の集合  \mathbb{Q}可算になります。

写像 f \colon \mathbb{Z} \times  \mathbb{N}^{+} \rightarrow \mathbb{Q}f((m,n))=m/n, m \in \mathbb{Z},n \in \mathbb{N}^{+} で定めると、f は全射です。

一方、Prop.Set&Top.2.16.1.(ⅰ)より、 \mathbb{Z} \times  \mathbb{N}^{+} は可算集合なので、 \mathbb{Q} も可算集合となります。



◇Ex.Set&Top.2.16.3

整数係数の方程式

a_nx^{n}+a_{n-1}x^{n-1}+ \dots + a_0 =0, a_i \in \mathbb{Z},i=0,1, \dots ,n

の解となる複素数のことを代数的数と言います。解とならない複素数のことを超越数と言います。

代数的数全体の集合が可算集合であることを示しましょう。

まず、整数係数の多項式全体の集合を \mathbb{Z}[x] と表し、n 次多項式全体の集合を \mathb{Z}_{n} [x] と表します。

各次数 n について、整数の組 a_i \in \mathbb{Z},i=0,1, \dots ,n を定めれば整数係数の方程式は定まりますから、

写像 p \colon \mathbb{Z}^{n+1} \rightarrow  \mathb{Z}_{n} [x]p( (a_0,a_1, \dots,a_n)) = a_nx^{n}+a_{n-1}x^{n-1}+ \dots + a_0 と定めれば、p は全射です。

Prop.Set&Top.2.16.1.(ⅰ)より、 \mathbb{Z}^{n+1} は可算集合ですから、\mathb{Z}_{n} [x] は可算集合となります。

したがって、Prop.Set&Top.2.16.1.(ⅱ)より、

\mathbb{Z}[x] = \bigcup_{n=0}^{ \infty } \mathb{Z}_{n} [x]

は可算集合です。

ところで、代数的数全体の集合は、次のように表すことができます。

\bigcup_{f(x) \in \mathbb{Z}[x]} \{ x \in \mathbb{C} \mid f(x)=0 \}

さて、n 次方程式は高々 n 個の解しかもたないことが知られています。(代数学の基本定理

すなわち、 \{ x \in \mathbb{C} \mid f(x)=0 \} は高々 n 個の元しか持たない有限集合です。

したがって、 \mathbb{Z}[x] が可算であることより、再びProp.Set&Top.2.16.1.(ⅱ)から、代数的数全体の集合

\bigcup_{f(x) \in \mathbb{Z}[x]} \{ x \in \mathbb{C} \mid f(x)=0 \}

は可算となります。


 

集合 その17へ>

<集合 その15へ

記事一覧(大学数学)に戻る

関連記事

  1. 大学数学

    写像.8 単射の性質

    単射の性質単射であることを同値な条件で言い替えることで特徴付け…

  2. 大学数学

    写像.10 積集合の普遍性

    積集合の普遍性積集合とは何かを集合と元を用いて具体的に記述する…

  3. 大学数学

    集合.13 同値類と集合の分割

    同値類同値関係 \( \sim \) で結ばれているということ…

  4. 大学数学

    論理記号.3 すべての、~が存在する

    \( \forall \) すべての、任意の集合 \( X \…

  5. 大学数学

    集合.7 積集合(n個の場合)

    積集合( \(n \) 個の場合)例えば、\( x,y \in…

  6. 大学数学

    論理記号.4 ~がただ一つ存在する、定義

    \( \exists ! \) ~がただ一つ存在する\( \e…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    集合.4 共通集合と和集合(n個の場合)
  2. 大学数学

    集合.2 部分集合、べき集合
  3. 大学数学

    集合.6 共通集合と和集合(一般の場合)
  4. 大学数学

    数の構成.2 自然数.2 自然数の加法.1 和の定義と数学的帰納法
  5. 大学数学

    集合.13 同値類と集合の分割
PAGE TOP
error: Content is protected !!