可算集合のベキ集合の濃度

自然数集合のベキ集合の濃度

可算集合のベキ集合は高々可算集合であることが明らかになりました。しかし、可算集合の部分集合をすべて集めた集合族、すなわち可算集合のベキ集合は非可算集合です。つまり、可算集合の1つ1つの部分集合は有限または可算であるにも関わらず、そのような部分集合の総数は可算ではありません。本節では以上のことを証明するとともに、さらに、可算集合の部分集合と0-1無限列の対応を明らかにし、可算集合の有限部分集合全体と無限部分集合全体の濃度を調べます。

集合\(A\)のベキ集合は、\(A \)のすべての部分集合からなる集合族\begin{equation*}2^{A}=\left\{ B\ |\ B\subset A\right\}
\end{equation*}として定義されます。特に、空集合は任意の集合の部分集合であるため\(\phi \subset A\)であり、したがって、\begin{equation*}\phi \in 2^{A}
\end{equation*}です。また、\(A\subset A\)ゆえに、\begin{equation*}A\in 2^{A}
\end{equation*}であることに注意してください。

自然数集合\(\mathbb{N} \)は可算集合です。可算集合の部分集合は高々可算集合であるため、\(\mathbb{N} \)の部分集合はいずれも高々可算集合です。言い換えると、ベキ集合\(2^{\mathbb{N} }\)の要素はいずれも高々可算集合です。ただし、そのことは、ベキ集合\(2^{\mathbb{N} }\)が高々可算集合であることを意味しません。実際、\(2^{\mathbb{N} }\)は非可算集合です。つまり、\(2^{\mathbb{N} }\)の要素は高々可算集合ですが、\(2^{\mathbb{N} }\)そのものは高々可算ではなく、非可算集合です。

可算集合のベキ集合の濃度

可算集合である自然数集合\(\mathbb{N} \)のベキ集合\(2^{\mathbb{N} }\)が非可算集合であることが明らかになりました。この結果は自然数集合に限らず、任意の可算集合に拡張できます。

先の命題は2つの点を指摘しています。1つ目は、任意の可算集合のベキ集合は非可算集合であるということです。2つ目は、任意の可算集合のベキ集合は\(\mathbb{N} \)のベキ集合と等しい濃度を持つということです。したがって、任意の可算集合のベキ集合の濃度は一致します。つまり、可算集合\(A,B\)を任意に選んだとき、\(2^{A}\)と\(2^{B}\)はともに非可算集合であるとともに、\begin{equation*}\left\vert 2^{A}\right\vert =\left\vert 2^{B}\right\vert
\end{equation*}が成り立ちます。

ベキ集合と0-1無限列

0-1無限列（infinite binary sequence）とは、各項が\(0\)または\(1 \)であるような数列\begin{equation*}\left\{ x_{n}\right\} _{n\in \mathbb{N} }
\end{equation*}です。ただし、任意の\(n\in \mathbb{N} \)について\(x_{n}\in \left\{ 0,1\right\} \)です。すべての0-1無限列からなる集合を、\begin{equation*}\left\{ 0,1\right\} ^{\mathbb{N} }=\left\{ \left\{ x_{n}\right\} _{n\in \mathbb{N} }\ |\ \forall n\in \mathbb{N} :x_{n}\in \left\{ 0,1\right\} \right\}
\end{equation*}で表記します。

