WIIS

教材一覧
教材一覧
教材検索
CARDINALITY OF SET

集合の濃度の大小関係

目次

< 前のページ
Share on twitter
Twitterで共有
Share on email
メールで共有

濃度の大小関係

集合\(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 \)が成り立つものとみなすということです。

例(濃度の大小関係)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},a_{3}\right\} \\
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*}が成り立つことが明らかになりました。

例(濃度の大小関係)
すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,\cdots \right\}
\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*}が成り立つことが明らかになりました。

例(濃度の大小関係)
自然数\(n\)を任意に選んだ上で、\(1\)以上\(n\)以下のすべての自然数からなる集合を、\begin{equation*}\mathbb{N} _{n}=\left\{ 1,\cdots ,n\right\} \end{equation*}で表記します。これとすべての自然数からなる集合\(\mathbb{N} \)の間には\(\mathbb{N} _{n}\subset \mathbb{N} \)という関係が成り立つため、それぞれの\(x\in \mathbb{N} _{n}\)に対して、\begin{equation*}f\left( x\right) =x\in \mathbb{N} \end{equation*}を定める写像\(f:\mathbb{N} _{n}\rightarrow \mathbb{N} \)が定義可能です。さらに、\(x,x^{\prime }\in \mathbb{N} _{n}\)を任意に選んだとき、\(f\)の定義より、\begin{equation*}x\not=x^{\prime }\Rightarrow f\left( x\right) \not=f\left( x^{\prime
}\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 \)は成り立ちません。

例(濃度の大小関係)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},a_{3}\right\} \\
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\)について、全射\(f:B\rightarrow A\)が存在することは、\(\left\vert A\right\vert \leq \left\vert B\right\vert \)が成り立つための必要十分条件である。ただし、選択公理を認めるものとする。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

集合\(A\)の濃度が集合\(B\)の濃度以下であることを示すためには、\(A\)から\(B\)への単射が存在することを示す代わりに、\(B\)から\(A\)への全射が存在することを示してもよいということです。

例(全射を用いた濃度の大小関係の判定)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},a_{3}\right\} \\
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*}が成り立つことが明らかになりました。

例(全射を用いた濃度の大小関係の判定)
すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,\cdots \right\}
\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*}が成り立つことが明らかになりました。

例(全射を用いた濃度の大小関係の判定)
自然数\(n\)を任意に選んだ上で、\(1\)以上\(n\)以下のすべての自然数からなる集合を、\begin{equation*}\mathbb{N} _{n}=\left\{ 1,\cdots ,n\right\} \end{equation*}で表記します。これとすべての自然数からなる集合\(\mathbb{N} \)の間には\(\mathbb{N} _{n}\subset \mathbb{N} \)が成り立つことを踏まえた上で、それぞれの\(x\in \mathbb{N} \)に対して、\begin{equation*}f\left( x\right) =\left\{
\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 \)は成り立ちません。

例(全射を用いた濃度の大小関係の判定)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},a_{3}\right\} \\
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\)の部分集合への全単射が存在することは必要十分です。以上の事実を踏まえると濃度の大小関係に関する以下の命題を得ます。

命題(全単射を用いた濃度の大小関係の判定)
集合\(A,B\)について、\(A\)と等しい濃度を持つ\(B\)の部分集合が存在することは、\(\left\vert A\right\vert \leq \left\vert B\right\vert \)が成り立つための必要十分条件である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(全単射を用いた濃度の大小関係の判定)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},a_{3}\right\} \\
B &=&\left\{ b_{1},b_{2},b_{3},b_{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*}が成り立つことが明らかになりました。

例(全単射を用いた濃度の大小関係の判定)
すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,\cdots \right\}
\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*}が成り立つことが明らかになりました。

