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

集合の濃度

可算集合の和集合の濃度

目次

Twitterで共有
メールで共有

有限集合と可算集合の和集合は可算集合

復習になりますが、有限集合\(A,B\)をそれぞれ任意に選んだとき、それらの和集合\(A\cup B\)もまた有限集合になります。では、可算集合の和集合の濃度についても同様の主張が成立するのでしょうか。順番に考えます。

まず、有限集合\(A\)と可算集合\(B\)の和集合について考えます。これらの集合を、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},\cdots ,a_{n}\right\} \\
B &=&\left\{ b_{1},b_{2},\cdots \right\}
\end{eqnarray*}とそれぞれ表記するのであれば、和集合は、\begin{equation*}
A\cup B=\left\{ a_{1},a_{2},\cdots ,a_{n},b_{1},b_{2},\cdots \right\}
\end{equation*}となります。まず、\(A\)と\(B\)が互いに素である場合、すなわち\(A\cap B=\phi \)である場合には、以下の条件\begin{eqnarray*}f\left( 1\right) &=&a_{1} \\
f\left( 2\right) &=&a_{2} \\
&&\vdots \\
f\left( n\right) &=&a_{n} \\
f\left( n+1\right) &=&b_{1} \\
f\left( n+2\right) &=&b_{2} \\
&&\vdots \\
f\left( n+m\right) &=&b_{m} \\
&&\vdots
\end{eqnarray*}を満たす写像\(f:\mathbb{N} \rightarrow A\cup B\)が定義可能ですが、これは全単射であるため\(A\cup B\)は可算集合です(演習問題)。以上の事実を利用すると、\(A\)と\(B\)が互いに素ではない場合にも\(A\cup B\)が可算集合であることが示されます(演習問題)。

命題(有限集合と可算集合の和集合は可算集合)
有限集合\(A\)と可算集合\(B\)がそれぞれ任意に与えられたとき、和集合\(A\cup B\)は可算集合である。
証明

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

例(非負・非正の整数集合は可算)
非負の整数をすべて集めてできる集合\begin{equation*}\mathbb{Z} _{+}=\left\{ 0,1,2,3,\cdots \right\}
\end{equation*}が可算集合であることをすでに示しましたが、同じことを先の命題を用いて示すこともできます。実際、\begin{equation*}\mathbb{Z} _{+}=\mathbb{N} \cup \left\{ 0\right\}
\end{equation*}という関係が成り立ちますが、\(\mathbb{N} \)は可算集合であり\(\left\{0\right\} \)は有限集合であるため、先の命題より、それらの和集合と一致する\(\mathbb{Z} _{+}\)は可算集合です。つまり、\begin{equation}\left\vert \mathbb{Z} _{+}\right\vert =\aleph _{0} \quad \cdots (1)
\end{equation}が成り立ちます。非正の整数をすべて集めてできる集合\begin{equation*}\mathbb{Z} _{-}=\left\{ 0,-1,-2,-3,\cdots \right\}
\end{equation*}が与えられたとき、それぞれの\(x\in \mathbb{Z} _{+}\)に対して、\begin{equation*}f\left( x\right) =-x\in \mathbb{Z} _{-}
\end{equation*}を定める写像\(f:\mathbb{Z} _{+}\rightarrow \mathbb{Z} _{-}\)を定義すればこれは全単射であるため、\begin{equation}\left\vert \mathbb{Z} _{-}\right\vert =\left\vert \mathbb{Z} _{+}\right\vert \quad \cdots (2)
\end{equation}が成り立ちます。濃度の相等関係\(=\)は推移性を満たすため、\(\left(1\right) ,\left( 2\right) \)より、\begin{equation*}\left\vert \mathbb{Z} _{-}\right\vert =\aleph _{0}
\end{equation*}が成り立ちます。つまり、\(\mathbb{Z} _{-}\)もまた可算集合です。
例(非負・非正の有理数集合は可算)
すべての正の有理数からなる集合\begin{equation*}\mathbb{Q} _{++}=\left\{ \frac{m}{n}\ |\ n\in \mathbb{N} \wedge m\in \mathbb{N} \right\}
\end{equation*}が可算集合であることはすでに示した通りです。これと有限集合\(\{0\}\)の和集合をとるとすべての非負の有理数からなる集合\begin{equation*}\mathbb{Q} _{+}=\mathbb{Q} _{++}\cup \{0\}\end{equation*}を得ます。\(\mathbb{Q} _{++}\)は可算集合であり\(\left\{ 0\right\} \)は有限集合であるため、先の命題より、それらの和集合と一致する\(\mathbb{Q} _{+}\)は可算集合です。つまり、\begin{equation}\left\vert \mathbb{Q} _{+}\right\vert =\aleph _{0} \quad \cdots (1)
\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} _{-}=\mathbb{Q} _{− −}\cup \{0\}
\end{equation*}となります。それぞれの\(x\in \mathbb{Q} _{+}\)に対して、\begin{equation*}f\left( x\right) =-x\in \mathbb{Q} _{-}
\end{equation*}を定める写像\(f:\mathbb{Q} _{+}\rightarrow \mathbb{Q} _{-}\)を定義すればこれは全単射であるため、\begin{equation}\left\vert \mathbb{Q} _{-}\right\vert =\left\vert \mathbb{Q} _{+}\right\vert \quad \cdots (2)
\end{equation}が成り立ちます。濃度の相等関係\(=\)は推移性を満たすため、\(\left(1\right) ,\left( 2\right) \)より、\begin{equation*}\left\vert \mathbb{Q} _{-}\right\vert =\aleph _{0}
\end{equation*}が成り立ちます。つまり、\(\mathbb{Q} _{-}\)もまた可算集合です。

 

可算集合どうしの和集合は可算集合

