2 つの集合の間に全単射が存在する場合には、それらの集合の濃度は等しいと言います。集合の濃度が等しいことを二項関係と解釈したとき、これは反射律・対称律・推移律を満たす同値関係です。

集合の濃度

集合\(X,Y\)に対して、\(X\)から\(Y\)への全単射が少なくとも 1 つ存在するならば、つまり、\begin{eqnarray*}
&&\left( a\right) \ \forall x,x^{\prime }\in X:\left[ x\not=x\ \Rightarrow \
f\left( x\right) \not=f\left( x^{\prime }\right) \right] \\
&&\left( b\right) \ \forall y\in Y,\ \exists x\in X:y=f\left( x\right)
\end{eqnarray*}を満たす写像\(f:X\rightarrow Y\)が存在する場合には、\(X\)と\(Y\)は対等(equipotent)であると言い、このことを、\begin{equation*}
X\sim Y
\end{equation*}で表します。これは、\(Y\)のそれぞれの要素\(y\)に対して、\(y=f\left( x\right) \)を満たす一意的な\(X\)の要素\(x\)の存在を保証できる写像\(f\)が存在するということです。

全単射について復習する

集合\(X,Y\)が対等である場合には、\(X\)と\(Y\)の濃度(potency)が等しいといい、このことを、\begin{equation*}
\#X=\#Y
\end{equation*}で表します。つまり、任意の集合\(X,Y\)について、\begin{equation*}
\#X=\#Y\ \Leftrightarrow \ X\sim Y
\end{equation*}を満たすものとして、集合どうしの濃度が等しいことを定義するということです。

