すべての自然数からなる集合と等しい濃度を持つ集合を可算集合や可付番集合と呼びます。可算集合には無限個の要素が含まれるため、すべての要素を数え尽くすことはできませんが、要素を1番目から順番に数えることはできます。

可算濃度

復習になりますが、有限集合の濃度は集合に含まれる要素の個数と一致します。有限集合に含まれる要素の個数をすべて数え上げることは原理上可能であるため、有限集合の濃度は必ず 1 つの自然数として定まります。したがって、有限集合どうしの濃度は、自然数の大小として簡単に比較できます。

集合の濃度について復習する 有限集合について復習する

一方、無限集合には無限個の要素が含まれるため、要素をすべて数え尽くすことはできません。したがって、無限集合どうしの濃度は、自然数の大小として比較できません。ただ、2 つの無限集合\(X,Y\)が与えられたとき、\(X\)と\(Y\)の間に全単射が存在するかどうかを調べることはできるため、\(X\)と\(Y\)の濃度が等しいか否かを調べることはできます。では、無限集合どうしを比較したときに、より大きい濃度や、より少ない濃度というものが存在するのでしょうか。言い換えると、より大きい無限や、より小さい無限というものは存在するのでしょうか。

このような問題に取り組む前に、ベンチマークとして、すべての自然数からなる集合\(\mathbb{N} \)に含まれる要素の個数を表す濃度について考えます。\(\mathbb{N} \)は無限集合であり、そこには無限個の自然数が含まれるため、その濃度を自然数として表すことはできません。そこで、\(\mathbb{N} \)の濃度を、\begin{equation*}
\aleph _{0}=\#\mathbb{N} \end{equation*}という記号で表します。\(\aleph \)はヘブライ文字のアレフで、\(\aleph _{0}\)をアレフゼロと読みます。\(\aleph _{0}\)は\(\mathbb{N} \)の濃度を表す記号であり、そのような濃度を可算濃度(countable potency)や可付番濃度(enumerable potency)などと呼びます。

 

可算集合

