無限集合を含めた一般の集合について、それらの濃度の大きさを比較する大小関係を定義します。

濃度が超えない 反射律  反対称律  推移律  順序関係

濃度の大小関係

集合の濃度はその集合に含まれる要素の個数を拡張した概念である以上、異なる集合の濃度を比較しようとするのは自然な欲求です。

有限集合どうしの濃度を比較する際には、それらの集合に含まれる要素の個数をそれぞれ数え上げた上で、得られた 2 つの自然数の大小を比較することになります。一方、無限集合には無限個の要素が含まれるため、そこに含まれるすべての要素を数え尽くすことはできません。したがって、無限集合を含む一般の集合どうしの濃度を比較する際には、要素の個数を数える方法とは別のアプローチが必要です。では、具体的にはどのような手法が有効でしょうか。

有限集合\(X\)とその部分集合\(Y\)が与えられたとき、\(Y\)のすべての要素は\(X\)の要素でもあります。\(X\)と\(Y\)はともに有限集合であるため、\(Y\)の要素の個数が\(X\)の要素の個数を超えることはなく、\begin{equation*}
\#Y\leq \#X
\end{equation*}という関係が成り立ちます。ただし、\(X,Y\)はともに有限集合ですので、それらの濃度\(\#Y,\#X\)はいずれも自然数であり、上の式中の\(\leq \)は自然数どうしを比較する通常の大小関係を表す記号です。以上は議論の出発点となるべき疑いようのない事実であり、この考え方を拡張して、無限集合を含めた一般の集合にも適用してみましょう。

無限集合を含めた一般の集合\(X\)とその部分集合\(Y\)の濃度は自然数として定まるとは限らないため、それらの濃度を自然数の大小関係として比較することはできません。そこで、有限集合の場合と同様に、一般の集合\(X\)とその任意の部分集合\(Y\)についても、\(Y\)の濃度は\(X\)の濃度を超えないと定め、このことを\(\#Y\leq \#X\)で表します。つまり、任意の集合\(X,Y\)について、\begin{equation*}
\#Y\leq \#X\ \Leftrightarrow \ Y\subset X
\end{equation*}が成り立つものとして\(\leq \)を定義するということです。ただし、ここでの\(X,Y\)は有限集合とは限らないため、それらの濃度\(\#Y,\#X\)は自然数であるとは限らず、上の式中の\(\leq \)は自然数どうしを比較する通常の大小関係を表す記号ではなく、集合の濃度を比較する記号です。

例(濃度の大小関係)
すべての自然数からなる集合\(\mathbb{N}\)とすべての正の偶数からなる集合\(E\)はともに無限集合であるため、それらの濃度\(\#\mathbb{N} ,\ \#E\)を自然数として表現することはできません。ただし、両者の間には\(E\subset \mathbb{N}\)という包含関係が成り立つため、両者の濃度の間には、\begin{equation*}
\#E\leq \#\mathbb{N}
\end{equation*}という関係が成り立ちます。つまり、\(E\)の濃度は\(\mathbb{N}\)の濃度を超えません。

 

第三の集合を用いた濃度の比較

集合\(X,Y\)の間に\(X\subset Y\)もしくは\(Y\subset X\)などの包含関係が成立する場合には、それらの濃度の大小関係は比較可能です。しかし、集合\(X,Y\)に対して\(X\subset Y\)もしくは\(Y\subset X\)という包含関係は成立するとは限りません。包含関係が成立しない集合\(X,Y\)の濃度を比較するためにはどうすればよいでしょうか。

集合\(X,Y\)の間に包含関係が成立するとは限らない場合でも、\(X\)と濃度が等しい\(Y\)の部分集合が存在するのであれば、つまり、\begin{eqnarray*}
&&\left( a\right) \ \#Z=\#X \\
&&\left( b\right) \ Z\subset Y
\end{eqnarray*}をともに満たす集合\(Z\)を見つけることができるのであれば、\(X\)と\(Y\)の濃度は比較可能です。実際、\(\left( b\right) \)より\(\#Z\leq \#Y\)が成り立ちますが、これと\(\left( a\right) \)より\(\#X\leq \#Y\)が成り立ちます。逆に、集合\(X,Y\)の間に\(\#X\leq \#Y\)が成り立つ場合には、\(X\)と濃度が等しい\(Y\)の部分集合は必ず存在するのでしょうか。\(\#X\leq \#Y\)が成り立つ場合には\(\leq \)の定義より\(X\subset Y\)が成立します。また、対称律より\(\#X=\#X\)が成り立ちます。したがって、この場合には、\(X\)自身が\(X\)と濃度が等しい\(Y\)の部分集合となります。以上の議論の結論をまとめておきます。

命題(濃度の大小関係)
集合\(X,Y\)について、\(X\)と濃度が等しい\(Y\)の部分集合が存在することは、\(\#X\leq \#Y\)が成り立つための必要十分条件である。

 

写像を用いた濃度の大小関係の表現

以前学んだように、単射と全単射の間には以下の関係が成立します。

命題(単射と全単射の関係)
集合\(X,Y\)について、単射\(f:X\rightarrow Y\)が存在することは、部分集合\(Y^{\prime }\subset Y\)と全単射\(f:X\rightarrow Y^{\prime }\)が存在するための必要十分条件である。

先ほど確認したように、集合\(X,Y\)に対して\(Y\)の部分集合\(Y^{\prime }\)と全単射\(f:X\rightarrow Y^{\prime }\)が存在することは、\(\#X\leq \#Y\)が成り立つための必要十分条件ですので、単射と全単射の関係を規定する上の命題を利用すると、濃度の大小関係は以下のように言い換え可能です。

系(単射を用いた濃度の比較)
集合\(X,Y\)について、単射\(f:X\rightarrow Y\)が存在することは、\(\#X\leq \#Y\)が成り立つための必要十分条件である。

また、一般に、単射と全射の間には以下の関係が成立します。

命題(単射と全射の関係)
集合\(X,Y\)について、\(X\)から\(Y\)への単射が存在することは、\(Y\)から\(X\)への全射が存在するための必要十分条件である。ただし、選択公理を認めるものとする。

先ほど確認したように、集合\(X,Y\)に対して単射\(f:X\rightarrow Y\)が存在することは、\(\#X\leq \#Y\)が成り立つための必要十分条件ですので、単射と全射の関係を規定する上の命題を利用すると、濃度の大小関係は以下のように言い換え可能です。

系(全射を用いた濃度の比較)
集合\(X,Y\)について、全射\(g:Y\rightarrow X\)が存在することは、\(\#X\leq \#Y\)が成り立つための必要十分条件である。ただし、選択公理を認めるものとする。

 

濃度の大小関係は順序関係

集合族\(\mathfrak{A}\)に属する集合\(X,Y\)を任意にとると、\(\#X\leq \#Y\)は成り立つか否かのどちらか一方ですので、\(\leq \)は\(\mathfrak{A}\)上の二項関係です。

集合\(X\)を任意に選ぶと、それに対して恒等写像\(I_{X}:X\rightarrow X\)が常に存在します。ただし、\(I_{X}\)が恒等写像であることとは、\begin{equation*}
\forall x\in X:I_{X}\left( x\right) =x
\end{equation*}を満たすことを意味します。これは、入力した\(X\)の要素\(x\)に対して常に同じ要素\(x\)を像として返す写像です。一般に、恒等写像は全単射であるため、\(X\)から\(X\)への全単射が必ず存在することが示されました。したがって\(\#X\leq \#Y\)が成り立ちます。つまり、集合の濃度の大小関係\(\leq \)は反射律(reflexive law)を満たす集合族\(\mathfrak{A}\)上の二項関係です。

命題(反射律)
任意の集合\(X\)について、\begin{equation*}
\#X\leq \#X
\end{equation*}が成り立つ。

\(\#X\leq \#Y\)かつ\(\#Y\leq \#X\)を満たす集合\(X,Y\)を任意に選ぶと、\(\leq \)の定義より、\(X\)から\(Y\)への単射と\(Y\)から\(X\)への単射が存在します。するとシュレーダーシュレーダーの定理より\(X\)から\(Y\)への全単射が存在しますが、これは\(\#X=\#Y\)が成り立つことを意味します。つまり、集合の濃度の大小関係\(\leq \)は反対称律(antisymmetric law)を満たす集合族\(\mathfrak{A}\)上の二項関係です。

命題(反対称律)
任意の集合\(X,Y\)について、\begin{equation*}
\left( \#X\leq \#Y\ \wedge \ \#Y\leq \#X\right) \ \Rightarrow \ \#X=\#Y
\end{equation*}が成り立つ。

\(\#X\leq \#Y\)かつ\(\#Y\leq \#Z\)を満たす集合\(X,Y,Z\)を任意に選ぶと、\(\leq \)の定義より、\(X\)から\(Y\)への単射と\(Y\)から\(Z\)への単射が存在します。一般に、単射どうしの合成写像もまた単射となるため、\(X\)から\(Z\)への単射が存在しますが、これは\(\#X\leq \#Z\)が成り立つことを意味します。つまり、集合の濃度の大小関係\(\leq \)は推移律(transitive law)を満たす集合族\(\mathfrak{A}\)上の二項関係です。

命題(推移律)
任意の集合\(X,Y,Z\)について、\begin{equation*}
\left( \#X\leq \#Y\ \wedge \ \#Y\leq \#Z\right) \ \Rightarrow \ \#X\leq \#Z
\end{equation*}が成り立つ。

反射律・反対称律・推移律を満たす二項関係を順序関係(order relation)と呼びます。濃度の大小関係を表す\(\leq \)を集合族\(\mathfrak{A}\)上に定義された二項関係とみなすとき、これまでの議論により、\(\leq \)は反射律・反対称律・推移律を満たすため、これは順序関係としての要件を満たします。

系(濃度の大小関係は順序関係)
集合族\(\mathfrak{A}\)上の二項関係\(\leq \)を、任意の集合\(X,Y\in \mathfrak{A}\)に対して、\begin{equation*}
\#X\leq \#Y\Leftrightarrow X\text{から}Y\text{への単射が存在する}
\end{equation*}を満たすものとして定義すると、この\(\leq \)は\(\mathfrak{A}\)上の順序関係である。

次回は集合の濃度を比較する狭義順序について学びます。
次へ進む 演習問題(プレミアム会員限定)

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

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

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

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

アカウント
ログイン