濃度の狭義大小関係
全体集合\(U\)のベキ集合を\(2^{U}\)で表記します。任意の集合\(A,B\in 2^{U}\)に対して、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert \Leftrightarrow \text{全単射}f:A\rightarrow B\text{が存在する}
\end{equation*}を満たすものとして集合の濃度の相等関係\(=\)を定義し、任意の集合\(A,B\in 2^{U}\)に対して、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert \Leftrightarrow \text{単射}f:A\rightarrow B\text{が存在する}
\end{equation*}を満たすものとして集合の濃度の大小関係\(\leq \)を定義しました。ただし、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つ場合には2つの可能性があります。1つは\(A\)と\(B\)の濃度が等しい場合であり、もう1つは\(A\)の濃度が\(B\)の濃度より狭義に小さい場合です。そこで、この2つのケースを区別するために、任意の集合\(A,B\in 2^{U}\)に対して、\begin{equation*}\left\vert A\right\vert <\left\vert B\right\vert \Leftrightarrow \left\vert
A\right\vert \leq \left\vert B\right\vert \wedge \left\vert A\right\vert
\not=\left\vert B\right\vert
\end{equation*}を満たすものとして集合の濃度の狭義大小関係\(<\)を定義します。その上で、集合\(A,B\)に関して\(\left\vert A\right\vert <\left\vert B\right\vert \)が成り立つ場合、\(A\)の濃度は\(B\)の濃度よりも小さい（less than）とか、\(B\)の濃度は\(A\)の濃度よりも大きい（greater than）などと言います。つまり、\(A\)の濃度が\(B\)の濃度以下であるとともに両者の濃度が異なる場合、そしてその場合にのみ\(A\)の濃度が\(B\)の濃度よりも小さいものと定めます。言い換えると、\(A\)から\(B\)への単射が存在する一方で全単射が存在しない場合、そしてその場合にのみ\(A\)の濃度が\(B\)の濃度よりも小さいものと定めるということです。
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*}と定義します。\(f\)は単射であるため、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立ちます。その一方で、\(B\)の要素の個数は\(A\)の要素の個数よりも多いため、写像\(g:A\rightarrow B\)を任意に選ぶと、少なくとも1つの\(b\in B\)に対して\(b=g\left( a\right) \)を満たす\(a\in A\)は存在しないため\(g\)は全射ではなく、したがって全単射ではありません。つまり、\(A\)から\(B\)への全単射が存在しないため、\begin{equation*}\left\vert A\right\vert \not=\left\vert B\right\vert
\end{equation*}が成り立ちます。以上より、\begin{equation*}
\left\vert A\right\vert <\left\vert B\right\vert
\end{equation*}であることが示されました。
集合\(A\)が集合\(B\)の真部分集合であったとしても、\(A\)の濃度は\(B\)の濃度よりも小さいとは限りません。以下の例より明らかです。
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow E\)を構成します。これは全単射であるため、\begin{equation*}\left\vert E\right\vert =\left\vert \mathbb{N} \right\vert
\end{equation*}が成り立ち、したがって、\begin{equation*}
\left\vert E\right\vert <\left\vert \mathbb{N} \right\vert
\end{equation*}は成り立ちません。
\end{equation*}を構成します。空写像は単射であるため、\begin{equation*}
\left\vert \phi \right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立ちます。その一方、\(A\)は非空であるため\(\phi \)と\(A\)への全射は存在せず、ゆえに、\begin{equation*}\left\vert \phi \right\vert \not=\left\vert A\right\vert
\end{equation*}です。以上より、\begin{equation*}
\left\vert \phi \right\vert <\left\vert A\right\vert
\end{equation*}であることが示されました。つまり、空集合の濃度は任意の非空集合の濃度よりも小さいです。
集合\(A,B\)について\(\left\vert A\right\vert \leq \left\vert B\right\vert \)または\(\left\vert A\right\vert \not=\left\vert B\right\vert \)の少なくとも一方が成り立たない場合、すなわち、\(A\)から\(B\)への単射が存在しないか、\(A\)から\(B\)への全単射が存在するか、少なくともその一方が成り立つ場合には\(\left\vert A\right\vert <\left\vert B\right\vert \)は成り立ちません。
\end{equation*}と正の偶数集合\begin{equation*}
E=\left\{ 2,4,\cdots \right\}
\end{equation*}が与えられているものとします。写像\(f:\mathbb{N} \rightarrow E\)はそれぞれの\(n\in \mathbb{N} \)に対して、\begin{equation*}f\left( n\right) =2n\in E
\end{equation*}を定めるものとします。この\(f\)は全単射であるため\(\left\vert \mathbb{N} \right\vert =\left\vert E\right\vert \)が成り立ちます。したがって\(\left\vert \mathbb{N} \right\vert <\left\vert E\right\vert \)や\(\left\vert E\right\vert<\left\vert \mathbb{N} \right\vert \)は成り立ちません。
写像を用いた濃度の狭義大小関係の判定
濃度の狭義大小関係の定義を写像を用いて表現すると以下のようになります。
シュレーダー＝ベルンシュタインの定理を用いると、先の命題を以下のように言い換えることもできます。
選択公理を認める場合、集合\(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\)は全射です。その一方で、\(A\)の要素の個数は\(B\)の要素の個数よりも少ないため、写像\(g:B\rightarrow A\)を任意に選ぶと、少なくとも2つの異なる要素\(b_{i},b_{j}\in B\)に対して\(g\left( b_{i}\right) =g\left( b_{j}\right) \)となり、したがって\(g\)は単射ではなく、ゆえに全単射でもありません。つまり、\(B\)から\(A\)への全単射は存在しないため、先の命題より\(\left\vert A\right\vert <\left\vert B\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] \prec \left[ B\right] \Leftrightarrow \left\vert
A\right\vert <\left\vert B\right\vert
\end{equation*}を満たすものとして\(2^{U}/\sim \)上の二項関係\(\prec \)を定義します。つまり、同値類\(\left[ A\right] ,\left[ B\right] \)について、\(\left[ A\right] \)の代表元\(A\)の濃度が\(\left[ B\right] \)の代表元\(B\)の濃度より小さい場合、そしてその場合にのみ\(\left[ A\right] \prec \left[ B\right] \)が成り立つものとして商集合\(2^{U}/\sim \)上の二項関係\(\prec \)を定義するということです。この定義は代表元の選び方に依存しないため、商集合上の二項関係としてきちんと定義されていることに注意してください。この二項関係\(\prec \)を濃度の狭義大小関係\(<\)と同一視することにより、濃度の狭義大小関係を商集合\(2^{U}/\sim \)上の二項関係とみなすことができます。では、濃度の大小関係はどのような性質を満たす二項関係でしょうか。
選択公理を認める場合、商集合\(2^{U}/\sim \)上に定義された濃度の狭義大小関係は狭義全順序関係です。つまり、非対称律、推移律、三分律に相当する以下の性質\begin{eqnarray*}&&\left( S_{1}\right) \ \forall a,b\in 2^{U}/\sim :\left[ a\prec
b\Rightarrow \lnot \left( b\prec a\right) \right] \\
&&\left( S_{2}\right) \ \forall a,b,c\in 2^{U}/\sim :\left[ \left( a\prec
b\wedge b\prec c\right) \Rightarrow a\prec c\right] \\
&&\left( S_{3}\right) \ \forall a,b\in 2^{U}/\sim :a\prec b,b\prec a,a=b\text{の中の1つだけが成り立つ}
\end{eqnarray*}を満たします。
b\Rightarrow \lnot \left( b\prec a\right) \right] \\
&&\left( S_{2}\right) \ \forall a,b,c\in 2^{U}/\sim :\left[ \left( a\prec
b\wedge b\prec c\right) \Rightarrow a\prec c\right] \\
&&\left( S_{3}\right) \ \forall a,b\in 2^{U}/\sim :a\prec b,b\prec a,a=b\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立つ。ただし、\(\left( S_{3}\right) \)については選択公理を認めるものとする。
先の命題では、濃度の狭義大小関係をベキ集合\(2^{U}\)上の二項関係として定義するのではなく、商集合\(2^{U}/\sim \)上の二項関係としてわざわざ定義しましたが、その理由は以下の通りです。
\end{equation*}を満たすものとして濃度の狭義大小関係\(\precsim \)を\(2^{U}\)上の二項関係として定義した状況を想定します。仮に、\begin{eqnarray*}A &=&\left\{ 1,2\right\} \\
B &=&\left\{ a,b\right\}
\end{eqnarray*}であれば、\(A\)から\(B\)への全単射が存在するため、\begin{eqnarray*}A &\prec &B \\
B &\prec &A
\end{eqnarray*}がともに成り立ちません。さらに、\begin{equation*}
A=B
\end{equation*}も成り立たないため三分律は成り立ちません。一方、濃度の狭義大小関係\(\prec \)を商集合\(2^{U}/\sim \)上の二項関係とみなした場合には、\begin{eqnarray*}\left[ A\right] &\prec &\left[ B\right] \\
\left[ B\right] &\prec &\left[ A\right] \end{eqnarray*}がともに成り立たない一方で、\begin{equation*}
\left[ A\right] =\left[ B\right] \end{equation*}が成り立つため、三分律と整合的です。
演習問題
A\right\vert <\left\vert B\right\vert
\end{equation*}を満たすものとして\(2^{U}/\sim \)上の二項関係\(\prec \)を定義します。この関係が代表元の選び方に依存しないことを証明してください。
A\times C\right\vert \leq \left\vert B\times C\right\vert
\end{equation*}が常に成り立つことはすでに示した通りです。では、\begin{equation*}
\left\vert A\right\vert <\left\vert B\right\vert \Rightarrow \left\vert
A\times C\right\vert <\left\vert B\times C\right\vert
\end{equation*}もまた常に成り立つでしょうか。成り立つ場合には証明し、成り立たない場合には凡例を提示してください。
ログイン
会員向けコンテンツです。
まだ会員登録がお済みでない方は、会員登録ページよりアカウントを作成してください。