教材一覧
CARDINALITY OF SET

可算集合

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

可算濃度

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

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

無限集合どうしの濃度は等しくなるとは限りません。具体例として、実数空間\(\mathbb{R} \)上の有界な開区間\begin{equation*}\left( 0,1\right) =\left\{ x\in \mathbb{R} \ |\ 0<x<1\right\}
\end{equation*}と、すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,\cdots \right\}
\end{equation*}の間には全単射\(f:\left( 0,1\right)\rightarrow \mathbb{N} \)が存在しないことをカントールの対角線論法を用いて証明しました。つまり、\begin{equation*}\left\vert \mathbb{N} \right\vert \not=\left\vert \left( 0,1\right) \right\vert
\end{equation*}が成り立つということです。

以上の例が示唆するように、無限集合の濃度は1種類だけであるとは限りません。以上を踏まえた上で、無限集合の濃度に関する議論の出発点として、まずは\(\mathbb{N} \)の濃度\(\left\vert \mathbb{N} \right\vert \)について考察します。これを可算濃度(countable potency)や可付番濃度(enumerable potency)などと呼びます。\(\mathbb{N} \)は無限集合であり、そこには無限個の自然数が含まれるため、可算濃度\(\left\vert \mathbb{N} \right\vert \)を自然数として表すことはできません。可算濃度\(\left\vert \mathbb{N} \right\vert \)を表す記号として、\begin{equation*}\aleph _{0}
\end{equation*}を採用することがあります。\(\aleph _{0}=\left\vert \mathbb{N} \right\vert \)です。\(\aleph \)はヘブライ文字のアレフで、\(\aleph _{0}\)をアレフゼロと読みます。繰り返しになりますが、可算濃度を自然数として表すことはできないため\(\aleph _{0}\)は自然数ではありません。

 

可算集合

集合\(A\)の濃度が可算濃度\(\aleph _{0}\)であるとき、すなわち、\begin{equation*}\left\vert A\right\vert =\aleph _{0}
\end{equation*}が成り立つ場合には、\(A\)を可算集合(countable set)や可算無限集合(countably infinite set)、可付番集合(enumerable set)などと呼びます。定義より、\(A\)が可算集合であることは全単射\begin{equation*}f:\mathbb{N} \rightarrow A
\end{equation*}が存在することを意味します。

可算集合\(A\)に対しては全単射\(f:\mathbb{N} \rightarrow A\)が存在するため、\begin{eqnarray*}f\left( 1\right) &=&a_{1}\in A \\
f\left( 2\right) &=&a_{2}\in A \\
&&\vdots \\
f\left( n\right) &=&a_{n}\in A \\
&&\vdots
\end{eqnarray*}という形で\(A\)のそれぞれの要素に対して自然数を1つずつ付番できるため、\begin{equation*}A=\left\{ a_{1},a_{2},\cdots ,a_{n},\cdots \right\}
\end{equation*}と表現できます。その逆もまた成立します。

命題(可算集合という名称の由来)
集合\(A\)のすべての要素を\begin{equation*}a_{1},a_{2},\cdots ,a_{n},\cdots
\end{equation*}という形で順番に並べられることは、\(A\)が可算集合であるための必要十分条件である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

無限集合\(A\)のすべての要素を\begin{equation*}a_{1},a_{2},\cdots ,a_{n},\cdots
\end{equation*}という形で並べられない場合、上の命題より、\(A\)は可算集合ではありません。先にカントールの対角線論法を用いて\(\left( 0,1\right) \)が可算集合でないことを示しましたが、その際のポイントは、\(\left( 0,1\right) \)の要素であるすべての実数(無限小数)を上のように順番に並べることができないことを示すことでした。

可算集合\(A\)には無限個の要素が含まれるため、すべての要素を数え尽くすことはできませ。しかし上の命題より、可算集合\(A\)の要素を\(1\)番目から順番に数えることはできます。可算集合や可付番集合という名称の由来はここにあります。以下では代表的な可算集合を紹介します。

 

非負の整数集合・非正の整数集合は可算

すべての自然数からなる集合\(\mathbb{N} \)に\(0\)を加えた集合、すなわちすべての非負な整数からなる集合を、\begin{equation*}\mathbb{Z} _{+}=\mathbb{N} \cup \left\{ 0\right\} =\left\{ 0,1,2,\cdots \right\} \end{equation*}と表記します。これは可算集合です。有限集合\(A\)に関しては、\(a\not\in A\)を満たす要素\(a\)を加えた集合\(A\cup \{a\}\)をとると、\(A\)の要素の個数は\(A\cup \{a\}\)の要素の個数よりも少ないため、両者の濃度は等しくなりません。このような発想の延長上で考えると\(\mathbb{N} \)と\(\mathbb{Z} _{+}\)は異なる濃度を持っていると思いがちですが、実際には、両者は等しい濃度を持つということです。有限集合においては起こり得ない不思議な現象です。

