有限集合のベキ集合の濃度
前節までに、有限集合の部分集合・和集合・共通部分・差集合・直積集合の濃度について考えました。本節では、有限集合のベキ集合の濃度について考えます。
集合\(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*}であることに注意してください。
有限集合\(A\)の各要素について、それを\(A\)の部分集合に含めるか含めないかの2通りの選択肢があります。この選択を\(\left\vert A\right\vert \)回独立に行うため、\(A\)の部分集合の個数、すなわちベキ集合\(2^{A}\)の濃度は、\begin{equation*}2^{\left\vert A\right\vert }
\end{equation*}であると予想できます。まずは、この直感を厳密に証明します。
\end{equation*}が成り立つ。
A=\left\{ 1,2,3\right\}
\end{equation*}の濃度は、\begin{equation*}
\left\vert A\right\vert =3
\end{equation*}であるため、ベキ集合の濃度は、\begin{eqnarray*}
\left\vert 2^{A}\right\vert &=&2^{\left\vert A\right\vert } \\
&=&2^{3} \\
&=&8
\end{eqnarray*}です。実際、\begin{equation*}
2^{A}=\left\{ \phi ,\left\{ 1\right\} ,\left\{ 2\right\} ,\left\{ 3\right\}
,\left\{ 1,2\right\} ,\left\{ 1,3\right\} ,\left\{ 2,3\right\} ,\left\{
1,2,3\right\} \right\}
\end{equation*}であるため、\begin{equation*}
\left\vert 2^{A}\right\vert =8
\end{equation*}です。
\end{equation*}です。ベキ集合の濃度は、\begin{eqnarray*}
\left\vert 2^{\phi }\right\vert &=&2^{\left\vert \phi \right\vert } \\
&=&2^{0} \\
&=&1
\end{eqnarray*}が成り立ちます。実際、\begin{equation*}
2^{\phi }=\left\{ \phi \right\}
\end{equation*}であるため、\begin{equation*}
\left\vert 2^{\phi }\right\vert =1
\end{equation*}です。したがって、先の命題は有限集合\(A\)が空集合であるケースも含んでいます。
A=\left\{ 1,2,3,4,5\right\}
\end{equation*}の部分集合をすべて列挙する作業は煩雑であるため、ベキ集合\(2^{A}\)の要素を具体的に特定した上で、その個数を数える作業は面倒です。一方、先の命題を利用すると、\begin{eqnarray*}\left\vert 2^{A}\right\vert &=&2^{\left\vert A\right\vert } \\
&=&2^{5} \\
&=&32
\end{eqnarray*}として、ベキ集合の濃度を容易に導出できます。
\end{equation*}として得られます。したがって、\(A\)の真部分集合の個数は、\begin{eqnarray*}\left\vert 2^{A}\backslash \left\{ A\right\} \right\vert &=&\left\vert
2^{A}\right\vert -\left\vert \left\{ A\right\} \right\vert \quad \because
\left\{ A\right\} \subset 2^{A} \\
&=&2^{\left\vert A\right\vert }-1
\end{eqnarray*}であり、\(A\)の非空な部分集合の個数は、\begin{eqnarray*}\left\vert 2^{A}\backslash \left\{ \phi \right\} \right\vert &=&\left\vert
2^{A}\right\vert -\left\vert \left\{ \phi \right\} \right\vert \quad
\because \left\{ \phi \right\} \subset 2^{A} \\
&=&2^{\left\vert A\right\vert }-1
\end{eqnarray*}です。さらに、\(A\)が非空な有限集合である場合、空集合でも全体集合でもない\(A\)の部分集合の個数は、\begin{eqnarray*}\left\vert 2^{A}\backslash \left\{ A,\phi \right\} \right\vert
&=&\left\vert 2^{A}\right\vert -\left\vert \left\{ A,\phi \right\}
\right\vert \quad \because \left\{ A,\phi \right\} \subset 2^{A} \\
&=&2^{\left\vert A\right\vert }-2
\end{eqnarray*}です。
互いに素な集合の和集合のベキ集合
有限集合\(A,B\)が互いに素である場合には、それらの和集合のベキ集合\(2^{A\cup B}\)の濃度は、個々の集合のベキ集合\(2^{A},2^{B}\)の濃度の積と一致します。つまり、\begin{equation}\left\vert 2^{A\cup B}\right\vert =\left\vert 2^{A}\right\vert \left\vert
2^{B}\right\vert \quad \cdots (1)
\end{equation}が成り立ちます。さらに、左辺については、\begin{eqnarray*}
\left\vert 2^{A\cup B}\right\vert &=&2^{\left\vert A\cup B\right\vert
}\quad \because A\cup B\text{は有限集合} \\
&=&2^{\left\vert A\right\vert +\left\vert B\right\vert }\quad \because A\text{と}B\text{は互いに素}
\end{eqnarray*}が成り立ち、右辺については、\begin{equation*}
\left\vert 2^{A}\right\vert \left\vert 2^{B}\right\vert =2^{\left\vert
A\right\vert }2^{\left\vert B\right\vert }\quad \because A,B\text{は有限集合}
\end{equation*}が成り立つため、これらと\(\left( 1\right) \)より、\begin{equation*}2^{\left\vert A\right\vert +\left\vert B\right\vert }=2^{\left\vert
A\right\vert }2^{\left\vert B\right\vert }
\end{equation*}を得ます。これは指数法則と同様の性質です。
2^{B}\right\vert
\end{equation*}が成り立つ。
演習問題
\end{equation*}が成り立つものとします。以下の問いに答えてください。
- \(A\)のすべての部分集合の個数
- \(A\)のすべての真部分集合の個数
- \(A\)のすべての非空な部分集合の個数
- \(A\)の部分集合の中でも空集合や\(A\)自身ではないものの個数
\end{equation*}が成り立つものとします。\(\left\vert A\right\vert \)を求めてください。
\left\vert B\right\vert &=&4
\end{eqnarray*}が成り立つものとします。以下の問いに答えてください。
- \(B\subset C\subset A\)を満たす集合\(C\)の個数を求めてください。
- \(B\subset C\subset A\)かつ\(B\not=C\)かつ\(C\not=A\)を満たす集合\(C\)の個数を求めてください。
2^{A}\right\vert =\left\vert 2^{B}\right\vert
\end{equation*}が成り立つことを証明してください。
\end{equation*}を定める写像\begin{equation*}
f:2^{A}\rightarrow 2^{A}
\end{equation*}を定義します。以下の問いに答えてください。
- 任意の\(B\in 2^{A}\)に対して、\begin{equation*}f\left( f\left( B\right) \right) =B\end{equation*}が成り立つことを示してください。
- \(A\not=\phi \)の場合には、\begin{equation*}f\left( B\right) =B\end{equation*}を満たす\(B\in 2^{A}\)が存在しないことを証明してください。
- \(A=\phi \)の場合について調べてください。
\end{equation*}が成り立つものとします。\(\left\vert A\right\vert \)を特定してください。