自然数集合の部分集合\(A\subset \mathbb{N} \)が与えられたとき、0-1無限列\(\left\{ x_{n}\right\} _{n\in \mathbb{N} }\)を、\begin{equation*}x_{n}=\left\{
\begin{array}{cl}
1 & \left( if\ n\in A\right) \\
0 & \left( if\ n\not\in A\right)\end{array}\right.
\end{equation*}と定義します。この無限列は、各自然数が\(A\)に属するかどうかを記録したものです。

すべての0-1無限列からなる集合\(\left\{ 0,1\right\} ^{\mathbb{N} }\)の濃度は、自然数集合\(\mathbb{N} \)のベキ集合\(2^{\mathbb{N} }\)と同じ濃度を持ちます。

これまでは自然数集合の部分集合\(A\subset \mathbb{N} \)から0-1無限列を定義しましたが、一般の可算集合の部分集合からも0-1無限列を定義できます。具体的には以下の通りです。

可算集合\(A\)の要素を、\begin{equation*}A=\left\{ a_{1},a_{2},a_{3},\cdots \right\}
\end{equation*}と付番します。その部分集合\(B\subset A\)が与えられたとき、0-1無限列\(\left\{x_{n}\right\} _{n\in \mathbb{N} }\)を、\begin{equation*}x_{n}=\left\{
\begin{array}{cl}
1 & \left( if\ a_{n}\in B\right) \\
0 & \left( if\ a_{n}\not\in B\right)\end{array}\right.
\end{equation*}と定義します。この無限列は、\(A\)の各要素が\(B\)に属するかどうかを記録したものです。

以下が成り立ちます。

可算集合\(A\)の部分集合\(B\subset A\)に対応する0-1無限列\(\left\{ x_{n}\right\} _{n\in \mathbb{N} }\)を、\begin{equation*}x_{n}=\left\{
\begin{array}{cl}
1 & \left( if\ a_{n}\in B\right) \\
0 & \left( if\ a_{n}\not\in B\right)\end{array}\right.
\end{equation*}を満たすものとして定義しました。これは、それぞれの\(x\in A\)に対して、\begin{equation*}\chi _{B}\left( x\right) =\left\{
\begin{array}{cl}
1 & \left( if\ x\in B\right) \\
0 & \left( if\ x\not\in B\right)\end{array}\right.
\end{equation*}を定める写像\begin{equation*}
\chi _{B}:A\rightarrow \left\{ 0,1\right\}
\end{equation*}と同一視できます。このような写像\(\chi _{B}\)を特性関数と呼びます。特性関数を用いれば、可算集合に限定されない一般の集合を舞台に、これまでと同様の議論を行うことができます。詳細は場を改めて解説します。

可算集合の部分集合族の濃度

以降の議論では、見やすさを考慮して集合\(A\)のベキ集合\(2^{A}\)を、\begin{equation*}\mathcal{P}\left( A\right)
\end{equation*}で表記します。

集合\(A\)のすべての有限部分集合からなる集合族を、\begin{equation*}\mathcal{P}_{fin}\left( A\right) =\left\{ B\subset A\ |\ \exists n\in \mathbb{Z} _{+}:\left\vert B\right\vert =n\right\}
\end{equation*}で表記します。特に、自然数\(k\in \mathbb{N} \)に対して、\(k\)個の要素を持つ\(A\)のすべての有限部分集合からなる集合族を、\begin{equation*}\mathcal{P}_{k}\left( A\right) =\left\{ B\subset A\ |\ \left\vert
B\right\vert =k\right\}
\end{equation*}で表記します。また、\begin{equation*}
\mathcal{P}_{0}\left( A\right) =\left\{ \phi \right\}
\end{equation*}と定義します。このとき、\begin{equation*}
\mathcal{P}_{fin}\left( A\right) =\bigcup_{k=0}^{+\infty }\mathcal{P}_{k}\left( A\right)
\end{equation*}が成り立つことに注意してください。

先に明らかにしたように、\(A\)が可算集合である場合に\(\mathcal{P}\left( A\right) \)は非可算集合です。その一方で、可算集合\(A\)の有限部分集合からなる集合族\(\mathcal{P}_{fin}\left( A\right) \)は可算集合です。

可算集合\(A\)のベキ集合\(\mathcal{P}\left( A\right) \)は非可算集合である一方で、\(A\)の有限部分集合からなる集合族\(\mathcal{P}_{fin}\left( A\right) \)は可算集合であることが明らかになりました。したがって、\begin{equation*}\mathcal{P}_{fin}\left( A\right) \subset \mathcal{P}\left( A\right)
\end{equation*}である一方で、\begin{equation*}
\left\vert \mathcal{P}_{fin}\left( A\right) \right\vert \not=\left\vert
\mathcal{P}\left( A\right) \right\vert
\end{equation*}です。つまり、可算集合\(A\)の有限部分集合に対して重複なく付番することはできますが、有限部分集合と無限部分集合を合わせたすべての部分集合に対して重複なく付番することはできません。したがって、可算集合のベキ集合が非可算集合である原因は有限部分集合が多すぎるからではなく、無限部分集合が非可算個存在することにあると推察できます。実際、集合\(A\)の無限部分集合全体からなる集合族を、\begin{equation*}\mathcal{P}_{\infty }\left( A\right) =\left\{ B\subset A\ |\ \forall n\in \mathbb{Z} _{+}:\left\vert B\right\vert \not=n\right\}
\end{equation*}で表記する場合、以下が成り立ちます。

演習問題