非可算集合

非可算集合

これまでの議論を簡単に振り返ると、まず、すべての集合を有限集合と無限集合に分類した上で、無限集合の中でもすべての自然数からなる集合\(\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) \)が非可算集合であることが示されたことになります。

実数空間\(\mathbb{R} \)上の有界な開区間\begin{equation*}\left( 0,1\right) =\left\{ x\in \mathbb{R} \ |\ 0<x<1\right\}
\end{equation*}は無限集合ですが、これが可算集合であるものと仮定して、つまり全単射\(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）と呼びます。

\(\mathbb{R} \)上の有界開区間\(\left( 0,1\right) \)は非可算集合であるため、\begin{equation}\left\vert \mathbb{N} \right\vert \not=\left\vert \left( 0,1\right) \right\vert \quad \cdots (1)
\end{equation}が成り立ちます。非可算集合は無限集合であり、可算集合は最小の無限集合であるため、\begin{equation}
\left\vert \mathbb{N} \right\vert \leq \left\vert \left( 0,1\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( 0,1\right) \right\vert
\end{equation*}が成り立ちます。非可算集合である\(\left( 0,1\right) \)の濃度は可算濃度よりも大きいということです。

演習問題