等しい濃度を持つ集合
集合\(A\)から集合\(B\)への写像\(f:A\rightarrow B\)が全単射であることとは、\(f\)が単射かつ全射であることとして、すなわち、\begin{eqnarray*}&&\left( a\right) \ \forall a,a^{\prime }\in A:\left[ a\not=a^{\prime
}\Rightarrow f\left( a\right) \not=f\left( a^{\prime }\right) \right] \\
&&\left( b\right) \ \forall b\in B,\ \exists a\in A:b=f\left( a\right)
\end{eqnarray*}がともに成り立つこととして定義されます。
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在する場合には、\(A\)と\(B\)は等しい濃度（same cardinality）を持つと言い、そのことを、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}で表記します。つまり、任意の集合\(A,B\)について、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert \Leftrightarrow \text{全単射}f:A\rightarrow B\text{が存在する}
\end{equation*}という関係を満たすものとして集合の濃度の相等関係\(=\)は定義されるということです。
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在する場合、それは1つだけであるとは限りません。ただ、\(A\)から\(B\)への全単射が存在する場合には、その個数に関わらず、\(\left\vert A\right\vert =\left\vert B\right\vert \)が成り立つものとみなします。言い換えると、\(A\)から\(B\)への全単射がいくつ存在するか分からない場合でも、少なくとも1つ存在することが明らかであれば、\(\left\vert A\right\vert=\left\vert B\right\vert \)が成り立つものとみなすということです。
B &=&\left\{ b_{1},b_{2},b_{3}\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_{2}\right) &=&b_{3}
\end{eqnarray*}を満たすものとして定義する場合、この写像\(f\)は全単射です。実際、始集合の要素\(a_{i},a_{j}\in A\)を任意に選んだとき、\begin{equation*}a_{i}\not=a_{j}\Rightarrow f\left( a_{i}\right) \not=f\left( a_{j}\right)
\end{equation*}が成り立つため\(f\)は単射であり、終集合の要素\(b_{i}\in B\)を任意に選んだとき、それに対して、\begin{equation*}f\left( a_{i}\right) =b_{i}
\end{equation*}を満たす\(a_{i}\in A\)が存在するため\(f\)は全射です。以上より\(f\)は全単射であることが示されたため、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}が成り立ちます。
\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
\end{equation*}を定めるものとします。この\(f\)は全単射です。実際、異なる自然数\(n,n^{\prime }\in \mathbb{N} \)を任意に選んだとき、\begin{eqnarray*}f\left( n\right) &=&2n\quad \because f\text{の定義} \\
&\not=&2n^{\prime }\quad \because n\not=n^{\prime } \\
&=&f\left( n^{\prime }\right) \quad \because f\text{の定義}
\end{eqnarray*}となるため\(f\)は単射です。また、正の偶数\(e\in E\)を任意に選ぶと、正の偶数の定義より\(\frac{e}{2}\in \mathbb{N} \)であるとともに、\begin{eqnarray*}f\left( \frac{e}{2}\right) &=&2\cdot \frac{e}{2}\quad \because f\text{の定義} \\
&=&e \\
&\in &E
\end{eqnarray*}となるため\(f\)は全射です。したがって\(f\)は全単射であるため、\begin{equation*}\left\vert \mathbb{N} \right\vert =\left\vert E\right\vert
\end{equation*}であることが示されました。
等しくない濃度を持つ集合
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全単射が存在しない場合には、\(A\)と\(B\)は等しくない濃度（unequal cardinalities）を持つと言い、そのことを、\begin{equation*}\left\vert A\right\vert \not=\left\vert B\right\vert
\end{equation*}で表記します。つまり、任意の集合\(A,B\)について、\begin{equation*}\left\vert A\right\vert \not=\left\vert B\right\vert \Leftrightarrow \text{全単射}f:A\rightarrow B\text{が存在しない}
\end{equation*}という関係を満たすものとして集合の濃度の非相等関係\(\not=\)は定義されるということです。
B &=&\left\{ b_{1},b_{2}\right\}
\end{eqnarray*}で与えられているものとします。\(A\)の要素の個数は\(B\)の要素の個数よりも多いため、写像\(f:A\rightarrow B\)を任意に選ぶと、\begin{equation*}f\left( a_{i}\right) =f\left( a_{j}\right) \in B
\end{equation*}を満たす\(A\)の異なる要素\(a_{i},a_{j}\)が存在するため\(f\)は単射ではなく、したがって全単射でもありません。\(A\)から\(B\)への任意の写像について同様の議論が成立するため、\(A\)から\(B\)への全単射は存在せず、したがって、\begin{equation*}\left\vert A\right\vert \not=\left\vert B\right\vert
\end{equation*}であることが示されました。
単射を用いた濃度の相等関係の判定
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への単射と、\(B\)から\(A\)への単射がともに存在する場合、\(A\)から\(B\)への全単射が存在することが保証されます（シュレーダー＝ベルンシュタインの定理）。以上の事実を踏まえると、濃度の相等関係に関する以下の命題を得ます。
\end{equation*}が成り立つ。
つまり、\(A\)から\(B\)への全単射を具体的に構成できない場合でも、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射をそれぞれ構成できるのであれば、\(A\)と\(B\)の濃度が等しいことを保証できるということです。
全射を用いた濃度の相等関係の判定
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への全射と、\(B\)から\(A\)への全射がともに存在する場合、選択公理を認めるのであれば、\(A\)から\(B\)への全単射が存在することが保証されます。以上の事実を踏まえると、濃度の相等関係に関する以下の命題を得ます。
\end{equation*}が成り立つ。ただし、選択公理を認めるものとする。
つまり、\(A\)から\(B\)への全単射を具体的に構成できない場合でも、\(A\)から\(B\)への全射と\(B\)から\(A\)への全射をそれぞれ構成できるのであれば、\(A\)と\(B\)の濃度が等しいことを保証できるということです。ただし、先の命題とは異なり、こちらの命題では選択公理が要求されている点に注意してください。
単射と全射を用いた濃度の相等関係の判定
集合\(A,B\)が与えられたとき、\(A\)から\(B\)への単射と、同じく\(A\)から\(B\)への全射がともに存在する場合、選択公理を認めるのであれば、\(A\)から\(B\)への全単射が存在することが保証されます。以上の事実を踏まえると、濃度の相等関係に関する以下の命題を得ます。
\end{equation*}が成り立つ。ただし、選択公理を認めるものとする。
この命題のポイントは、存在が保証されている\(A\)から\(B\)への単射と全射は異なる写像でもよいという点です（それらが同じ写像であるならば、その写像そのものが全単射であることは明らかです）。つまり、\(A\)から\(B\)への全単射を具体的に構成できない場合でも、\(A\)から\(B\)への単射と全射をそれぞれ構成できるのであれば、\(A\)と\(B\)の濃度が等しいことを保証できるということです。この命題でも選択公理が要求されています。
部分集合への全単射を用いた濃度の相等関係の判定
集合\(A,B\)が与えられたとき、\(A\)から\(B\)の部分集合への全単射と、\(B\)から\(A\)の部分集合への全単射がともに存在する場合、\(A\)から\(B\)への全単射が存在することが保証されます。以上の事実を踏まえると、濃度の相等関係に関する以下の命題を得ます。
\end{equation*}が成り立つ。
この命題では選択公理が要求されてないことに注意してください。
濃度の相等関係は同値関係
全体集合\(U\)を任意に選んだ上で、その部分集合どうしの濃度が等しいか判定する状況を想定します。任意の集合\(A,B\in 2^{U}\)について、以下の関係\begin{equation*}\left( A,B\right) \in R\Leftrightarrow \left\vert A\right\vert =\left\vert
B\right\vert
\end{equation*}を満たすものとして\(2^{U}\)上の二項関係\begin{equation*}R\subset 2^{U}\times 2^{U}
\end{equation*}を定義します。ただし、\(2^{U}\)は\(U\)のべき集合、すなわち\(U\)のすべての部分集合を要素として持つ集合族です。つまり、\(U\)の部分集合\(A,B\)について、\(A\)と\(B\)が等しい濃度を持つ場合、そしてその場合にのみ\(\left( A,B\right) \in R\)が成り立つものとして\(2^{U}\)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を濃度の相等関係\(=\)と同一視することにより、濃度の相等関係\(=\)を\(2^{U}\)上の二項関係とみなすことができます。では、濃度の相等関係\(=\)はどのような性質を満たす二項関係でしょうか。
集合\(U\)のべき集合\(2^{U}\)上に定義された濃度の相等関係\(=\)は\(2^{U}\)上の同値関係です。つまり、\(=\)は反射律、対称律、推移律に相当する以下の性質\begin{eqnarray*}&&\left( E_{1}\right) \ \forall A\in 2^{U}:\left\vert A\right\vert
=\left\vert A\right\vert \\
&&\left( E_{2}\right) \ \forall A,B\in 2^{U}:\left( \left\vert A\right\vert
=\left\vert B\right\vert \Rightarrow \left\vert B\right\vert =\left\vert
A\right\vert \right) \\
&&\left( E_{3}\right) \ \forall A,B,C\in 2^{U}:\left[ \left( \left\vert
A\right\vert =\left\vert B\right\vert \wedge \left\vert B\right\vert
=\left\vert C\right\vert \right) \Rightarrow \left\vert A\right\vert
=\left\vert C\right\vert \right]
\end{eqnarray*}を満たします。
反射律\(\left( E_{1}\right) \)は、任意の集合\(A\)の濃度は自身\(A\)の濃度と一致することを意味します。つまり、\(A\)から\(A\)自身への全単射が必ず存在するということです。
対称律\(\left( E_{2}\right) \)は、集合\(A,B\)を任意に選んだとき、\(A\)と\(B\)の濃度が等しい場合には、\(B\)と\(A\)の濃度も等しいことが保証されることを意味します。つまり、\(A\)から\(B\)への全単射が存在する場合には、\(B\)から\(A\)への全単射が存在することも保証されるということです。
推移律\(\left( E_{3}\right) \)は、集合\(A,B,C\)を任意に選んだとき、\(A\)と\(B\)の濃度が等しく、\(B\)と\(C\)の濃度が等しい場合には、\(A\)と\(C\)の濃度が一致することが保証されることを意味します。つまり、\(A\)から\(B\)への全単射と\(B\)から\(C\)への全単射がともに存在する場合には、\(A\)から\(C\)への全単射が存在することが保証されるということです。
濃度の相等関係\(=\)は同値関係であるため、集合\(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\)と等しい濃度を持つ集合を要素とする集合族です。さらに、\(2^{U}\)の\(=\)による商集合が、\begin{equation*}2^{U}\backslash ==\left\{ \left[ A\right] \ |\ A\in 2^{U}\right\}
\end{equation*}と定義されますが、商集合の性質より、これは\(2^{U}\)の分割です。つまり、「等しい濃度を持つ」という基準から\(U\)の部分集合を複数のグループに分類したとき、それぞれの部分集合は何らかのグループに属するとともに、異なる複数のグループに属する部分集合が存在しないことが保証されます。
演習問題
B &=&\left\{ x\in \mathbb{Z} \ |\ -5\leq x\leq 0\right\}
\end{eqnarray*}と定義されています。ただし、\(\mathbb{Z} \)はすべての整数からなる集合です。このとき、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}が成り立つことを証明してください。
\end{equation*}という関係が成り立つことを証明してください。
\end{equation*}が成り立つことを証明してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】