WIIS

集合の濃度

可算集合の直積集合の濃度

目次

次のページ:

非可算集合

Mailで保存
Xで共有

有限集合と可算集合の直積は可算集合

有限集合\(A,B\)をそれぞれ任意に選んだとき、それらの直積集合\begin{equation*}A\times B
\end{equation*}もまた有限集合になることが明らかになりました。では、可算集合の直積の濃度についても同様の主張が成立するのでしょうか。

まずは、有限集合\(A\)と可算集合\(B\)の直積\(A\times B\)の濃度について考えます。

\(A=\phi \)の場合には、\begin{eqnarray*}A\times B &=&\phi \times B \\
&=&\phi
\end{eqnarray*}となりますが、空集合は有限集合であるため、この場合には\(A\times B\)は有限集合です。

\(A\not=\phi \)の場合には、\begin{equation*}\left\vert A\times B\right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立ちます。つまり、非空な有限集合と可算集合の直積は可算集合になります。

命題(有限集合と可算集合の直積は可算集合)
非空な有限集合\(A\)と可算集合\(B\)がそれぞれ任意に与えられたとき、直積集合\begin{equation*}A\times B
\end{equation*}は可算集合である。すなわち、\begin{equation*}
\left\vert A\times B\right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つ。

証明

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

 

自然数集合の直積の濃度

可算集合である自然数集合\(\mathbb{N} \)どうしの直積\begin{equation*}\mathbb{N} \times \mathbb{N} \end{equation*}は可算集合です。

命題(自然数集合の直積は可算)
自然数集合の直積\(\mathbb{N} \times \mathbb{N} \)は可算集合である。すなわち、\begin{equation*}\left\vert \mathbb{N} \times \mathbb{N} \right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つ。

証明

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

例(非負の整数集合の直積は可算集合)
自然数集合\(\mathbb{N} \)について、\begin{equation}\left\vert \mathbb{N} \times \mathbb{N} \right\vert =\left\vert \mathbb{N} \right\vert \quad \cdots (1)
\end{equation}が成り立つことが明らかになりました。正の有理数からなる集合は、\begin{equation*}\mathbb{Q} _{++}=\left\{ \frac{m}{n}\in \mathbb{Q} \ |\ m\in \mathbb{N} \wedge n\in \mathbb{N} \right\}
\end{equation*}ですが、正の有理数\(\frac{m}{n}\in \mathbb{Q} _{++}\)に対して、\begin{equation*}f\left( \frac{m}{n}\right) =\left( m,n\right)
\end{equation*}を定める写像\begin{equation*}
f:\mathbb{Q} _{++}\rightarrow \mathbb{N} \times \mathbb{N} \end{equation*}を定義します。任意の\(\frac{m_{1}}{n_{1}},\frac{m_{2}}{n_{2}}\in \mathbb{Q} _{++}\)に対して、\begin{eqnarray*}f\left( \frac{m_{1}}{n_{1}}\right) =f\left( \frac{m_{2}}{n_{2}}\right)
&\Leftrightarrow &\left( m_{1},n_{1}\right) =\left( m_{2},n_{2}\right) \quad
\because f\text{の定義} \\
&\Leftrightarrow &m_{1}=m_{2}\wedge n_{1}=n_{2} \\
&\Rightarrow &\frac{m_{1}}{n_{1}}=\frac{m_{2}}{n_{2}}
\end{eqnarray*}が成り立つため\(f\)は単射です。また、\(\left( m,n\right)\in \mathbb{N} \times \mathbb{N} \)を任意に選んだとき、それに対して\(\frac{m}{n}\in \mathbb{Q} _{++}\)に注目すれば、\begin{equation*}f\left( \frac{m}{n}\right) =\left( m,n\right) \quad \because f\text{の定義}
\end{equation*}が成り立つため\(f\)は全射です。以上より\(f\)は全単射であることが明らかになりました。したがって、\begin{equation}\left\vert \mathbb{Q} _{++}\right\vert =\left\vert \mathbb{N} \times \mathbb{N} \right\vert \quad \cdots (2)
\end{equation}が成り立ちます。濃度の相等関係\(=\)は推移律を満たすため、\(\left(1\right) ,\left( 2\right) \)より、\begin{equation*}\left\vert \mathbb{Q} _{++}\right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}を得ます。つまり、正の有理数からなる集合\(\mathbb{Q} _{++}\)は可算集合です。
例(非負・非正の有理数集合は可算)
正の有理数からなる集合\begin{equation*}\mathbb{Q} _{++}=\left\{ \frac{m}{n}\in \mathbb{Q} \ |\ 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} _{+}\)は可算集合です。つまり、\begin{equation}\left\vert \mathbb{Q} _{+}\right\vert =\left\vert \mathbb{N} \right\vert \quad \cdots (1)
\end{equation}が成り立ちます。すべての負の有理数からなる集合\begin{equation*}\mathbb{Q} _{− −}=\left\{ -\frac{m}{n}\in \mathbb{Q} \ |\ 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
\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 =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立ちます。以上より、\(\mathbb{Q} _{+}\)と\(\mathbb{Q} _{-}\)がともに可算集合であることが明らかになりました。
例(有理数集合は可算)
有理数集合\(\mathbb{Q} \)について以下の関係\begin{equation*}\mathbb{Q} =\mathbb{Q} _{+}\cup \mathbb{Q} _{-}\end{equation*}が成り立ちます。先に示したように\(\mathbb{Q} _{+}\)と\(\mathbb{Q} _{-}\)は可算集合ですが、可算集合どうしの和集合は可算集合であるため\(\mathbb{Q} _{+}\cup \mathbb{Q} _{-}\)は可算集合であり、したがってそれと一致する\(\mathbb{Q} \)もまた可算集合です。つまり、\begin{equation*}\left\vert \mathbb{Q} \right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立ちます。

 

可算集合の直積は可算

自然数集合\(\mathbb{N} \)であるとは限らない可算集合\(A,B\)についても、それらの直積\begin{equation*}A\times B
\end{equation*}は可算集合になります。

命題(可算集合の直積は可算)
集合\(A,B\)がともに可算集合であるならば、直積\begin{equation*}A\times B
\end{equation*}もまた可算集合である。

証明

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

例(可算集合の直積は可算集合)
自然数集合\(\mathbb{N} \)や整数集合\(\mathbb{Z} \)および有理数集合\(\mathbb{Q} \)はいずれも可算集合です。したがって、先の命題より、\begin{eqnarray*}&&\mathbb{N} \times \mathbb{N} ,\quad \mathbb{N} \times \mathbb{Z} ,\quad \mathbb{N} \times \mathbb{Q} , \\
&&\mathbb{Z} \times \mathbb{Z} ,\quad \mathbb{Z} \times \mathbb{Q} ,\quad \mathbb{Q} \times \mathbb{Q} \end{eqnarray*}などはいずれも可算集合です。

 

有限個の可算集合の直積は可算集合

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

命題(有限個の可算集合の直積は可算集合)
有限\(n\)個の集合\(A_{1},A_{2},\cdots ,A_{n}\)がいずれも可算集合であるならば、直積集合\begin{equation*}A_{1}\times A_{2}\times \cdots \times A_{n}
\end{equation*}もまた可算集合である。

証明

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

例(有限個の可算集合の直積は可算集合)
自然数集合\(\mathbb{N} \)やすべての整数集合\(\mathbb{Z} \)および有理数集合\(\mathbb{Q} \)はいずれも可算集合であるため、先の命題より、自然数\(n\in \mathbb{N} \)を任意に選んだとき、\begin{equation*}\mathbb{N} ^{n},\quad \mathbb{Z} ^{n},\quad \mathbb{Q} ^{n}\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*}\prod_{\lambda \in \Lambda }A_{\lambda }
\end{equation*}もまた可算集合である。

