WIIS

教材一覧
教材一覧
教材検索
RELATION

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

目次

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

整列関係と整列集合

全順序集合\(A\)が与えられているものとします。つまり、\(A\)上に定義された二項関係\(\leq \)が反射律反対称律推移律に加えて完備律を満たすということ、具体的には、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left( x\leq y\wedge y\leq
x\Rightarrow x=y\right) \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{eqnarray*}が成り立つということです。全順序集合\(A\)の非空な部分集合\(X\)について、そのある要素\(a\)が\(X\)の任意の要素以下である場合には、つまり、\begin{equation*}\exists a\in X,\ \forall x\in X:a\leq x
\end{equation*}が成り立つならば、\(a\)を\(X\)の最小元と呼び、これを、\begin{equation*}a=\min X
\end{equation*}で表記します。つまり、\(\min X\)は集合\(X\)の最小元を表す記号です。定義より、\(X\)の最小元は\(X\)の要素でなければなりません。

一般に、全順序集合の非空な部分集合は最小元を持つとは限りません。一方、全順序集合\(A\)の任意の非空な部分集合が最小元を持つ場合には、すなわち、\begin{equation*}\forall X\in 2^{A}\backslash \left\{ \phi \right\} ,\ \exists a\in X,\
\forall x\in X:a\leq x
\end{equation*}が成り立つ場合には、このような全順序集合\(A\)を整列集合(well-ordered set)と呼びます。また、整列集合\(A\)上に定義された全順序\(\leq \)を整列順序関係(well order relation)と呼びます。

 

整列集合の具体例

以下が整列集合の具体例です。

命題(大小関係が定義された自然数集合は整列集合)
すべての自然数からなる集合\(\mathbb{N} \)上に大小関係\(\leq \)を定義する。\(\left( \mathbb{N} ,\leq \right) \)は整列集合である。
証明

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

定義より、整列集合は全順序集合であり、全順序集合ではない集合は整列集合ではありません。その一方で、その逆は成り立つとは限りません。つまり、全順序集合は整列集合であるとは限りません。以下の例より明らかです。

例(整列集合ではない全順序集合)
すべての整数からなる集合\(\mathbb{Z} \)上に大小関係\(\leq \)を定義します。\(\left( \mathbb{Z} ,\leq \right) \)は全順序集合である一方で整列集合ではありません。実際、\(\mathbb{Z} \)は\(\mathbb{Z} \)の部分集合である一方で\(\min \mathbb{Z} \)は存在しないからです。

ただし、全順序集合が有限集合である場合には、それが整列集合であることを保証できます。

命題(有限な全順序集合は整列集合)
全順序集合\(\left( A,\leq \right) \)が有限集合であるならば、\(\left( A,\leq \right) \)は整列集合である。
証明

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

例(有限な全順序集合は整列集合)
以下の集合\begin{equation*}
A=\left\{ -10,-9,\cdots ,0,\cdots ,9,10\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。すべての実数集合\(\mathbb{R} \)上に定義された大小関係\(\leq \)は全順序です。\(A\)は\(\mathbb{R} \)の非空な部分集合であるため、\(\leq \)を\(A\)に制限して得られる二項関係は全順序です。したがって\(\left( A,\leq \right) \)が全順序集合であることが示されました。加えて、\(A\)は有限集合であるため、上の命題より\(A\)は整列集合です。

 

演習問題

問題(整列集合)
以下の集合\begin{equation*}
A=\left\{ \sqrt{2},\sqrt{3},\sqrt{4},\sqrt{5},\sqrt{6},\sqrt{7}\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( A,\leq \right) \)は整列集合でしょうか。議論してください。
解答を見る

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

問題(整列集合)
以下の集合\begin{equation*}
A=\left\{ \frac{1}{x}\ |\ x\in \mathbb{N} \wedge x\leq 100\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( A,\leq \right) \)は整列集合でしょうか。議論してください。
解答を見る

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

問題(整列集合)
以下の集合\begin{equation*}
A=\left\{ x\ |\ x\in \mathbb{Q} \wedge x>5\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( A,\leq \right) \)は整列集合でしょうか。議論してください。
解答を見る

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

問題(整列集合)
以下の集合\begin{equation*}
\left[ 0,1\right] =\left\{ x\in \mathbb{R} \ |\ 0\leq x\leq 1\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( \left[ 0,1\right] ,\leq\right) \)は整列集合でしょうか。議論してください。
解答を見る

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

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

関連知識

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

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

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

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

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

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

全順序
順序部分集合

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

DISCUSSION

質問とコメント

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

関係