カントールの定理とカントールのパラドクス

カントールの定理

これまでの議論を振り返ると、まず、すべての集合を有限集合と無限集合に分類した上で、無限集合の中でも自然数集合\(\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*}という関係が成り立つことを示しました。つまり、可算集合は無限集合の中でも最小の濃度を持つ集合です。さらに、実数集合\(\mathbb{R} \)が非可算集合であることを示した上で、\(\mathbb{R} \)と等しい濃度を持つ集合を連続体と呼び、\begin{equation*}\left\vert \mathbb{N} \right\vert <\left\vert \mathbb{R} \right\vert
\end{equation*}が成り立つことを確認しました。では、可算集合や連続体とは異なる無限集合は存在するのでしょうか。言い換えると、連続体とは異なる非可算集合は存在するのでしょうか。この問いへの答えを得るために以下の命題を示します。これをカントールの定理（Cantor’s Theorem）と呼びます。

カントールのパラドクス

あらゆる集合を要素として持つ集合族をラッセル集合（Russel set）と呼びます。すでに明らかにしたように、ラッセル集合が存在することを認める場合にはラッセルのパラドクス（Russell’s paradox）と呼ばれる問題が生じます。

カントールの定理から矛盾を導くこともできます。具体的には、ラッセル集合\(\mathfrak{A}\)が存在するものと仮定した上で、そのベキ集合\(2^{\mathfrak{A}}\)をとります。ベキ集合の要素は集合であるため、その要素\(A\in 2^{\mathfrak{A}}\)を任意に選んだとき、\(A\)は何らかの集合であるため、ラッセル集合の定義より\(A\in \mathfrak{A}\)が成り立ちます。したがって、\begin{equation*}2^{\mathfrak{A}}\subset \mathfrak{A}
\end{equation*}が成り立ちます。すると、濃度の大小関係\(\leq \)の性質より、\begin{equation}\left\vert 2^{\mathfrak{A}}\right\vert \leq \left\vert \mathfrak{A}\right\vert \quad \cdots (1)
\end{equation}が成り立ちます。一方、カントールの定理は任意の集合に対して成立しますが、ラッセル集合\(\mathfrak{A}\)は集合であることから、\begin{equation}\left\vert \mathfrak{A}\right\vert <\left\vert 2^{\mathfrak{A}}\right\vert
\quad \cdots (2)
\end{equation}が成り立ちます。\(\left(1\right) \)と\(\left( 2\right) \)がともに成り立つことは矛盾です。これをカントールのパラドクス（Cantor’s paradox）と呼びます。

ラッセルのパラドクスについて解説した際に言及したように、このような問題を回避するためには公理主義的アプローチのもとで集合論を構成することになります。

可算集合や連続体とは異なる無限集合

以降の議論では、見やすさを考慮して集合\(A\)のベキ集合\(2^{A}\)を、\begin{equation*}\mathcal{P}\left( A\right)
\end{equation*}で表記します。このとき、カントールの定理は、\begin{equation*}
\left\vert A\right\vert <\left\vert \mathcal{P}\left( A\right) \right\vert
\end{equation*}と表現されます。さて、カントールの定理は任意の集合\(A\)に対して成立するため、無限集合に対しても同様の主張が成立します。具体例として、無限集合の中でも最小の濃度を持つ可算集合\(\mathbb{N} \)に対しても、カントールの定理より、\begin{equation*}\left\vert \mathbb{N} \right\vert <\left\vert \mathcal{P}\left( \mathbb{N} \right) \right\vert
\end{equation*}が成り立ちます。繰り返しになりますが、カントールの定理は任意の集合に対して成立するため、ベキ集合\(\mathcal{P}\left( \mathbb{N} \right) \)に対しても、\begin{equation*}\left\vert \mathcal{P}\left( \mathbb{N} \right) \right\vert <\left\vert \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) \right\vert
\end{equation*}が成り立ちます。濃度の狭義大小関係\(<\)が推移性を満たすため、このとき、\begin{equation*}\left\vert \mathbb{N} \right\vert <\left\vert \mathcal{P}\left( \mathbb{N} \right) \right\vert <\left\vert \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) \right\vert
\end{equation*}が成り立ちます。同様の議論を繰り返すことにより、\begin{equation*}
\left\vert \mathbb{N} \right\vert <\left\vert \mathcal{P}\left( \mathbb{N} \right) \right\vert <\left\vert \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) \right\vert <\left\vert \mathcal{P}\left( \mathcal{P}\left(
\mathcal{P}\left( \mathbb{N} \right) \right) \right) \right\vert <\left\vert \mathcal{P}\left( \mathcal{P}\left( \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) \right) \right) \right\vert <\cdots
\end{equation*}を導くことができます。以上の事実は、\begin{equation*}\mathbb{N} ,\ \mathcal{P}\left( \mathbb{N} \right) ,\ \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) ,\ \mathcal{P}\left( \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) \right) ,\ \mathcal{P}\left( \mathcal{P}\left( \mathcal{P}\left( \mathcal{P}\left( \mathbb{N} \right) \right) \right) \right) ,\ \cdots
\end{equation*}がいずれも異なる濃度を持つ無限集合であることを意味します。つまり、異なる大きさの無限濃度をいくらでも作ることができるということです。したがって、可算濃度や連続体濃度とは異なる無限濃度が存在することが明らかになりました。

カントールの定理は、いくらでも大きい無限濃度が存在することも主張します。実際、無限集合\(A\)を任意に選んだとき、カントールの定理より、\begin{equation*}\left\vert A\right\vert <\left\vert \mathcal{P}\left( A\right) \right\vert
\end{equation*}が成り立ちますが、これは\(A\)よりも大きい濃度を持つ無限集合\(\mathcal{P}\left( A\right) \)が存在することを意味するからです。

演習問題