例(集合の濃度)
集合\(X=\{x_{1},x_{2},x_{3}\}\)と集合\(Y=\{y_{1},y_{2},y_{3}\}\)について考えます。写像\(f:X\rightarrow Y\)を、\begin{eqnarray*}
f\left( x_{1}\right) &=&y_{1} \\
f\left( x_{2}\right) &=&y_{2} \\
f\left( x_{3}\right) &=&y_{3}
\end{eqnarray*}を満たすものとして定義すると、この\(f\)は明らかに全単射であるため\(X\sim Y\)すなわち\(\#X=\#Y\)が成り立ちます。続いて、集合\(Z=\{z_{1},z_{2}\}\)について考えます。\(X\)の要素の個数は\(Z\)の要素の個数よりも多いため、写像\(g:X\rightarrow Z\)を任意にとると、\(g\left( x_{i}\right) =g\left( x_{j}\right) \in Z\)を満たす\(X\)の異なる要素\(x_{i},x_{j}\)が必ず存在します。つまり、\(g\)は単射ではないため、全単射でもありません。したがって、\(X\sim Z\)すなわち\(\#X=\#Z\)は成り立ちません。
例(集合の濃度)
すべての自然数からなる集合\(\mathbb{N} =\{1,2,\cdots \}\)と、すべての正の偶数からなる集合\(E=\{2,4,\cdots \}\)が与えられたとき、それぞれの\(n\in \mathbb{N} \)に対して、\begin{equation*}
f\left( n\right) =2n\in E
\end{equation*}を定める写像\(f:\mathbb{N} \rightarrow E\)を構成します。異なる自然数\(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\)は全単射であり、\(\mathbb{N} \sim E\)すなわち\(\#\mathbb{N} =\#E\)が成り立ちます。

 

同値関係としての濃度

すべての集合を要素とする集合族\(\mathfrak{A}\)に属する集合\(X,Y\)を任意にとると、全単射\(f:X\rightarrow Y\)は存在するか否かのどちらか一方です。つまり、\(\#X=\#Y\)は成り立つか否かのどちらか一方であるため、集合の濃度が等しいことを表す\(=\)は\(\mathfrak{A}\)上の二項関係です。

二項関係について復習する

集合\(X\in \mathfrak{A}\)を任意に選ぶと、それに対して恒等写像\(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=\#X\)が成り立ちます。つまり、集合の濃度が等しいことを表す\(=\)は反射律(reflexive law)を満たします。任意の集合\(X\)について、その濃度は\(X\)自身の濃度と等しいということです。

恒等写像について復習する
命題(反射律)
任意の集合\(X\)について、\begin{equation*}
\#X=\#X
\end{equation*}が成り立つ。
証明を見る(プレミアム会員限定)

\(\#X=\#Y\)を満たす集合\(X,Y\in \mathfrak{A}\)を任意に選びます。これは全単射\(f:X\rightarrow Y\)が存在することを意味します。一般に、全単射\(f\)には逆写像\(f^{-1}:Y\rightarrow X\)が存在し、なおかつ\(f^{-1}\)もまた全単射となるため、\(Y\)から\(X\)への全単射が存在することが示されました。したがって\(\#Y=\#X\)が成り立ちます。つまり、集合の濃度が等しいことを表す\(=\)は対称律(symmetric law)を満たします。任意の集合\(X,Y\)について、\(X\)の濃度と\(Y\)の濃度が等しければ、\(Y\)の濃度と\(X\)の濃度は等しいということです。

逆写像について復習する
命題(対称律)
任意の集合\(X,Y\)について、\begin{equation*}
\#X=\#Y\ \Rightarrow \ \#Y=\#X
\end{equation*}が成り立つ。
証明を見る(プレミアム会員限定)

\(\#X=\#Y\)かつ\(\#Y=\#Z\)を満たす集合\(X,Y,Z\in \mathfrak{A}\)を任意に選びます。これは全単射\(f:X\rightarrow Y,\ g:Y\rightarrow Z\)が存在することを意味します。これらの写像から合成写像\(g\circ f:X\rightarrow Z\)を構成できますが、一般に、全単射どうしの合成写像もまた全単射となるため、\(X\)から\(Z\)への全単射が存在することが示されました。したがって\(\#X=\#Z\)が成り立ちます。つまり、集合の濃度が等しいことを表す\(=\)は推移律(transitive law)を満たします。任意の集合\(X,Y,Z\)について、\(X\)の濃度と\(Y\)の濃度が等しく、かつ\(Y\)の濃度と\(Z\)の濃度が等しい場合には、\(X\)の濃度と\(Z\)の濃度が等しくなるということです。

合成写像について復習する
命題(推移律)
任意の集合\(X,Y\)について、\begin{equation*}
\left( \#X=\#Y\ \wedge \ \#Y=\#Z\right) \ \Rightarrow \ \#X=\#Z
\end{equation*}が成り立つ。
証明を見る(プレミアム会員限定)

一般に、反射律・対称律・推移律を満たす二項関係を同値関係(equivalence relation)と呼びます。集合の濃度が等しいことを表す\(=\)を集合族\(\mathfrak{A}\)上に定義された二項関係とみなすとき、これまでの議論により、\(=\)は反射律・対称律・推移律を満たすため、\(=\)は同値関係です。

同値関係について復習する
系(濃度の相等関係は同値関係)
すべての集合を要素とする集合族\(\mathfrak{A}\)上の二項関係\(=\)を、それぞれの順序対\(\left( X,Y\right) \in \mathfrak{A}\times \mathfrak{A}\)に対して、\begin{equation*}
\#X=\#Y\ \Leftrightarrow \ \text{全単射}f:X\rightarrow Y\text{が存在する}
\end{equation*}を満たすものとして定義すると、この\(=\)は\(\mathfrak{A}\)上の同値関係である。

上の命題より、それぞれの集合\(X\in \mathfrak{A}\)に対して、それを代表とする同値類\begin{equation*}
\left[ X\right] =\left\{ Y\in \mathfrak{A}\ |\ \#X=\#Y\right\}
\end{equation*}を考えることができます。同値類の性質より、\begin{eqnarray*}
&&\left( a\right) \ \forall X\in \mathfrak{A}:X\in \left[ X\right] \\
&&\left( b\right) \ \mathfrak{A}=\bigcup_{X\in \mathfrak{A}}\left[ X\right] \\
&&\left( c\right) \ \forall X,Y\in \mathfrak{A}:\left( \#X=\#Y\
\Leftrightarrow \ \left[ X\right] =\left[ X\right] \right) \\
&&\left( d\right) \ \forall X,Y\in \mathfrak{A}:\left[ \lnot \left(
\#X=\#Y\right) \ \Leftrightarrow \ \left[ X\right] \cap \left[ X\right] =\phi \right] \end{eqnarray*}が成り立ちます。つまり、「濃度が等しい」という基準からすべての集合を複数のグループに分類したとき、それぞれの集合は何らかのグループに属し、なおかつ、異なるグループに同時に属するような集合は存在しないということです。

同値類について復習する

次回は有限集合について学びます。
次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)

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

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

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

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

アカウント
ログイン