教材一覧
教材一覧
教材検索

集合の濃度

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

目次

前のページ:

高々可算集合

Twitterで共有
メールで共有

可算集合の無限部分集合は可算集合

復習になりますが有限集合\(A\)の部分集合\(B \)を任意に選んだとき、\(B\)もまた有限集合であるとともに、\begin{equation*}\left\vert B\right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立ちます。また、有限集合\(A\)の真部分集合\(B\)を任意に選んだとき、\(B\)もまた有限集合であるとともに、\begin{equation*}\left\vert B\right\vert <\left\vert A\right\vert
\end{equation*}が成り立ちます。では、可算集合とその部分集合の濃度についても同様の議論が成立するのでしょうか。

可算集合\(A\)の部分集合\(B \)を任意に選びます。\(B\subset A\)です。まずは\(B=A\)である場合について考えます。これは\(B\subset A\)と\(A\subset B\)がともに成り立つことと必要十分であるため、すると濃度の大小関係\(\leq \)の性質より\(\left\vert B\right\vert \leq \left\vert A\right\vert \)と\(\left\vert A\right\vert \leq \left\vert B\right\vert \)がともに成り立ちます。濃度の大小関係\(\leq \)は反対称律を満たすため、このとき\(\left\vert A\right\vert =\left\vert B\right\vert \)が成り立ちます。続いて\(B\not=A\)である場合、すなわち\(B\)が\(A\)の真部分集合である場合について考えます。\(B\)は有限集合または無限集合のどちらか一方です。\(B\)が有限集合である場合、\(A\)が無限集合であることから\(\left\vert B\right\vert \not=\left\vert A\right\vert \)が明らかに成り立ちます。一方、\(B\)が無限集合である場合には、\begin{equation*}\left\vert B\right\vert =\left\vert A\right\vert
\end{equation*}が成り立つことが示されます。つまり、可算集合\(A\)の真部分集合\(B\)が無限集合である場合には両者の濃度が等しくなること、すなわち\(B\)もまた可算集合になることが保証されます。有限集合においては起こり得ない不思議な現象です。

命題(可算集合の無限真部分集合は可算集合)
可算集合\(A\)の真部分集合\(B\)が無限集合である場合には、\(B\)もまた可算集合である。すなわち、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert =\aleph _{0}
\end{equation*}が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

可算集合は自身と等しい濃度を持つことと上の命題を踏まえると以下を得ます。

命題(可算集合の無限部分集合は可算集合)
可算集合\(A\)の部分集合\(B \)が無限集合である場合には、\(B\)もまた可算集合である。すなわち、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert =\aleph _{0}
\end{equation*}が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(自然数集合の無限部分集合)
すべての自然数からなる集合\(\mathbb{N} \)は可算集合であるため、先の命題より、\(\mathbb{N} \)の部分集合であるような無限集合もまた可算集合です。具体例を挙げると、すべての非負の偶数からなる集合\begin{equation*}E=\left\{ 2n\ |\ n\in \mathbb{N} \right\}
\end{equation*}や、すべての非負の奇数からなる集合\begin{equation*}
O=\left\{ 2n-1\ |\ n\in \mathbb{N} \right\}
\end{equation*}はいずれも\(\mathbb{N} \)の部分集合であるような無限集合であるため、これらは可算集合です。つまり、\begin{equation*}\left\vert E\right\vert =\left\vert O\right\vert =\left\vert \mathbb{N} \right\vert =\aleph _{0}
\end{equation*}が成り立ちます。

例(整数集合の無限部分集合)
すべての整数からなる集合\(\mathbb{Z} \)は可算集合であるため、先の命題より、\(\mathbb{Z} \)の部分集合であるような無限集合もまた可算集合です。具体例を挙げると、すべての正の整数からなる集合\begin{equation*}\mathbb{Z} _{++}=\left\{ z\in \mathbb{Z} \ |\ z>0\right\}\end{equation*}や、すべての非負の整数からなる集合\begin{equation*}\mathbb{Z} _{+}=\left\{ z\in \mathbb{Z} \ |\ z\geq 0\right\}
\end{equation*}や、すべての負の整数からなる集合\begin{equation*}\mathbb{Z} _{− −}=\left\{ z\in \mathbb{Z} \ |\ z<0\right\}
\end{equation*}や、すべての非正の整数からなる集合\begin{equation*}\mathbb{Z} _{-}=\left\{ z\in \mathbb{Z} \ |\ z\leq 0\right\}
\end{equation*}はいずれも\(\mathbb{Z} \)の部分集合であるような無限集合であるため、これらは可算集合です。つまり、\begin{equation*}\left\vert \mathbb{Z} _{++}\right\vert =\left\vert \mathbb{Z} _{+}\right\vert =\left\vert \mathbb{Z} _{− −}\right\vert =\left\vert \mathbb{Z} _{-}\right\vert =\left\vert \mathbb{Z} \right\vert =\aleph _{0}
\end{equation*}が成り立ちます。

例(自然数集合の直積の無限部分集合)
すべての自然数からなる集合\(\mathbb{N} \)の直積\begin{equation*}\mathbb{N} \times \mathbb{N} =\left\{ \left( x,y\right) \ |\ x\in \mathbb{N} \wedge y\in \mathbb{N} \right\}\end{equation*}は可算集合であるため、先の命題より、\(\mathbb{N} \times \mathbb{N}\)の部分集合であるような無限集合もまた可算集合です。具体例を挙げると、以下の集合\begin{equation*}\mathbb{Z} _{+}\times \mathbb{Z} _{+}=\left\{ \left( x,y\right) \in \mathbb{N} \times \mathbb{N} \ |\ x>0\wedge y>0\right\}\end{equation*}は\(\mathbb{N} \times \mathbb{N} \)の部分集合であるような無限集合であるため、これは可算集合です。つまり、\begin{equation*}\left\vert \mathbb{Z} _{+}\times \mathbb{Z} _{+}\right\vert =\left\vert \mathbb{N} \times \mathbb{N} \right\vert =\aleph _{0}
\end{equation*}が成り立ちます。

 

可算集合の部分集合は高々可算集合

可算集合の部分集合は有限集合と無限集合のどちらか一方であることと先の命題を踏まえると以下を得ます。

命題(可算集合の部分集合は高々可算集合)
可算集合の任意の部分集合は高々可算集合である。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

高々可算集合の部分集合は高々可算集合

先の命題を踏まえると以下を得ます。

命題(高々可算集合の部分集合は高々可算集合)
高々可算集合の任意の部分集合は高々可算集合である。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

演習問題

問題(可算集合の部分集合の濃度)
すべての正の有理数からなる集合\begin{equation*}\mathbb{Q} _{++}=\left\{ \frac{m}{n}\ |\ n\in \mathbb{N} \wedge m\in \mathbb{N} \right\}
\end{equation*}が可算集合であることを証明してください。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(可算集合の部分集合の濃度)
すべての負の有理数からなる集合\begin{equation*}\mathbb{Q} _{− −}=\left\{ -\frac{m}{n}\ |\ n\in \mathbb{N} \wedge m\in \mathbb{N} \right\}
\end{equation*}が可算集合であることを証明してください。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

前のページ:

高々可算集合

Twitterで共有
メールで共有
DISCUSSION

質問とコメント