高々可算集合

有限濃度と可算濃度の大小関係

前節では、自然数集合\(\mathbb{N} \)と等しい濃度を持つ集合を可算集合と呼びました。可算集合は無限集合ですが、そのすべての要素を自然数によって順番に付番できるという意味で、最も基本的な無限集合です。一方、有限集合も、その要素を自然数によって付番できます。ただし、有限集合の場合には自然数集合の一部分だけを使えば十分です。このように、有限集合と可算集合は「要素を自然数によって管理できる」という共通の性質を持っています。本節では、有限集合と可算集合をまとめて高々可算集合と呼びます。その準備として、有限濃度と可算濃度の大小関係を確認し、選択公理のもとで可算濃度が最小の無限濃度であることを示します。さらに、高々可算集合を、自然数集合との間の単射や全射を用いて特徴づけます。

有限集合\(A\)を任意に選んだとき、それに対して何らかの非負の整数\(n\in \mathbb{Z} _{+}\)が存在して、\begin{equation}\left\vert A\right\vert =\left\vert \mathbb{N} _{n}\right\vert \quad \cdots (1)
\end{equation}が成り立ちます。ただし、\begin{equation*}\mathbb{N} _{n}=\left\{
\begin{array}{cc}
\phi & \left( if\ n=0\right) \\
\left\{ 1,2,\cdots ,n\right\} & \left( if\ n\geq 1\right)
\end{array}\right.
\end{equation*}です。\(\mathbb{N} _{n}\subset \mathbb{N} \)であるため、濃度の大小関係\(\leq \)の性質より、\begin{equation}\left\vert \mathbb{N} _{n}\right\vert \leq \left\vert \mathbb{N} \right\vert \quad \cdots (2)
\end{equation}を得ます。さらに、\(\mathbb{N} _{n}\)は有限集合である一方で\(\mathbb{N} \)は無限集合であるため、\begin{equation}\left\vert \mathbb{N} _{n}\right\vert \not=\left\vert \mathbb{N} \right\vert \quad \cdots (3)
\end{equation}を得ます。\(\left( 2\right) ,\left( 3\right) \)および集合の濃度の狭義大小関係\(<\)の定義より、\begin{equation*}\left\vert \mathbb{N} _{n}\right\vert <\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つため、これと\(\left( 1\right) \)より、\begin{equation*}\left\vert A\right\vert <\left\vert \mathbb{N} \right\vert
\end{equation*}を得ます。任意の有限集合について同様の議論が成り立ちます。つまり、可算濃度は任意の有限濃度よりも大きいということです。

可算濃度は最小の無限濃度

可算濃度は任意の有限濃度よりも大きいことが明らかになりました。では、有限濃度よりも大きく可算濃度よりも小さい無限濃度は存在するのでしょうか。つまり、任意の有限集合\(A\)に対して、\begin{equation*}\left\vert A\right\vert <\left\vert B\right\vert <\left\vert \mathbb{N} \right\vert
\end{equation*}を満たす無限集合\(B\)は存在するのでしょうか。以下で順番に考えます。

まず、選択公理を認める場合、任意の無限集合が可算集合を部分集合として持つことを保証できます。

任意の無限集合\(A\)に対して、\begin{equation*}B\subset A
\end{equation*}を満たす可算集合\(B\)が存在することが明らかになりました。すると、濃度の大小関係\(\leq \)の性質より、\begin{equation}\left\vert B\right\vert \leq \left\vert A\right\vert \quad \cdots (1)
\end{equation}が成り立ちます。\(B\)は可算集合であるため、\begin{equation}\left\vert B\right\vert =\left\vert \mathbb{N} \right\vert \quad \cdots (2)
\end{equation}です。\(\left( 1\right) ,\left( 2\right) \)より、\begin{equation*}\left\vert \mathbb{N} \right\vert \leq \left\vert A\right\vert
\end{equation*}を得ます。任意の無限集合に関して同様の議論が成立するため、任意の無限集合の濃度は可算濃度以上であること、逆に言えば、可算濃度は最小の無限濃度であることが明らかになりました。

高々可算集合

これまでの議論を振り返ります。まず、任意の有限集合\(A\)に対して、\begin{equation}\left\vert A\right\vert <\left\vert \mathbb{N} \right\vert \quad \cdots (1)
\end{equation}が成り立つことが明らかになりました。また、任意の無限集合\(B\)に対して、\begin{equation}\left\vert \mathbb{N} \right\vert \leq \left\vert B\right\vert \quad \cdots (2)
\end{equation}が成り立つことも明らかになりました。\(\left( 1\right) ,\left( 2\right) \)より、任意の有限集合\(A\)と任意の無限集合\(B\)に対して、\begin{equation*}\left\vert A\right\vert <\left\vert \mathbb{N} \right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立ちます。

以上の命題より、有限濃度よりも大きく可算濃度よりも小さい無限濃度は存在しないことが明らかになりました。このような事情を踏まえた上で、有限集合と可算集合の総称として高々可算集合（at most countable set）という用語を使う場合もあります。つまり、集合\(A\)が高々可算集合であることとは、その濃度\(\left\vert A\right\vert \)が何らかの非負の整数\(n\)であるか可算濃度\(\left\vert \mathbb{N} \right\vert \)であるかのどちらか一方であるということです。ただし、「可算集合」という用語を高々可算集合の意味で使う場合もあるため、どちらの意味で使われているかは文脈から判断する必要があります。本稿では可算濃度を持つ集合を「可算集合」と呼ぶとともに、可算集合と有限集合の総称として「高々可算集合」という用語を利用します。

写像を用いた高々可算集合の特徴づけ

空集合は有限集合であるため高々可算です。非空集合については、それが高々可算であることを写像を用いて以下のように表現できます。

先の命題では集合\(A\)が非空である状況を想定しましたが、空集合についても同様の主張は成り立つのでしょうか。つまり、空集合\(\phi \)が高々可算であることを踏まえると、全射\(f:\mathbb{N} \rightarrow \phi \)と単射\(g:\phi \rightarrow \mathbb{N} \)がともに存在すると言えるのでしょうか。空写像\begin{equation*}g:\phi \rightarrow \mathbb{N} \end{equation*}は単射です。一方、\(\mathbb{N} \)から\(\phi \)への写像\begin{equation*}f:\mathbb{N} \rightarrow \phi
\end{equation*}はそもそも存在しません。

演習問題