例(全単射を用いた濃度の大小関係の判定)
自然数\(n\)を任意に選んだ上で、\(1\)以上\(n\)以下のすべての自然数からなる集合を、\begin{equation*}\mathbb{N} _{n}=\left\{ 1,\cdots ,n\right\} \end{equation*}で表記します。これとすべての自然数からなる集合\(\mathbb{N} \)の間には\(\mathbb{N} _{n}\subset \mathbb{N} \)が成り立つことを踏まえた上で、それぞれの\(x\in \mathbb{N} _{n}\)に対して、\begin{equation*}f\left( x\right) =x
\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 \)は成り立ちません。

例(全単射を用いた濃度の大小関係の判定)
集合\(A,B\)がそれぞれ、\begin{eqnarray*}A &=&\left\{ a_{1},a_{2},a_{3}\right\} \\
B &=&\left\{ b_{1},b_{2},b_{3},b_{4}\right\}
\end{eqnarray*}で与えられているものとします。\(A\)の要素の個数は\(B\)の要素の個数よりも少ないため、\(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 \)は成り立ちません。

 

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

すべての集合を要素として持つ集合族を\(\mathfrak{A}\)で表記します。集合\(A,B\in \mathfrak{A}\)を任意に選んだとき、\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\)について、\(A\)から\(B\)への単射は存在するか否かのどちら一方であるため、\(\leq \)を\(\mathfrak{A}\)上の二項関係とみなすことができます。では、\(\leq \)はどのような性質を満たす二項関係でしょうか。