命題(非負の整数集合は可算集合)
すべての非負の整数からなる集合\(\mathbb{Z} _{+}\)は可算集合である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

以上の事実を利用すると、すべての非正な整数からなる集合\begin{equation*}\mathbb{Z} _{-}=\mathbb{Z} \backslash \mathbb{Z} _{+}=\left\{ 0,-1,-2,\cdots \right\}
\end{equation*}が可算であることを容易に示すことができます。

命題(非正の整数集合は可算集合)
すべての非正の整数からなる集合\(\mathbb{Z} _{-}\)は可算集合である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

非負の偶数集合・非負の奇数集合は可算

すべての非負の偶数からなる集合を\(E\)で表記します。つまり、\begin{equation*}E=\left\{ 2n\ |\ n\in \mathbb{N} \right\} =\left\{ 2,4,6,\cdots \right\}
\end{equation*}です。これは可算集合です。

命題(非負の偶数集合は可算)
すべての非負の偶数からなる集合\(E\)は可算集合である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

すべての非負の奇数からなる集合を\(O\)で表記します。つまり、\begin{equation*}O=\left\{ 2n-1\ |\ n\in \mathbb{N} \right\} =\left\{ 1,3,5,\cdots \right\}
\end{equation*}です。これもまた可算集合です。

命題(非負の奇数集合は可算)
すべての非負の奇数からなる集合\(O\)は可算集合である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

整数集合は可算

すべての整数からなる集合\(\mathbb{Z} \)もまた可算集合です。つまり、\(\mathbb{N} \)から\(\mathbb{Z} \)への全単射が存在します。実際、\(\mathbb{N} \)は\(E\)と\(O\)に分割可能であり、\(\mathbb{Z} \)は\(\mathbb{N} \)と\(\mathbb{Z} _{-}\)に分割可能ですが、先に示したようにこれらはいずれも可算であるため、\(E\)から\(\mathbb{N} \)への全単射と\(O\)から\(\mathbb{Z} _{-}\)への全単射が存在します。これらの全単射を用いれば\(\mathbb{N} \)から\(\mathbb{Z} \)への全単射を容易に作ることができます。

命題(整数集合は可算)

すべての整数からなる集合\(\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} \rightarrow \mathbb{N} \)について考えると、これは全単射になります。

命題(自然数集合の直積は可算)
自然数集合の直積\(\mathbb{N} \times \mathbb{N} \)は可算集合である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

演習問題

問題(可算集合)
以下の集合\begin{equation*}
A=\left\{ \frac{\sqrt{2}}{n}\ |\ n\in \mathbb{N} \right\}
\end{equation*}が可算であることを示してください。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(可算集合)
以下の集合\begin{equation*}
A=\left\{ \cdots ,\frac{1}{8},\frac{1}{4},\frac{1}{2},1,2,4,8,\cdots
\right\}
\end{equation*}が可算であることを示してください。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(可算集合)
以下の集合\begin{equation*}
\left\{ 0,1\right\} \times \mathbb{N} \end{equation*}が可算であることを示してください。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

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

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

事象

標本空間と事象

起こり得るすべての結果は分かっていても、その中のどの結果が実際に起こるかはランダムネスによって支配されている実験や観察を試行と呼びます。試行によって起こり得る個々の結果を標本点と呼び、すべての標本点からなる集合を標本集合と呼びます。試行によって起こり得る現象は標本空間の部分集合として定式化され、それを事象と呼びます。

有限集合

有限集合

有限個の要素を持つ集合を有限集合と呼びます。有限集合の濃度を有限濃度と呼びます。有限集合どうしの濃度が等しいことと、それらの集合に含まれる要素の個数が等しいことは必要十分です。

標本空間

非可算集合

可算集合ではない無限集合を非可算集合と呼びます。非可算集合の具体例を提示します。

可算集合

可算型確率空間

標本空間が可算集合であるとき、その任意の部分集合を事象として考察対象に含めることができます。その上で、標本空間のベキ集合上に集合関数を定義した上で、それが確率論の公理と呼ばれる性質を満たすものと定めます。こうして得られる概念を可算確率空間と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録