証明

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

例(有限個の可算集合の直積は可算集合)
集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の任意の要素\(A_{\lambda }\ \left(\lambda \in \Lambda \right) \)が可算集合であるものとします。添字集合が、\begin{equation*}\Lambda =\left\{ 1,2,\cdots ,n\right\}
\end{equation*}である場合、\(\Lambda \)は有限集合であるため、先の命題より、\begin{eqnarray*}\prod_{\lambda \in \Lambda }A_{\lambda } &=&\prod_{\lambda \in \left\{
1,2,\cdots ,n\right\} }A_{\lambda } \\
&=&A_{1}\times A_{2}\times \cdots \times A_{n}
\end{eqnarray*}は可算集合です。これは一個前に示した命題の主張と一致します。

例(有限個の可算集合の直積は可算集合)
集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の任意の要素\(A_{\lambda }\ \left(\lambda \in \Lambda \right) \)が可算集合であるものとします。添字集合が、\begin{equation*}\Lambda =\left\{ a,b,c,d\right\}
\end{equation*}である場合、\(\Lambda \)は有限集合であるため、先の命題より、\begin{eqnarray*}\prod_{\lambda \in \Lambda }A_{\lambda } &=&\prod_{\lambda \in \left\{
a,b,c,d\right\} }A_{\lambda } \\
&=&A_{a}\times A_{b}\times A_{c}\times A_{d}
\end{eqnarray*}は可算集合です。

 

有限個の高々可算集合の直積は高々可算集合

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

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

証明

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

 

演習問題

問題(可算集合)
以下の集合\begin{equation*}
\left\{ 0,1\right\} \times \mathbb{N} \end{equation*}が可算であることを示してください。

解答を見る

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

問題(可算集合)
以下の集合\begin{equation*}\mathbb{N} \times \mathbb{N} \times \mathbb{N} \end{equation*}が可算であることを示してください。

解答を見る

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

問題(可算集合の直積)
可算集合\(A\)と自然数\(n\in \mathbb{N} \)をそれぞれ任意に選んだとき、\begin{equation*}A^{n}=A\times \cdots \times A
\end{equation*}もまた可算であることを示してください。

解答を見る

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

問題(可算集合の直積)
以下の集合\begin{equation*}\mathbb{N} ^{7}
\end{equation*}が可算集合であることを示してください。

解答を見る

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

関連知識

次のページ:

非可算集合

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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