非可算集合

非可算集合

これまでの議論を簡単に振り返ると、まず、すべての集合を有限集合と無限集合に分類した上で、無限集合の中でも自然数集合\(\mathbb{N} \)と等しい濃度を持つ集合を可算集合と呼びました。その上で、選択公理を認める場合には、任意の有限集合\(A\)と任意の無限集合\(B\)に対して、\begin{equation*}\left\vert A\right\vert <\left\vert \mathbb{N} \right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つことを示しました。つまり、可算集合は無限集合の中でも最小の濃度を持つ集合です。では、可算集合よりも大きい濃度を持つ無限集合は存在するのでしょうか。つまり、\begin{equation*}
\left\vert \mathbb{N} \right\vert <\left\vert B\right\vert
\end{equation*}を満たす無限集合\(B\)は存在するのでしょうか。

可算集合ではない無限集合を非可算集合（uncountable set）と呼びます。仮に非可算集合が存在するのであれば、可算集合とは異なる濃度を持つ無限集合が存在するということであり、無限どうしの間にも、より大きい無限やより小さい無限というものが存在するということになります。

有界開区間は非可算集合

非可算集合は存在するのでしょうか。以降では、実数集合\(\mathbb{R} \)の部分集合である有界な開区間\begin{equation*}\left( 0,1\right) =\{x\in \mathbb{R} \ |\ 0<x<1\}
\end{equation*}が非可算集合であることを示します。具体的には、\(\left( 0,1\right) \)が無限集合であることを示した上で、\(\left( 0,1\right) \)が可算集合であるものと仮定して矛盾を導きます。

まずは\(\left( 0,1\right) \)が無限集合であることの証明です。それぞれの\(n\in \mathbb{N} \)に対して、以下の実数\begin{equation*}f\left( n\right) =\frac{1}{n+1}
\end{equation*}を定める写像\begin{equation*}
f:\mathbb{N} \rightarrow \left( 0,1\right)
\end{equation*}を定義します。任意の\(n\in \mathbb{N} \)について\(n\geq 1\)であるため、\begin{equation*}0<\frac{1}{n+1}\leq \frac{1}{2}<1
\end{equation*}すなわち、\begin{equation*}
0<f\left( n\right) <1
\end{equation*}であり、\(f\)は\(\mathbb{N} \)から\(\left( 0,1\right) \)への写像として正しく定義されています。さらに、任意の\(m,n\in \mathbb{N} \)について、\begin{eqnarray*}f\left( m\right) =f\left( n\right) &\Leftrightarrow &\frac{1}{m+1}=\frac{1}{n+1}\quad \because f\text{の定義} \\
&\Rightarrow &m+1=n+1 \\
&\Rightarrow &m=n
\end{eqnarray*}が成り立つため\(f\)は単射です。したがって、濃度の大小関係の定義より、\begin{equation*}\left\vert \mathbb{N} \right\vert \leq \left\vert \left( 0,1\right) \right\vert
\end{equation*}を得ます。\(\mathbb{N} \)は可算集合であり、ゆえに無限集合です。したがって\(\left( 0,1\right) \)もまた無限集合であることが明らかになりました。

続いて、\(\left( 0,1\right) \)が可算集合であるものと仮定して矛盾を導きます。言い換えると、全単射\begin{equation*}f:\mathbb{N} \rightarrow \left( 0,1\right)
\end{equation*}が存在するものと仮定して矛盾を導きます。任意の\(n\in \mathbb{N} \)に対して\(f\left( n\right) \)は\(0\)より大きく\(1\)より小さい実数であるため、これは有限小数か無限小数のどちらか一方です。ただし、有限小数の後ろに\(0\)を無限に並べれば有限小数を無限小数と同一視できます。したがって、それぞれの自然数\(n\)に対して\(f\left( n\right) \)は\(0\)より大きく\(1\)より小さい無限小数であるため、それらを、\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\)までの整数を値としてとり得ます。ただし、1つの実数が2通りの十進小数表示を持つ場合があることに注意が必要です。例えば、\begin{eqnarray*}&&0.5000\cdots \\
&&0.4999\cdots
\end{eqnarray*}は異なる小数表示ですが、同じ実数を表します。実際、\begin{equation*}
0.4999\cdots =0.4+\sum_{k=2}^{+\infty }\frac{9}{10^{k}}
\end{equation*}である一方で、\begin{eqnarray*}
0.4999\cdots &=&0.4+9\sum_{k=2}^{+\infty }\frac{1}{10^{k}} \\
&=&0.4+9\cdot \frac{\frac{1}{100}}{1-\frac{1}{10}} \\
&=&0.4+0.1 \\
&=&0.5 \\
&=&0.5000\cdots
\end{eqnarray*}だからです。一般に、有限小数として表される実数は、末尾に\(0\)を無限に並べる表示と、その有限小数の最後の0でない数字を\(1\)だけ減らし、その後に\(9\)を無限に並べる表示の2通りを持ちます。そこで、それぞれの\(n\)について、\(f\left( n\right) \)としては\(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}\not=1) \\
2 & (if\ a_{nn}=1)\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} \)は存在しません。他方で、任意の\(n\in \mathbb{N} \)について\(b_{n}\in \left\{ 1,2\right\} \)であるため\(0<b<1\)すなわち\(b\in\left( 0,1\right) \)が成り立ちます。ゆえに\(f\)は全射ではありませんが、これは\(f\)が全単射であることと矛盾です。したがって、\(\left\vert \left( 0,1\right) \right\vert=\left\vert \mathbb{N} \right\vert \)が成り立たないことが示されました。ちなみに、ここで利用した証明方法をカントールの対角線論法（Cantor’s diagonal argument）と呼びます。

