可算濃度
有限濃度を持つ集合を有限集合と呼び、有限集合ではない集合を無限集合と呼びました。有限集合の濃度は集合に含まれる要素の個数と一致します。有限集合に含まれる要素の個数をすべて数え上げることは原理上可能であるため、有限集合の濃度は必ず1つの自然数として定まります。したがって、有限集合どうしの濃度は自然数の大小として簡単に比較できます。
一方、無限集合には無限個の要素が含まれるため、その要素をすべて数え尽くすことはできません。したがって、無限集合どうしの濃度を自然数の大小として比較できません。ただ、2つの無限集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在するか調べることはできるため、\(A\)と\(B\)の濃度が等しいかどうかを調べることはできます。では、無限集合どうしを比較したときに、より大きい濃度や、より少ない濃度というものが存在するのでしょうか。言い換えると、より大きい無限や、より小さい無限というものは存在するのでしょうか。無限集合どうしの濃度は等しくなるとは限りません。以下の例より明らかです。
\end{equation*}と、すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,\cdots \right\}
\end{equation*}について考えます。これらはともに無限集合です。しかし、全単射\(f:\mathbb{N} \rightarrow (0,1)\)は存在しません。このことを示すために、全単射\(f:\mathbb{N} \rightarrow (0,1)\)が存在するものと仮定して矛盾を導きます。仮定より、任意の自然数\(n\in \mathbb{N} \)に対して\(f\left( n\right) \in \mathbb{R} \)は実数であるため、これは有限小数か無限小数のどちらか一方です。ただし、有限小数の後ろに\(0\)を無限に並べれば有限小数を無限小数と同一視できます。したがって、それぞれの自然数\(n\)に対して\(f\left( n\right) \)は無限小数になるため、それらを、\begin{align*}f(1)& =0.a_{11}a_{12}\cdots a_{1m}\cdots \\
f(2)& =0.a_{21}a_{22}\cdots a_{2m}\cdots \\
& \vdots \\
f(n)& =0.a_{n1}a_{n2}\cdots a_{nm}\cdots \\
& \vdots
\end{align*}と表現します。ただし、\(a_{nm}\)は無限小数\(f\left(n\right) \)の小数第\(m\)位の数を表しており、これは\(0\)から\(9\)までの整数を値としてとり得ます。以上を踏まえた上で、以下のような無限小数\begin{equation*}b=0.b_{1}b_{2}\cdots b_{n}\cdots
\end{equation*}を考えます。ただし、\(b\)の小数点以下の数\(b_{1},b_{2},\cdots ,b_{n},\cdots \)を、\begin{equation*}b_{n}=\left\{
\begin{array}{cc}
1 & (if\ a_{nn}=0) \\
0 & (if\ a_{nn}\not=0)\end{array}\right.
\end{equation*}と定めます。定義より\(b_{1}\not=a_{11}\)であるため\(b\not=f\left( 1\right) \)です。また、\(b_{2}\not=a_{22}\)であるため\(b\not=f\left(2\right) \)です。一般に、\(b_{n}\not=a_{nn}\)であるため\(b\not=f\left(n\right) \)であるため、\(b=f\left(n\right) \)を満たす\(n\in \mathbb{N} \)は存在しません。一方、定義より\(b\in \left( 0,1\right) \)であるため\(f\)は全射ではありません。これは\(f\)が全単射であることと矛盾します。したがって、\(\left\vert \left( 0,1\right)\right\vert =\left\vert \mathbb{N} \right\vert \)が成り立たないこと、すなわち、\begin{equation*}\left\vert \left( 0,1\right) \right\vert \not=\left\vert \mathbb{N} \right\vert
\end{equation*}であることが示されました。ここで利用した証明方法をカントールの対角線論法（Cantor’s diagonal argument）と呼びます。
以上の例が示唆するように、無限集合の濃度は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）もしくは可付番集合（enumerableset）などと呼びます。定義より、\(A\)が可算集合であることは全単射\begin{equation*}f:\mathbb{N} \rightarrow A
\end{equation*}が存在することを意味します。
全単射\(f:\mathbb{N} \rightarrow A\)が存在することと逆写像\(f^{-1}:A\rightarrow \mathbb{N} \)が存在することは必要十分であるとともに、この場合には\(f^{-1}\)は全単射になります。したがって、\(A\)が可算集合であることを、全単射\begin{equation*}f:A\rightarrow \mathbb{N} \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*}と表現できます。その逆もまた成立します。
\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=\left\{ x_{1}x_{2}x_{3}\cdots \ |\ \forall n\in \mathbb{N} :x_{n}\in \left\{ \text{あ},\text{い},\text{う},\text{え},\text{お},\cdots ,\text{ん}\right\} \right\}
\end{equation*}が与えられているものとします。この集合\(A\)に属するすべての文字列を辞書式順序にもとづいて1列に並べることができるため、先の命題より、\(A\)は可算集合です。つまり、\begin{equation*}\left\vert A\right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立ちます。
非負の整数集合・非正の整数集合は可算
すべての自然数からなる集合\(\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} _{+}\)は異なる濃度を持っていると思いがちですが、実際には、両者は等しい濃度を持つということです。有限集合においては起こり得ない不思議な現象です。
\end{equation*}が成り立つ。
以上の事実を利用すると、すべての非正な整数からなる集合\begin{equation*}\mathbb{Z} _{-}=\mathbb{Z} \backslash \mathbb{Z} _{+}=\left\{ 0,-1,-2,\cdots \right\}
\end{equation*}が可算であることを容易に示すことができます。
\end{equation*}が成り立つ。
非負の偶数集合・非負の奇数集合は可算
すべての非負の偶数からなる集合を\(E\)で表記します。つまり、\begin{equation*}E=\left\{ 2n\ |\ n\in \mathbb{N} \right\} =\left\{ 2,4,6,\cdots \right\}
\end{equation*}です。これは可算集合です。
\end{equation*}が成り立つ。
すべての非負の奇数からなる集合を\(O\)で表記します。つまり、\begin{equation*}O=\left\{ 2n-1\ |\ n\in \mathbb{N} \right\} =\left\{ 1,3,5,\cdots \right\}
\end{equation*}です。これもまた可算集合です。
\end{equation*}が成り立つ。
整数集合は可算
すべての整数からなる集合\(\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} \)は可算集合である。つまり、\begin{equation*}\left\vert \mathbb{Z} \right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つ。
演習問題
A=\left\{ \frac{\sqrt{2}}{n}\ |\ n\in \mathbb{N} \right\}
\end{equation*}が可算であることを示してください。
A=\left\{ \cdots ,\frac{1}{8},\frac{1}{4},\frac{1}{2},1,2,4,8,\cdots \right\}
\end{equation*}が可算であることを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】