可算集合どうしの和集合もまた可算集合です。証明では有限集合と可算集合の和集合に関する先の命題や、可算集合の無限部分集合もまた可算集合であるという事実を利用します。

命題(可算集合どうしの和集合は可算集合)
集合\(A,B\)がともに可算集合であるならば、和集合\(A\cup B\)は可算集合である。
証明

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

例(整数集合は可算)
すべての整数からなる集合\(\mathbb{Z} \)は可算集合ですが、同じことを先の命題を用いて示すこともできます。実際、\begin{equation*}\mathbb{Z} =\mathbb{Z} _{+}\cup \mathbb{Z} _{-}\end{equation*}という関係が成り立ちますが、先に例を通じて確認したように\(\mathbb{Z} _{+}\)と\(\mathbb{Z} _{-}\)は可算集合であるため、先の命題より、それらの和集合と一致する\(\mathbb{Z} \)もまた可算集合です。
例(有理数集合は可算)
すべての有理数からなる集合\(\mathbb{Q} \)は可算集合です。実際、\begin{equation*}\mathbb{Q} =\mathbb{Q} _{+}\cup \mathbb{Q} _{-}\end{equation*}という関係が成り立ちますが、先に例を通じて確認したように\(\mathbb{Q} _{+}\)と\(\mathbb{Q} _{-}\)は可算集合であるため、先の命題より、それらの和集合と一致する\(\mathbb{Q} \)もまた可算集合です。

 

有限個の可算集合の和集合は可算集合

先の命題は3個以上の可算集合に関しても拡張可能です。証明では集合の個数\(n\)に関する数学的帰納法を利用します。

命題(有限個の可算集合の和集合は可算集合)
有限\(n\)個の集合\(A_{1},A_{2},\cdots ,A_{n}\)がいずれも可算集合であるならば、和集合\(A_{1}\cup A_{2}\cup \cdots \cup A_{n}\)も可算集合である。
証明

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

集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の添字集合\(\Lambda \)が有限集合であるとともに、この集合族の任意の要素\(A_{\lambda }\)が可算集合である場合、この集合族の和集合もまた可算集合になります。証明では直前の命題を利用します。

命題(有限可算集合族の和集合は可算集合)
集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の任意の要素\(A_{\lambda }\ \left(\lambda \in \Lambda \right) \)は可算集合であり、なおかつ添字集合\(\Lambda \)が有限集合であるならば、和集合\begin{equation*}\bigcup_{\lambda \in \Lambda }A_{\lambda }
\end{equation*}もまた可算集合である。

証明

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

 

可算個の可算集合の和集合は可算集合

実は、先の命題は可算個の可算集合に関しても拡張可能です。

命題(可算個の可算集合の和集合は可算集合)
可算集合族\(\left\{ A_{i}\right\} _{i\in \mathbb{N} }\)の任意の要素\(A_{i}\ \left( i\in \mathbb{N} \right) \)が可算集合であるならば、和集合\begin{equation*}\bigcup_{i\in \mathbb{N} }A_{i}
\end{equation*}もまた可算集合である。

証明

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

集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の添字集合\(\Lambda \)が可算集合であるとともに、この集合族の任意の要素\(A_{\lambda }\)が可算集合である場合、この集合族の和集合もまた可算集合になります。証明では直前の命題を利用します。

命題(可算可算集合族の和集合は可算集合)
集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の任意の要素\(A_{\lambda }\ \left(\lambda \in \Lambda \right) \)は可算集合であり、なおかつ添字集合\(\Lambda \)が可算集合であるならば、和集合\begin{equation*}\bigcup_{\lambda \in \Lambda }A_{\lambda }
\end{equation*}もまた可算集合である。

証明

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

偶数集合\(E\)、奇数集合\(O\)、整数集合\(\mathbb{Z} \)、有理数集合\(\mathbb{Q} \)などはいずれも可算集合であるため、上の命題において\(\Lambda \)をこれらの可算集合に置き換えても同様の結論が得られます。

 

高々可算個の高々可算集合の和集合は高々可算集合

ある集合が高々可算集合であることとは、その集合が有限集合もしくは可算集合のどちらか一方であることを意味します。以上の事実とこれまでの議論を踏まえると以下を得ます。

命題(高々可算個の高々可算集合の和集合は高々可算集合)
集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の任意の要素\(A_{\lambda }\ \left(\lambda \in \Lambda \right) \)は高々可算集合であり、なおかつ添字集合\(\Lambda \)が高々可算集合であるならば、和集合\begin{equation*}\bigcup_{\lambda \in \Lambda }A_{\lambda }
\end{equation*}もまた高々可算集合である。

証明

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

集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の任意の要素\(A_{\lambda }\ \left(\lambda \in \Lambda \right) \)は有限集合であり、なおかつ添字集合\(\Lambda \)が可算集合である場合、上の命題より\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の和集合は高々可算集合であることが保証されますが、可算集合であるとは限りません。以下の例より明らかです。

例(高々可算個の高々可算集合の和集合は高々可算集合)
集合族\(\left\{ A_{i}\right\} _{i\in \mathbb{N} }\)が、\begin{equation*}\forall i\in \mathbb{N} :A_{i}=\left\{ 1\right\}
\end{equation*}を満たすものとします。つまり、この集合族の添字集合\(\mathbb{N} \)は可算集合である一方で、任意の要素\(A_{i}\)は有限集合です。この集合族の和集合は、\begin{equation*}\bigcup_{i\in \mathbb{N} }A_{i}=\bigcup_{i\in \mathbb{N} }\left\{ 1\right\} =\left\{ 1\right\}
\end{equation*}ですが、これは有限集合です。したがって可算集合ではありません。

Twitterで共有
メールで共有
DISCUSSION

質問とコメント