濃度の大小関係
前節では、2つの集合の間に全単射が存在する場合、それらの集合は等しい濃度を持つと定義しました。では、2つの集合の濃度が等しくない場合には、どちらの濃度がより大きいかをどのように比較すればよいでしょうか。集合\(A\)の各要素を、重複することなく集合\(B\)の要素へ対応させることができる、すなわち\(A\)から\(B\)への単射が存在する場合には、\(A\)は\(B\)の中に収まると考えることができます。この考え方にもとづいて濃度の大小関係を定義します。本節では、単射を用いた濃度の大小関係の定義から始め、全射や部分集合への全単射を用いた判定方法を明らかにします。その上で、濃度の大小関係がどのような順序構造を持つかを考察します。
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への単射が存在する場合には、\(A\)の濃度は\(B\)の濃度以下である(less than or equalto)と言い、そのことを、\begin{equation*}
\left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}で表記します。つまり、任意の集合\(A,B\)について、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert \Leftrightarrow \text{単射}f:A\rightarrow B\text{が存在する}
\end{equation*}という関係を満たすものとして集合の濃度の大小関係\(\leq \)は定義されるということです。
集合\(A,B\)について\(\left\vert A\right\vert \leq \left\vert B\right\vert \)が成り立つ場合、そのことを\(B\)の濃度は\(A\)の濃度以上である(greater than or equal to)とか、\(A\)の濃度は\(B\)の濃度を超えない(notgreater than)、\(B\)の濃度は\(A\)の濃度を下回らない(not less than)などと言うこともできます。
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への単射が存在する場合、それは1つだけであるとは限りません。ただ、\(A\)から\(B\)への単射が存在する場合には、その個数に関わらず\(\left\vert A\right\vert \leq \left\vert B\right\vert \)が成り立つものとみなします。言い換えると、\(A\)から\(B\)への単射がいくつ存在するか分からない場合でも、少なくとも1つ存在することが明らかであれば\(\left\vert A\right\vert \leq \left\vert B\right\vert \)が成り立つものとみなすということです。
B &=&\left\{ b_{1},b_{2},b_{3},b_{4}\right\}
\end{eqnarray*}で与えられているものとします。写像\(f:A\rightarrow B\)が、\begin{eqnarray*}f\left( a_{1}\right) &=&b_{1} \\
f\left( a_{2}\right) &=&b_{2} \\
f\left( a_{3}\right) &=&b_{3}
\end{eqnarray*}と定義されているものとします。始集合の要素\(a_{i},a_{j}\in A\)を任意に選んだとき、\(f\)の定義より、\begin{equation*}a_{i}\not=a_{j}\Rightarrow f\left( a_{i}\right) \not=f\left( a_{j}\right)
\end{equation*}が成り立つため\(f\)は単射です。したがって、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つことが明らかになりました。
\end{equation*}とすべての正の偶数からなる集合\begin{equation*}
E=\left\{ 2,4,\cdots \right\}
\end{equation*}が与えられているものとします。\(E\subset \mathbb{N} \)が成り立つため、それぞれの\(e\in E\)に対して、\begin{equation*}f\left( e\right) =e\in \mathbb{N} \end{equation*}を定める写像\(f:E\rightarrow \mathbb{N} \)が定義可能です。さらに、正の偶数\(e,e^{\prime }\in E\)を任意に選んだとき、\(f\)の定義より、\begin{equation*}e\not=e^{\prime }\Rightarrow f\left( e\right) \not=f\left( e^{\prime }\right)
\end{equation*}が成り立つため\(f\)は単射です。したがって、\begin{equation*}\left\vert E\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つことが明らかになりました。
}\right)
\end{equation*}が成り立つため\(f\)は単射です。したがって、\begin{equation*}\left\vert \mathbb{N} _{n}\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つことが明らかになりました。
集合\(A,B\)について\(A\)から\(B\)への単射が存在しない場合には\(\left\vert A\right\vert \leq\left\vert B\right\vert \)は成り立ちません。
B &=&\left\{ b_{1},b_{2},b_{3},b_{4}\right\}
\end{eqnarray*}で与えられているものとします。\(A\)の要素の個数は\(B\)の要素の個数よりも少ないため、写像\(f:B\rightarrow A\)を任意に選んだとき、少なくとも2つの異なる要素\(b_{i},b_{j}\in B\)について\(f\left( b_{i}\right)=f\left( b_{j}\right) \)が成り立つため、\(f\)は単射ではありません。つまり、\(B\)から\(A\)への単射は存在しないため\(\left\vert B\right\vert \leq \left\vert A\right\vert \)は成り立ちません。
全射を用いた濃度の大小関係の判定
選択公理を認める場合、集合\(A,B\)について\(A\)から\(B\)への単射が存在することと、\(B\)から\(A\)への全射が存在することは必要十分です。以上の事実を踏まえると濃度の大小関係に関する以下の命題を得ます。
集合\(A\)の濃度が集合\(B\)の濃度以下であることを示すためには、\(A\)から\(B\)への単射が存在することを示す代わりに、\(B\)から\(A\)への全射が存在することを示してもよいということです。
B &=&\left\{ b_{1},b_{2},b_{3},b_{4}\right\}
\end{eqnarray*}で与えられているものとします。写像\(f:B\rightarrow A\)が、\begin{eqnarray*}f\left( b_{1}\right) &=&a_{1} \\
f\left( b_{2}\right) &=&a_{2} \\
f\left( b_{3}\right) &=&a_{3} \\
f\left( b_{4}\right) &=&a_{3}
\end{eqnarray*}と定義されているものとします。\(f\)は全射であるため先の命題より、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つことが明らかになりました。
\end{equation*}とすべての正の偶数からなる集合\begin{equation*}
E=\left\{ 2,4,\cdots \right\}
\end{equation*}が与えられているものとします。\(E\subset \mathbb{N} \)が成り立つことを踏まえた上で、それぞれの\(n\in \mathbb{N} \)に対して、\begin{equation*}f\left( n\right) =\left\{
\begin{array}{cc}
n & \left( if\ n\in E\right) \\
2 & \left( if\ n\not\in E\right)\end{array}\right.
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow E\)を定義します。\(f\)は全射であるため先の命題より、\begin{equation*}\left\vert E\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つことが明らかになりました。
\begin{array}{cc}
x & \left( if\ x\in \mathbb{N} _{n}\right) \\
1 & \left( if\ x\not\in \mathbb{N} _{n}\right)\end{array}\right.
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow \mathbb{N} _{n}\)を定義します。\(f\)は全射であるため先の命題より、\begin{equation*}\left\vert \mathbb{N} _{n}\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つことが明らかになりました。
先の命題より、集合\(A,B\)について\(B\)から\(A\)への全射が存在しない場合には\(\left\vert A\right\vert \leq \left\vert B\right\vert \)は成り立ちません。
B &=&\left\{ b_{1},b_{2},b_{3},b_{4}\right\}
\end{eqnarray*}で与えられているものとします。\(A\)の要素の個数は\(B\)の要素の個数よりも少ないため、写像\(f:A\rightarrow B\)を任意に選んだとき、少なくとも1つの要素\(b_{i}\in B\)に対して\(b_{i}=f\left( a_{j}\right) \)を満たす\(a_{j}\in A\)が存在せず、したがって\(f\)は全射ではありません。つまり、\(A\)から\(B\)への全射は存在しないため、先の命題より\(\left\vert B\right\vert \leq \left\vert A\right\vert \)は成り立ちません。
全単射を用いた濃度の大小関係の判定
集合\(A,B\)について\(A\)から\(B\)への単射が存在することと、\(A\)から\(B\)の部分集合への全単射が存在することは必要十分です。以上の事実を踏まえると濃度の大小関係に関する以下の命題を得ます。
B &=&\left\{ a_{1},a_{2},a_{3},a_{4}\right\}
\end{eqnarray*}で与えられているものとします。\(A\subset B\)であることを踏まえた上で、それぞれの\(a\in A\)に対して、\begin{equation*}f\left( a\right) =a
\end{equation*}を定める写像\(f:A\rightarrow A\)を定義します。\(f\)は全単射であるため先の命題より、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つことが明らかになりました。
\end{equation*}とすべての正の偶数からなる集合\begin{equation*}
E=\left\{ 2,4,\cdots \right\}
\end{equation*}が与えられているものとします。\(E\subset \mathbb{N} \)が成り立つことを踏まえた上で、それぞれの\(e\in E\)に対して、\begin{equation*}f\left( e\right) =e
\end{equation*}を定める写像\(f:E\rightarrow E\)を定義します。\(f\)は全単射であるため先の命題より、\begin{equation*}\left\vert E\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つことが明らかになりました。
\end{equation*}を定める写像\(f:\mathbb{N} _{n}\rightarrow \mathbb{N} _{n}\)を定義します。\(f\)は全単射であるため先の命題より、\begin{equation*}\left\vert \mathbb{N} _{n}\right\vert \leq \left\vert \mathbb{N} \right\vert
\end{equation*}が成り立つことが明らかになりました。
先の命題より、集合\(A,B\)について、\(A\)と等しい濃度を持つ\(B\)の部分集合が存在しない場合には\(\left\vert A\right\vert \leq \left\vert B\right\vert \)は成り立ちません。
B &=&\left\{ b_{1},b_{2},b_{3},b_{4}\right\}
\end{eqnarray*}で与えられているものとします。\(A\)の要素の個数は\(B\)の要素の個数よりも少ないため、\(A\)の部分集合\(A^{\prime }\)を任意に選んだ上で写像\(f:B\rightarrow A^{\prime }\)を定義すると、少なくとも2つの異なる\(b_{i},b_{j}\in B\)に対して\(f\left( b_{i}\right) =f\left( b_{j}\right) \)となるため\(f\)は単射ではなく、したがって全単射でもありません。つまり、\(B\)から\(A\)の部分集合への全単射は存在しないため、先の命題より\(\left\vert B\right\vert \leq \left\vert A\right\vert \)は成り立ちません。
濃度の大小関係は全順序関係
全体集合\(U\)を選んだ上で、その部分集合どうしの濃度を比較する状況を想定します。\(U\)の任意の部分集合\(A,B\in 2^{U}\)について、以下の関係\begin{equation*}A\sim B\Leftrightarrow \left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}を満たすものとして\(2^{U}\)上の二項関係\(\sim \)を定義すれば、これは\(2^{U}\)上の同値関係です。つまり、濃度の相等関係は\(2^{U}\)上の同値関係であるため、商集合\(2^{U}/\sim \)を考えることができます。集合\(A\in 2^{U}\)を代表元とする同値類は、\begin{equation*}\left[ A\right] =\left\{ B\in 2^{U}\ |\ \left\vert A\right\vert =\left\vert
B\right\vert \right\}
\end{equation*}ですが、これは\(A\)と同じ濃度を持つ集合からなる集合族です。そこで、この同値類\(\left[ A\right] \)を\(A\)の濃度を表す対象とみなせます。その上で、任意の同値類\(\left[ A\right] ,\left[ B\right] \in 2^{U}/\sim \)に対して、以下の関係\begin{equation*}\left[ A\right] \precsim \left[ B\right] \Leftrightarrow \left\vert
A\right\vert \leq \left\vert B\right\vert
\end{equation*}を満たすものとして\(2^{U}/\sim \)上の二項関係\(\precsim\)を定義します。つまり、同値類\(\left[ A\right] ,\left[ B\right] \)について、\(\left[ A\right] \)の代表元\(A\)の濃度が\(\left[ B\right] \)の代表元\(B\)の濃度以下である場合、そしてその場合にのみ\(\left[ A\right] \precsim \left[ B\right] \)が成り立つものとして商集合\(2^{U}/\sim \)上の二項関係\(\precsim \)を定義するということです。この定義は代表元の選び方に依存しないため、商集合上の二項関係としてきちんと定義されていることに注意してください。この二項関係\(\precsim \)を濃度の大小関係\(\leq \)と同一視することにより、濃度の大小関係を商集合\(2^{U}/\sim \)上の二項関係とみなすことができます。では、濃度の大小関係はどのような性質を満たす二項関係でしょうか。
選択公理を認める場合、商集合\(2^{U}/\sim \)上に定義された濃度の大小関係は全順序関係です。つまり、反射律、反対称律、推移律、完備律に相当する以下の性質\begin{eqnarray*}&&\left( O_{1}\right) \ \forall a\in 2^{U}/\sim :a\precsim a \\
&&\left( O_{2}\right) \ \forall a,b\in 2^{U}/\sim :\left[ \left( a\precsim
b\wedge b\precsim a\right) \Rightarrow a=b\right] \\
&&\left( O_{3}\right) \ \forall a,b,c\in 2^{U}/\sim :\left[ \left( a\precsim
b\wedge b\precsim c\right) \Rightarrow a\precsim c\right] \\
&&\left( O_{4}\right) \ \forall a,b\in 2^{U}/\sim :a\precsim b\vee b\precsim
a
\end{eqnarray*}を満たします。
反射律\(\left( O_{1}\right) \)は、任意の集合\(A\)について\(A\)から\(A\)への単射が必ず存在するということを意味します。
反対称律\(\left( O_{2}\right) \)は、任意の集合\(A,B\)について、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射が存在する場合、\(A\)から\(B\)への全単射が存在することを意味します。
推移律\(\left( O_{3}\right) \)は、任意の集合\(A,B,C\)について、\(A\)から\(B\)への単射と\(B\)から\(C\)への単射が存在する場合、\(A\)から\(C\)への単射が存在することを意味します。
完備律\(\left( O_{4}\right) \)は、任意の集合\(A,B\)について、\(A\)から\(B\)への単射か\(B\)から\(A\)への単射の少なくとも一方が存在することを意味します。
&&\left( O_{2}\right) \ \forall a,b\in 2^{U}/\sim :\left[ \left( a\precsim
b\wedge b\precsim a\right) \Rightarrow a=b\right] \\
&&\left( O_{3}\right) \ \forall a,b,c\in 2^{U}/\sim :\left[ \left( a\precsim
b\wedge b\precsim c\right) \Rightarrow a\precsim c\right] \\
&&\left( O_{4}\right) \ \forall a,b\in 2^{U}/\sim :a\precsim b\vee b\precsim
a
\end{eqnarray*}が成り立つ。ただし、\(\left( O_{4}\right) \)については選択公理を認めるものとする。
先の命題では、濃度の大小関係をベキ集合\(2^{U}\)上の二項関係として定義するのではなく、商集合\(2^{U}/\sim \)上の二項関係としてわざわざ定義しましたが、その理由は以下の通りです。
B\right\vert
\end{equation*}を満たすものとして濃度の大小関係\(\precsim \)を\(2^{U}\)上の二項関係として定義した状況を想定します。仮に、\begin{eqnarray*}A &=&\left\{ 1,2\right\} \\
B &=&\left\{ a,b\right\}
\end{eqnarray*}であれば、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射を構成できるため、\begin{eqnarray*}A &\precsim &B \\
B &\precsim &A
\end{eqnarray*}がともに成り立ちます。その一方で、\begin{equation*}
A\not=B
\end{equation*}であるため、反対称律は成り立ちません。一方、濃度の大小関係\(\precsim \)を商集合\(2^{U}\backslash\sim \)上の二項関係とみなした場合には、\begin{eqnarray*}\left[ A\right] &\precsim &\left[ B\right] \\
\left[ B\right] &\precsim &\left[ A\right] \\
\left[ A\right] &=&\left[ B\right] \end{eqnarray*}がいずれも成り立つため、反対称律と整合的です。
演習問題
\end{equation*}が成り立つことを証明してください。
\end{equation*}が成り立つ場合には、\begin{equation*}
\left\vert A\times C\right\vert \leq \left\vert B\times C\right\vert
\end{equation*}もまた成り立つことを証明してください。
\end{equation*}が成り立つことを証明してください。
\end{equation*}は成り立つとは限らないことを示す反例を、\(A,B\)が有限集合であるケースと、\(A,B\)が無限集合であるケースのそれぞれについて提示してください。
\end{equation*}が成り立つ場合には、それに対して以下の条件\begin{eqnarray*}
\left( a\right) \ m &=&\left\vert A\right\vert \\
\left( b\right) \ n &=&\left\vert B\right\vert \\
\left( c\right) \ A &\subset &B
\end{eqnarray*}を満たす集合\(A,B\)が存在することを証明してください。
\end{equation*}が成り立つことを証明してください。
\end{equation*}が成り立つ場合には、\begin{equation*}
\left\vert 2^{A}\right\vert \leq \left\vert 2^{B}\right\vert
\end{equation*}もまた成り立つことを証明してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。