WIIS

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

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

目次

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

濃度の狭義大小関係

すべての集合を要素として持つ集合族を\(\mathfrak{A}\)で表記します。任意の集合\(A,B\in \mathfrak{A}\)に対して、\begin{equation*}\left\vert A\right\vert =\left\vert B\right\vert \Leftrightarrow \text{全単射}f:A\rightarrow B\text{が存在する}
\end{equation*}という関係を満たすものとして集合の濃度の相等関係\(=\)を定義するとともに、これが\(\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 \)を定義するとともに、これが\(\mathfrak{A}\)上の全順序関係であることを示しました。以上を踏まえた上で、任意の集合\(A,B\in \mathfrak{A}\)に対して、\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\)の濃度よりも小さいものと定めるということです。

例(濃度の狭義大小関係)
集合\(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*}と定義されているものとします。\(f\)は単射であるため\(\left\vert A\right\vert \leq\left\vert B\right\vert \)が成り立ちます。その一方で、\(B\)の要素の個数は\(A\)の要素の個数よりも多いため、写像\(g:A\rightarrow B\)を任意に選ぶと、少なくとも1つの\(b\in B\)に対して\(b=f\left(a\right) \)を満たす\(a\in A\)は存在しないため\(g\)は全射ではなく、したがって全単射ではありません。つまり、\(A\)から\(B\)への全単射が存在しないため\(\left\vert A\right\vert \not=\left\vert B\right\vert \)が成り立ちます。以上より\(\left\vert A\right\vert <\left\vert B\right\vert \)であることが示されました。

先の命題より、集合\(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 \)は成り立ちません。

例(濃度の狭義大小関係)
すべての自然数からなる集合\begin{equation*}\mathbb{N} =\left\{ 1,2,\cdots \right\}
\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\)について\(\left\vert A\right\vert <\left\vert B\right\vert \)が成り立つことは\(\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 \)が成り立つための必要十分条件である。
証明

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

復習になりますが、選択公理を認める場合、集合\(A,B\)について、\(A\)から\(B\)への単射が存在することと、\(B\)から\(A\)への全射が存在することは必要十分です。加えて、\(A\)から\(B\)への全単射が存在することと\(B\)から\(A\)への全単射が存在することは必要十分です。以上の事実と上の命題より以下を得ます。

命題(写像を用いた濃度の狭義大小関係の判定)
集合\(A,B\)について、\(B\)から\(A\)への全射が存在する一方で全単射が存在しないことは、\(\left\vert A\right\vert <\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: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}
\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 \)であることが示されました。

 

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

すべての集合を要素として持つ集合族を\(\mathfrak{A}\)で表記します。任意の集合\(A,B\in \mathfrak{A}\)に対して、\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*}という関係を満たすものとして集合の濃度の狭義大小関係\(\leq \)を定義しました。集合\(A,B\)について\(\left\vert A\right\vert<\left\vert B\right\vert \)は成り立つか否かのどちらか一方であるため、\(<\)を\(\mathfrak{A}\)上の二項関係とみなすことができます。では、\(<\)はどのような性質を満たす二項関係でしょうか。

集合\(A,B\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left\vert A\right\vert <\left\vert B\right\vert \Rightarrow \lnot \left(
\left\vert B\right\vert <\left\vert A\right\vert \right)
\end{equation*}が成り立つことを示すことができます。つまり、集合\(A\)の濃度が集合\(B\)の濃度よりも小さい場合、その逆は成り立たないということです。以上の事実は、集合の濃度の狭義大小関係\(<\)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが非対称律を満たすことを意味します。

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

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

集合\(A,B,C\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\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
\end{equation*}が成り立つことを示すことができます。つまり、集合\(A,B,C\)について、\(B\)の濃度が\(A\)の濃度よりも大きく、\(C\)の濃度が\(B\)の濃度よりも大きい場合、\(C\)の濃度が\(A\)の濃度よりも大きいことが保証されます。以上の事実は、集合の濃度の狭義大小関係\(<\)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが推移律を満たすことを意味します。

命題(濃度の狭義大小関係は推移律を満たす)
濃度の狭義大小関係\(<\)は非対称律を満たす。つまり、\begin{equation*}\forall A,B,C\in \mathfrak{A}:\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{equation*}が成り立つ。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。
証明

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

集合\(A,B\in \mathfrak{A}\)を任意に選んだとき、\begin{equation*}\left\vert A\right\vert <\left\vert B\right\vert ,\ \left\vert B\right\vert
<\left\vert A\right\vert ,\ \left\vert A\right\vert =\left\vert B\right\vert
\text{の中の1つだけが成り立つ}
\end{equation*}ことを示すことができます。つまり、集合の濃度の狭義大小関係\(<\)を\(\mathfrak{A}\)上の二項関係とみなしたとき、これが三分律を満たすということです。

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

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

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

命題(濃度の狭義大小関係は狭義順序)
集合の濃度の狭義大小関係\(<\)は\(\mathfrak{A}\)上の狭義全順序関係である。ただし、\(\mathfrak{A}\)はすべての集合を要素として持つ集合族である。
< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

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

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

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

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

無限集合
無限集合

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

狭義全順序
狭義全順序(狭義全順序集合)

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

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

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

DISCUSSION

質問とコメント

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