WIIS

WIIS

集合の濃度

集合の濃度の大小関係

  1. トップ
  2. 数学
  3. 集合
  4. 集合の濃度
関係
集合の濃度
順序集合
  • 集合Aから集合Bへの単射が存在する場合、Aの濃度はBの濃度以下であると言います。濃度の大小関係を二項関係とみなしたとき、これは反射律・反対称律・推移律・完備律を満たす全順序関係です。

目次

関連知識

前のページ：

集合の濃度

次のページ：

集合の濃度の狭義大小関係

あとで読む
Mailで保存
Xで共有

濃度の大小関係

集合\(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*}という関係もまた成り立つでしょうか。議論してください。

解答を見る

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

関連知識

前のページ：

集合の濃度

次のページ：

集合の濃度の狭義大小関係

あとで読む
Mailで保存
Xで共有
関係
集合の濃度
順序集合

質問とコメント

プレミアム会員専用コンテンツです

【会員登録】

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ（命題の証明や演習問題とその解答）へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

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

目次
質問
アカウント

LEARN MORE

さらに深く学びたい人のための会員サービス

会員登録

有料プレミアム会員は質問・コメントの投稿と閲覧、命題の証明の閲覧、演習問題とその解答への閲覧が可能になります。

よくある質問

皆さまからよく頂く質問への回答をまとめました。こちらに解決方法が見つからない場合にはお問い合わせください。

論理

集合

実数

ユークリッド空間

微分積分

測度

確率

ミクロ経済学
ゲーム理論
オークション理論
マッチング理論
思想
歴史
集合
写像
関係
集合の濃度
集合の濃度
有限集合
可算集合
非可算集合
濃度の演算
順序集合
アカウント
ツール
システム
使い方