可算集合の差集合の濃度
前節までに、可算集合の部分集合や和集合、共通部分の濃度について解説しました。本節では、可算集合の差集合の濃度について考えます。
集合\(A,B\)の差集合\(A\backslash B\)とは、\(A\)に属する一方で\(B\)には属さない要素からなる集合です。差集合については、\begin{equation*}A\backslash B\subset A
\end{equation*}が成り立ちます。したがって、\(A\)が可算集合である場合、\(B\)が可算であるかどうかに関わらず、可算集合の部分集合の濃度に関する性質を利用することにより、差集合\(A\backslash B\)は高々可算であることが示されます。
A &=&\mathbb{Q} \\
B &=&\mathbb{R} \backslash \mathbb{Z} \end{eqnarray*}に注目します。\(A\)は可算集合であり\(B\)は非可算集合です。差集合は、\begin{equation*}A\backslash B=\mathbb{Z} \end{equation*}ですが、これは可算集合であり、したがって非可算集合です。この例は、右側の集合\(B\)が非可算集合であっても、左側の集合\(A\)が可算集合であれば\(A\backslash B\)は高々可算集合になることを示しています。
先の命題を踏まえると以下を得ます。
2つの可算集合の差集合は高々可算集合であることが明らかになりましたが、そのパターンとしては空集合、1点集合、任意の有限濃度を持つ集合、可算集合のいずれにもなり得ます。
A &=&\mathbb{N} \\
B &=&\mathbb{N} \end{eqnarray*}はともに可算集合ですが、差集合は、\begin{equation*}
A\backslash B=\phi
\end{equation*}であるため、\begin{equation*}
\left\vert A\backslash B\right\vert =\left\vert \phi \right\vert =0
\end{equation*}です。
A &=&\mathbb{N} \\
B &=&\mathbb{N} \backslash \left\{ 1\right\}
\end{eqnarray*}はともに可算集合ですが、差集合は、\begin{equation*}
A\backslash B=\left\{ 1\right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\backslash B\right\vert =\left\vert \left\{ 1\right\}
\right\vert =1
\end{equation*}です。
B &=&\mathbb{N} \backslash \left\{ 1,\cdots ,k\right\}
\end{eqnarray*}はともに可算集合ですが、差集合は、\begin{equation*}
A\backslash B=\left\{ 1,\cdots ,k\right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\backslash B\right\vert =\left\vert \left\{ 1,\cdots ,k\right\}
\right\vert =k
\end{equation*}です。
A &=&\mathbb{N} \\
B &=&\left\{ 2n-1\ |\ n\in \mathbb{N} \right\}
\end{eqnarray*}はともに可算集合ですが、差集合は、\begin{equation*}
A\backslash B=\left\{ 2n\ |\ n\in \mathbb{N} \right\}
\end{equation*}であるため、\begin{equation*}
\left\vert A\backslash B\right\vert =\left\vert \left\{ 2n\ |\ n\in \mathbb{N} \right\} \right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}です。
有限集合\(A\)については、任意の集合\(B\)について差集合\(A\backslash B\)は有限集合であるとともに、\begin{equation*}\left\vert A\backslash B\right\vert =\left\vert A\right\vert -\left\vert
A\cap B\right\vert
\end{equation*}が成り立つため、\(\left\vert A\right\vert \)と\(\left\vert A\cap B\right\vert \)から差集合の濃度を特定できます。一方、\(A\)が可算集合である場合には、差集合の濃度\(\left\vert A\backslash B\right\vert \)は\(0,1,2,\cdots ,\left\vert \mathbb{N} \right\vert \)のいずれにもなり得ることを例を通じて確認しました。したがって、\(\left\vert A\right\vert \)と\(\left\vert A\cap B\right\vert \)から\(\left\vert A\backslash B\right\vert \)を一意に特定できません。一般的に保証されるのは、\begin{equation*}\left\vert A\backslash B\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}ということだけです。
可算集合と有限集合の差集合の濃度
集合\(A\)が可算集合である場合、任意の集合\(B\)に対して差集合\(A\backslash B\)は高々可算集合であることが明らかになりました。特に、\(B\)が有限集合である場合には\(A\backslash B\)が可算集合であることが保証されます。
A &=&\mathbb{Z} \\
B &=&\left\{ -2,-1,0,1,2\right\}
\end{eqnarray*}に注目します。\(A\)は可算集合であり\(B\)は有限集合です。差集合は、\begin{equation*}A\backslash B=\left\{ \cdots ,-5,-4,-3,3,4,5,\cdots \right\}
\end{equation*}ですが、先の命題より、これは可算集合です。
高々可算集合の差集合の濃度
これまでの議論を踏まえると以下を得ます。
先の命題を踏まえると以下を得ます。
演習問題
\end{equation*}が高々可算集合であることを証明してください。