集合\(A\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left\vert A\right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つことを示すことができます。つまり、\(A\)から\(A\)への単射が常に存在するということです。以上の事実は、集合の濃度の大小関係\(\leq \)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが反射律を満たすことを意味します。

命題(濃度の大小関係は反射律を満たす)
濃度の大小関係\(\leq \)は反射律を満たす。つまり、\begin{equation*}\forall A\in \mathfrak{A}:\left\vert A\right\vert \leq \left\vert
A\right\vert
\end{equation*}が成り立つ。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

集合\(A,B\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left( \left\vert A\right\vert \leq \left\vert B\right\vert \wedge
\left\vert B\right\vert \leq \left\vert A\right\vert \right) \Rightarrow
\left\vert A\right\vert =\left\vert B\right\vert
\end{equation*}が成り立つことを示すことができます。つまり、\(A\)から\(B\)への単射と\(B\)から\(A\)への単射が存在する場合、\(A\)から\(B\)への全単射が存在するということです。以上の事実は、集合の濃度の大小関係\(\leq \)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが反対称律を満たすことを意味します。

命題(濃度の大小関係は反対称律を満たす)
濃度の大小関係\(\leq \)は反対称律を満たす。つまり、\begin{equation*}\forall A,B\in \mathfrak{A}:\left[ \left( \left\vert A\right\vert \leq
\left\vert B\right\vert \wedge \left\vert B\right\vert \leq \left\vert
A\right\vert \right) \Rightarrow \left\vert A\right\vert =\left\vert
B\right\vert \right] \end{equation*}が成り立つ。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

集合\(A,B,C\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left( \left\vert A\right\vert \leq \left\vert B\right\vert \wedge
\left\vert B\right\vert \leq \left\vert C\right\vert \right) \Rightarrow
\left\vert A\right\vert \leq \left\vert C\right\vert
\end{equation*}が成り立つことを示すことができます。つまり、\(A\)から\(B\)への単射と\(B\)から\(C\)への単射が存在する場合、\(A\)から\(C\)への全単射が存在するということです。以上の事実は、集合の濃度の大小関係\(\leq \)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが推移律を満たすことを意味します。

命題(濃度の大小関係は反対称律を満たす)
濃度の大小関係\(\leq \)は推移律を満たす。つまり、\begin{equation*}\forall A,B,C\in \mathfrak{A}:\left[ \left( \left\vert A\right\vert \leq
\left\vert B\right\vert \wedge \left\vert B\right\vert \leq \left\vert
C\right\vert \right) \Rightarrow \left\vert A\right\vert \leq \left\vert
C\right\vert \right] \end{equation*}が成り立つ。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

集合\(A,B\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left\vert A\right\vert \leq \left\vert B\right\vert \vee \left\vert
B\right\vert \leq \left\vert A\right\vert
\end{equation*}が成り立つことを示すことができます。つまり、任意の集合\(A,B\)について、\(A\)から\(B\)への単射か\(B\)から\(A\)への単射の少なくとも一方が存在するということです。以上の事実は、集合の濃度の大小関係\(\leq \)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが完備律を満たすことを意味します。

命題(濃度の大小関係は完備律を満たす)
濃度の大小関係\(\leq \)は完備律を満たす。つまり、\begin{equation*}\forall A,B\in \mathfrak{A}:\left( \left\vert A\right\vert \leq \left\vert
B\right\vert \vee \left\vert B\right\vert \leq \left\vert A\right\vert
\right)
\end{equation*}が成り立つ。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

集合の濃度の大小関係\(\leq \)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが反射律、反対称律、推移律および完備律を満たすことが明らかになりました。つまり、\(\leq \)は全順序関係であるということです。

命題(濃度の大小関係は全順序)
濃度の大小関係\(\leq \)は\(\mathfrak{A}\)上の全順序関係である。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。

 

演習問題

問題(集合の濃度の大小関係)
集合\(A,B\in \mathfrak{A}\)が任意に与えられたとき、\begin{equation*}A\subset B\Rightarrow \left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(集合の濃度の大小関係)
非空な集合\(A,B\in \mathfrak{A}\)が任意に与えられたとき、\begin{equation*}\left\vert A\right\vert \leq \left\vert A\times B\right\vert
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(集合の濃度の大小関係)
集合\(A,B\in \mathfrak{A}\)が任意に与えられたとき、\begin{equation*}A\subset B\Rightarrow \left\vert A\right\vert \leq \left\vert B\right\vert
\end{equation*}が成り立つことを先に示しましたが、逆に、\begin{equation*}
\left\vert A\right\vert \leq \left\vert B\right\vert \Rightarrow A\subset B
\end{equation*}という関係もまた成り立つでしょうか。議論してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

< 前のページ
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

ベルンシュタインの定理
集合の濃度

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

狭義全順序
集合の濃度の狭義大小関係

集合Aの濃度が集合Bの濃度以下であるともに両者の濃度が等しくない場合、Aの濃度はBの濃度よりも小さいと言います。濃度の狭義大小関係を二項関係とみなしたとき、これは非対称律、推移律および三分律を満たす狭義全順序関係です。

無限集合
無限集合

有限集合ではない集合、つまり無限個の要素を持つ集合を無限集合と呼びます。無限集合のすべての要素を数え上げることはできないため、無限集合の濃度を 1 つの自然数として表すことはできません。ただ、2 つの無限集合が与えられたとき、それらが等しい濃度を持つかどうかを調べることはできます。

全順序
全順序(全順序集合)

反射律、反対称律、推移律、完備律を満たす二項関係、すなわち完備律を満たす半順序を全順序や線型順序などと呼びます。全順序を定義した上で、全順序の具体例を提示します。

全順序
全順序と狭義全順序の関係

全順序から狭義全順序を生成する方法や、逆に、狭義全順序から全順序を生成する方法を解説するとともに、両者の間に成立する関係について解説します。

ハッセ図
ハッセ図(有向グラフと順序)

有向グラフを用いることにより半順序集合を視覚的に表現できます。加えて、半順序の性質を利用することにより、有向グラフを簡略化したハッセ図と呼ばれる図を得ることができます。

全順序
順序部分集合

順序集合A上に定義されている順序のもとで、Aの非空な部分集合Xが順序集合になっている場合、XをAの順序部分集合と呼びます。

全順序
整列順序関係(整列集合)

全順序集合の任意の非空な部分集合が最小限を持つ場合、このような全順序集合を整列集合と呼びます。また、整列集合上に定義された全順序を整列関係と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録