可算集合の部分集合

可算集合の部分集合が無限集合であるならば、それもまた可算集合です。したがって、高々可算集合の部分集合は高々可算集合です。

可算集合 部分集合

可算集合の無限部分集合

有限集合\(X\)の真部分集合\(Y\)を任意に選びます。つまり、\(Y\subset X\)かつ\(Y\not=X\)です。このとき、\(Y\)の要素の個数は\(X\)の要素の個数よりも少ないため、\(\#Y=\#X\)は成り立ちません。では、\(X\)が可算集合である場合にはどうでしょうか。可算集合\(X\)の真部分集合\(Y\)が有限集合である場合には、やはり\(\#Y=\#X\)は成り立ちません。一方、可算集合\(X\)の真部分集合\(Y\)が無限集合である場合、有限集合の場合の延長線上で考えてしまうと\(\#Y\not=\#X\)となりそうですが、実際には、両者は等しい濃度を持ちます。有限集合においては起こり得ない不思議な現象です。

可算集合\(X\)が与えられたとき、その部分集合\(Y\)を任意に選びます。ただし、\(Y\)は無限集合です。可算集合の定義より、\(X\)の要素には\(x_{1},x_{2},\cdots \)と付番できますが、\(X\)における要素間の順番を保ったまま\(Y\)の要素に新たに付番したものを\(x_{n_{1}},x_{n_{2}},\cdots \)で表します。つまり、\begin{eqnarray*}
n_{1} &=&\min \{n\in \mathbb{N}\ |\ x_{n}\in Y\} \\
n_{2} &=&\min \{n\in \mathbb{N}\ |\ x_{n}\in Y,\ n>n_{1}\} \\
&&\vdots
\end{eqnarray*}ということです。その上で、それぞれの番号\(n_{i}\in \mathbb{N}\)に対して、\begin{equation*}
f\left( n_{i}\right) =x_{n_{i}}\in Y
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow Y\)を構成すれば、これは全単射となります(演習問題にします)。したがって、\(Y\)もまた可算集合です。

命題(可算集合の無限部分集合)
可算集合\(X\)の部分集合\(Y\)を任意に選ぶ。このとき、\(Y\)が無限集合であるならば、\(Y\)もまた可算集合である。
証明を見る(プレミアム会員限定)

上の命題の活用例をいくつか紹介します。

例(偶数集合)
すべての偶数からなる集合\begin{equation*}
E=\{2x\ |\ x\in \mathbb{N}\}
\end{equation*}が可算集合であることはすでに示した通りです。\(E\)は可算集合\(\mathbb{N} \)の無限部分集合であるため、上の命題からも\(E\)が可算集合であることを確認できます。
例(奇数集合)
すべての奇数からなる集合\begin{equation*}
O=\{2x-1\ |\ x\in \mathbb{N}\}
\end{equation*}が可算集合であることはすでに示した通りです。\(O\)は可算集合\(\mathbb{N} \)の無限部分集合であるため、上の命題からも\(O\)が可算集合であることを確認できます。
例(正の有理数集合)
すべての正の有理数からなる集合\begin{equation*}
\mathbb{Q} _{++}=\left\{ \frac{m}{n}\ |\ n,m\in \mathbb{N}\right\}
\end{equation*}は可算集合です。証明の方針は以下の通りです。まず、以下の集合\begin{equation*}
A=\left\{ \left( n,m\right) \ |\ \frac{m}{n}\in
\mathbb{Q} _{++}\right\}
\end{equation*}は明らかに\(\mathbb{Q} _{++}\)と対等です。つまり、\(A\sim \mathbb{Q} _{++}\)が成り立ちます。自然数集合の直積\(\mathbb{N} \times \mathbb{N}\)は可算集合ですが、\(A\)は\(\mathbb{N} \times \mathbb{N}\)の部分集合であり、なおかつ無限集合であるため、上の命題より、\(A\sim \mathbb{N}\times \mathbb{N}\)が成り立ちます。したがって、\(\sim \)の推移性より\(\mathbb{Q} _{++}\sim \mathbb{N}\times \mathbb{N}\)、さらに\(\mathbb{Q} _{++}\sim \mathbb{N}\)が成り立ちます。
例(負の有理数集合)
すべての負の有理数からなる集合\begin{equation*}
\mathbb{Q} _{–}=\left\{ -\frac{m}{n}\ |\ n,m\in \mathbb{N}\right\}
\end{equation*}は可算集合です。実際、それぞれの正の有理数\(\frac{m}{n}\in \mathbb{Q} _{++}\)に対して、\begin{equation*}
f\left( \frac{m}{n}\right) =-\frac{m}{n}\in
\mathbb{Q} _{–}
\end{equation*}を定める写像\(f:\mathbb{Q} _{++}\rightarrow \mathbb{Q} _{–}\)は全単射であるため(証明は演習問題にします)、\(\mathbb{Q} _{++}\sim \mathbb{Q} _{-}\)が成り立ちます。先に示したように\(\mathbb{Q} _{++}\sim \mathbb{N}\)であるため、\(\sim \)の推移性より\(\mathbb{Q} _{–}\sim \mathbb{N}\)が成り立ちます。

 

可算集合の部分集合

復習になりますが、有限集合と可算集合を総称して高々可算集合と呼びます。可算集合\(X\)の部分集合\(Y\)は有限集合と無限集合のどちらか一方です。\(Y\)が有限集合である場合には、\(Y\)は高々可算集合であると言えます。\(Y\)が無限集合である場合には、上の命題より、\(Y\)は可算集合です。したがって以下の命題が成り立ちます。

系(可算集合の部分集合)
可算集合\(X\)の部分集合\(Y\)を任意に選ぶ。このとき、\(Y\)は高々可算集合である。

上の命題と、有限集合の部分集合が有限集合であることを踏まえると、以下の命題を得ます。

系(高々可算集合の部分集合)
高々可算集合\(X\)の部分集合\(Y\)を任意に選ぶ。このとき、\(Y\)は高々可算集合である。

次回は可算集合の和集合について学びます。

次へ進む 質問・コメントを読む 演習問題(プレミアム会員限定)

ワイズをさらに活用するための会員サービス

ユーザー名とメールアドレスを入力して一般会員に無料登録すれば、質問やコメントを投稿できるようになります。さらに、有料(500円/月)のプレミアム会員へアップグレードすることにより、プレミアムコンテンツ(命題の証明や演習問題、解答など)にアクセスできます。
会員サービス

ディスカッションに参加しますか?

質問やコメントを投稿するにはログインが必要です。
ログイン

アカウント
ログイン