以上の議論より、\(\left(0,1\right) \)が無限集合であり、なおかつ可算集合ではないことが示されました。つまり、\(\left( 0,1\right) \)は非可算集合です。

一般の有界開区間についても同様の主張が成り立ちます。

\(\mathbb{R} \)上の有界開区間\(\left( a,b\right) \)は非可算集合であるため、\begin{equation}\left\vert \mathbb{N} \right\vert \not=\left\vert \left( a,b\right) \right\vert \quad \cdots (1)
\end{equation}が成り立ちます。非可算集合は無限集合であり、可算集合は最小の無限集合であるため、\begin{equation}
\left\vert \mathbb{N} \right\vert \leq \left\vert \left( a,b\right) \right\vert \quad \cdots (2)
\end{equation}が成り立ちます。\(\left(1\right) ,\left( 2\right) \)および濃度の狭義大小関係\(<\)の定義より、\begin{equation*}\left\vert \mathbb{N} \right\vert <\left\vert \left( a,b\right) \right\vert
\end{equation*}が成り立ちます。非可算集合である\(\left( a,b\right) \)の濃度は可算濃度よりも大きいということです。

非可算性の証明：可算であると仮定して矛盾を導く

集合\(A\)が非可算集合であることを示すためには、\(A\)が無限集合であり、なおかつ可算集合ではないことを証明する必要があります。非可算性の証明では、対象となる集合の構造に応じて方法を使い分けます。

非可算性を直接示す最も基本的な方法は、対象となる集合が可算集合であると仮定し、その要素を自然数を用いて列挙した上で、列挙に含まれない要素を構成する方法です。カントールの対角線論法が代表的なものですが、考え方を一般化する以下のようになります。

集合\(A\)が可算集合であるものと仮定すると、全単射\begin{equation*}f:\mathbb{N} \rightarrow A
\end{equation*}が存在します。したがって、\(A\)のすべての要素を、\begin{equation*}f\left( 1\right) ,f\left( 2\right) ,f\left( 3\right) ,\cdots
\end{equation*}と列挙できます。その上で、この列挙に含まれる要素を利用して新たな要素\(a\in A\)を構成します。その上で、\begin{equation*}\forall n\in \mathbb{N} :a\not\in f\left( n\right)
\end{equation*}を示します。すると、\(a\)は\(A\)の要素であるにもかかわらず、列挙されたどの要素とも一致しません。これは\(f\)が全射であることと矛盾します。したがって背理法より\(A\)は可算集合ではありません。

非可算性の証明：既知の非可算集合から単射を構成する

ある集合が非可算であることがすでに分かっている場合には、その集合から対象となる単射を構成することにより、対象集合の非可算性を証明できます。

非可算集合\(A\)を部分集合として集合\(B\)が与えられているものとします。つまり、\begin{equation*}A\subset B
\end{equation*}です。この場合、それぞれの\(a\in A\)に対して、\begin{equation*}f\left( a\right) =a
\end{equation*}を定める包含写像\begin{equation*}
f:A\rightarrow B
\end{equation*}を定義すれば、これは単射であるため、先の命題より\(B\)は非可算集合です。つまり、非可算集合を部分集合として含む集合は非可算集合です。

非可算性の証明：既知の非可算集合への全射を構成する

ある集合が非可算であることがすでに分かっている場合には、対象となる集合からその非可算集合へ全射を構成することにより、対象集合の非可算性を証明できます。

非可算性の証明：非可算集合から高々可算集合を取り除く

非可算集合から有限集合や可算集合を取り除いても、残った集合は非可算集合です。

演習問題