有限集合と可算集合の直積は可算集合
有限集合\(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*}が成り立ちます。つまり、非空な有限集合と可算集合の直積は可算集合になります。
\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*}は可算集合です。
\end{equation*}が成り立つ。
\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} _{++}\)は可算集合です。
\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} _{-}\)がともに可算集合であることが明らかになりました。
\end{equation*}が成り立ちます。
可算集合の直積は可算
自然数集合\(\mathbb{N} \)であるとは限らない可算集合\(A,B\)についても、それらの直積\begin{equation*}A\times B
\end{equation*}は可算集合になります。
\end{equation*}もまた可算集合である。
&&\mathbb{Z} \times \mathbb{Z} ,\quad \mathbb{Z} \times \mathbb{Q} ,\quad \mathbb{Q} \times \mathbb{Q} \end{eqnarray*}などはいずれも可算集合です。
有限個の可算集合の直積は可算集合
先の命題は3個以上の可算集合に関しても拡張可能です。証明では集合の個数\(n\)に関する数学的帰納法を利用します。
\end{equation*}もまた可算集合である。
集合族\(\left\{ A_{\lambda }\right\} _{\lambda \in \Lambda }\)の添字集合\(\Lambda \)が有限集合であるとともに、この集合族の任意の要素\(A_{\lambda }\)が可算集合である場合、この集合族の直積もまた可算集合になります。
\end{equation*}もまた可算集合である。
\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*}は可算集合です。これは一個前に示した命題の主張と一致します。
\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*}は可算集合です。
有限個の高々可算集合の直積は高々可算集合
ある集合が高々可算集合であることとは、その集合が有限集合もしくは可算集合のどちらか一方であることを意味します。以上の事実とこれまでの議論を踏まえると以下を得ます。
\end{equation*}もまた高々可算集合である。
演習問題
\left\{ 0,1\right\} \times \mathbb{N} \end{equation*}が可算であることを示してください。
\end{equation*}もまた可算であることを示してください。
\end{equation*}が可算集合であることを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】