集合\(X\)の濃度が可算濃度\(\aleph _{0}\)であるとき、\(X\)を可算集合(countable set)や可付番集合(enumerable set)などと呼びます。可算濃度の定義より、集合\(X\)が可算集合であることは、\(\mathbb{N} \)から\(X\)への全単射\(f:\mathbb{N} \rightarrow X\)が存在すること、すなわち\(\#X=\#\mathbb{N} \)が成り立つことを意味します。

可算集合\(X\)に対しては全単射\(f:\mathbb{N} \rightarrow X\)が存在するため、\begin{eqnarray*}
f\left( 1\right) &=&x_{1}\in X \\
f\left( 2\right) &=&x_{2}\in X \\
&&\vdots \\
f\left( n\right) &=&x_{n}\in X \\
&&\vdots
\end{eqnarray*}という形で\(X\)のそれぞれの要素に対して自然数を 1 つずつ付番できるため、\begin{equation*}
X=\{x_{1},x_{2},\cdots ,x_{n},\cdots \}
\end{equation*}と表現できます。可算集合\(X\)には無限個の要素が含まれるため、すべての要素を数え尽くすことはできませんが、\(X\)の要素を\(1\)番目から順番に数えることはできるというわけです。可算集合や可付番集合という名称の由来はここにあります。

例(自然数にゼロを加えた集合)
すべての自然数からなる集合\(\mathbb{N} \)に\(0\)を加えた集合を、\begin{equation*}\mathbb{N}_{0}=\mathbb{N} \cup \{0\}
\end{equation*}という記号で表します。それぞれの自然数\(x\in \mathbb{N}\)に対して、\begin{equation*}
f\left( x\right) =x-1\in \mathbb{N}_{0}
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow \mathbb{N}_{0}\)は全単射であるため(演習問題にします)、\(\#\mathbb{N} _{0}=\#\mathbb{N} \)が成り立ちます。有限集合\(X\)に関しては、それにある要素\(x\)を加えた集合\(X\cup \{x\}\)を考えると、\(X\)の要素の個数は\(X\cup \{x\}\)の要素の個数よりも少ないため、両者の濃度は等しくありません。このような発想の延長上で考えると\(\mathbb{N} \)と\(\mathbb{N} _{0}\)は異なる濃度を持っていると思いがちですが、実際には、両者は等しい濃度を持ちます。有限集合においては起こり得ない不思議な現象です。
例(偶数集合)
すべての偶数からなる集合\begin{equation*}
E=\{2x\ |\ x\in \mathbb{N}\}
\end{equation*}は可算集合です。実際、それぞれの自然数\(x\in \mathbb{N}\)に対して、\begin{equation*}
f\left( x\right) =2x\in E
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow E\)は全単射であるため(演習問題にします)、\(\#E=\#\mathbb{N} \)が成り立ちます。
例(奇数集合)
すべての奇数からなる集合\begin{equation*}
O=\{2x-1\ |\ x\in \mathbb{N}\}
\end{equation*}は可算集合です。実際、それぞれの自然数\(x\in \mathbb{N}\)に対して、\begin{equation*}
f\left( x\right) =2x-1\in O
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow O\)は全単射であるため(演習問題にします)、\(\#O=\#\mathbb{N} \)が成り立ちます。
例(整数集合)
すべての整数からなる集合\(\mathbb{Z}\)は可算集合です。証明の方針は以下の通りです。目標は\(\mathbb{N} \)から\(\mathbb{Z}\)への全単射\(f:\mathbb{N} \rightarrow \mathbb{Z} \)が存在することを示すことです。\(f\)の定義域\(\mathbb{N} \)は偶数集合\(E\)と奇数集合\(O\)に分割されます。また、\(f\)の終集合\(\mathbb{Z}\)は自然数集合\(\mathbb{N} =\{1,2,3,\cdots \}\)と自然数ではない整数からなる集合\(\mathbb{Z}\backslash \mathbb{N}=\{0,-1,-2,\cdots \}\)に分割されます。そこで、それぞれの偶数\(x\in E\)に対して、\begin{equation*}
g\left( x\right) =\frac{x}{2}\in \mathbb{N}\end{equation*}を定める写像\(g:E\rightarrow \mathbb{N}\)と、それぞれの奇数\(x\in O\)に対して、\begin{equation*}
h\left( x\right) =\frac{1-x}{2}\in \mathbb{Z} \backslash \mathbb{N}\end{equation*}を定める写像\(h:O\rightarrow \mathbb{Z} \backslash \mathbb{N}\)について考えると、これらはともに全単射です(演習問題にします)。したがって、それぞれの自然数\(x\in \mathbb{N}\)に対して、\begin{equation*}
f\left( x\right) =\left\{
\begin{array}{ll}
g\left( x\right) \in \mathbb{N}& \left( if\ x\in E\right) \\
h\left( x\right) \in \mathbb{Z} \backslash \mathbb{N}& \left( if\ x\in O\right)
\end{array}\right.
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow \mathbb{Z} \)について考えれば、これは全単射になります。
例(自然数集合の直積)
自然数集合\(\mathbb{N} \)の直積\begin{equation*}\mathbb{N}\times \mathbb{N}=\{\left( x,y\right) \ |\ x\in \mathbb{N},\ y\in \mathbb{N}\}
\end{equation*}は可算集合です。証明の方針は以下の通りです。目標は\(\mathbb{N} \times \mathbb{N}\)から\(\mathbb{N} \)への全単射が存在することを示すことです。そこで、すべての自然数を以下のように並べます。

それぞれの順序対\(\left( x,y\right) \in \mathbb{N}\times \mathbb{N}\)に対して、表中の上から\(x\)行目、左から\(y\)列目に位置する自然数\(f\left( x,y\right) \in \mathbb{N}\)を定める規則\(f\)について考えると、これは\(\mathbb{N} \times \mathbb{N}\)から\(\mathbb{N}\)への全単射です(演習問題にします)。

 

高々可算集合

有限集合と可算集合を総称して高々可算集合(at most countable set)と呼びます。つまり、\(X\)が高々可算集合であることは、その濃度\(\#X\)が何らかの自然数\(n\)であるか、可算濃度\(\aleph _{0}\)であるかのどちらか一方であることを意味します。

次回は可算集合の部分集合について学びます。

次へ進む 質問・コメントを読む 演習問題(プレミアム会員限定)

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するにはログインが必要です。
ログイン

アカウント
ログイン