WIIS

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

順序部分集合

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

半順序部分集合

半順序集合\(\left( A,\leq \right) \)が与えられているものとします。つまり、\(\leq \)は反射律反対称律に加えて推移律を満たすということ、具体的には、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \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] \end{eqnarray*}が成り立つということです。\(A\)の非空な部分集合\(X\)を選んだ上でその要素\(x,y\in X\)を任意に選んだとき、\(X\subset A\)ゆえに\(x,y\in A\)であるため、\(A\)上の半順序のもとで\(x\leq y\)が成り立つか判定できます。以上を踏まえた上で、それぞれの\(x,y\in X\)に対して、\begin{equation*}x\leq _{X}y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(X\)上の二項関係\(\leq _{X}\)を定義します。つまり、\(X\)の要素\(x,y\)を任意に選んだとき、\(A\)上の半順序\(\leq \)のもとで\(x\leq y\)が成り立つ場合、そしてその場合にのみ\(x\leq _{X}y\)が成り立つものとして\(X\)上の二項関係\(\leq _{X}\)を定義するということです。以上のように定義された二項関係\(\leq _{X}\)を\(\leq \)\(X\)に制限した半順序(restriction)と呼びます。その名の通り\(\leq _{X}\)は\(X\)上の半順序になることが保証されます。つまり、反射律と反対称律に加えて推移律を満たすということ、具体的には、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in X:x\leq _{X}x \\
&&\left( O_{2}\right) \ \forall x,y\in X:\left( x\leq _{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
&&\left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq _{X}y\wedge
y\leq _{X}z\right) \Rightarrow x\leq _{X}z\right] \end{eqnarray*}が成り立つということです。

命題(半順序の制限)
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、任意の\(x,y\in X\)に対して、\begin{equation*}x\leq _{X}y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして定義される\(X\)上の二項関係\(\leq _{X}\)は半順序である。
証明

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

半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、上の命題より、\(A\)上の半順序\(\leq \)を\(X\)に制限して得られる\(X\)上の二項関係\(\leq _{X}\)は半順序であるため、\begin{equation*}\left( X,\leq _{X}\right)
\end{equation*}もまた半順序集合になります。そこで、これを\(\left( A,\leq \right) \)の半順序部分集合(partial orderedsubset)や順序部分集合(ordered subset)などと呼びます。

多くの場合、半順序集合\(A\)上の半順序を部分集合\(X\subset A\)に制限することにより得られる半順序\(\leq _{X}\)を、制限する以前の半順序と同様の記号\(\leq \)で表記します。この場合、\(\left(A,\leq \right) \)の半順序部分集合を、\begin{equation*}\left( X,\leq \right)
\end{equation*}と表記できます。また、半順序部分集合について言及していることが文脈から明らかである場合、これをシンプルに\(X\)で表記します。

例(実数の大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は半順序であるため\(\mathbb{R} \)は半順序集合です。すべての整数からなる集合\(\mathbb{Z} \)は\(\mathbb{R} \)の非空な部分集合であるため、先の命題より、\(R\)は\(\mathbb{Z} \)上の半順序であり、したがって\(\mathbb{Z} \)は\(\mathbb{R} \)の半順序部分集合です。すべての有理数からなる集合\(\mathbb{Q} \)やすべての自然数からなる集合\(\mathbb{N} \)などについても同様の議論が成り立ちます。
例(集合の包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)が与えられたとき、それぞれの\(\left( A,B\right) \in \mathfrak{A}\times \mathfrak{A}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\subset B
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は半順序であるため\(\mathfrak{A}\)は半順序集合です。すべての有限集合からなる集合族\(\mathfrak{B}\)は\(\mathfrak{A}\)の非空な部分集合であるため、先の命題より、\(R\)は\(\mathfrak{B}\)上の半順序であり、したがって\(\mathfrak{B}\)は\(\mathfrak{A}\)の半順序部分集合です。
例(自然数の整除関係)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。\(R\)は半順序であるため\(\mathbb{N} \)は半順序集合です。奇数であるようなすべての自然数からなる集合\(O\)は\(\mathbb{N} \)の非空な部分集合であるため、先の命題より、\(R\)は\(O\)上の半順序であり、したがって\(O\)は\(\mathbb{N} \)の半順序部分集合です。偶数であるようなすべての自然数からなる集合\(E\)についても同様の議論が成立します。

 

全順序部分集合

半順序集合\(\left( A,\leq \right) \)が全順序である場合にも、すなわち、\(\leq \)が反射律と反対称律と推移律に加えて完備律\begin{equation*}\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}を満たす場合にも、先と同様の命題が成り立ちます。

命題(全順序の制限)
全順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、任意の\(x,y\in X\)に対して、\begin{equation*}x\leq _{X}y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして定義される\(X\)上の二項関係\(\leq _{X}\)は全順序である。
証明

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

全順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、上の命題より、\(A\)上の全順序\(\leq \)を\(X\)に制限して得られる\(X\)上の二項関係\(\leq _{X}\)は全順序であるため、\begin{equation*}\left( X,\leq _{X}\right)
\end{equation*}もまた全順序集合になります。そこで、これを\(\left( A,\leq \right) \)の全順序部分集合(total ordered subset)と呼びます。

多くの場合、全順序集合\(A\)上の全順序を部分集合\(X\subset A\)に制限することにより得られる全順序\(\leq _{X}\)を制限する以前の全順序と同様の記号\(\leq \)で表記します。この場合、\(\left( A,\leq\right) \)の全順序部分集合を、\begin{equation*}\left( X,\leq \right)
\end{equation*}と表記できます。また、全順序部分集合について言及していることが文脈から明らかである場合、これをシンプルに\(X\)で表記します。

例(実数の大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は全順序であるため\(\mathbb{R} \)は全順序集合です。すべての整数からなる集合\(\mathbb{Z} \)は\(\mathbb{R} \)の非空な部分集合であるため、先の命題より、\(R\)は\(\mathbb{Z} \)上の全順序であり、したがって\(\mathbb{Z} \)は\(\mathbb{R} \)の全順序部分集合です。すべての有理数からなる集合\(\mathbb{Q} \)やすべての自然数からなる集合\(\mathbb{N} \)などについても同様の議論が成り立ちます。

 

半順序集合の部分集合であるような全順序集合

半順序集合\(A\)の非空な部分集合\(X\)が与えられたとき、先の命題より、\(X\)もまた半順序集合になることが保証されます。その一方で、\(A\)上の半順序は\(A\)上において完備律を満たすとは限らないため、\(X\)は\(A\)の全順序部分集合になるとは限りません。以下の例より明らかです。

例(全順序集合ではない半順序集合の部分集合)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。\(R\)は半順序です。その一方で、例えば、2つの自然数\(2,3\)について\(2|3\)と\(3|2\)はともに成り立たず、したがって\(R\)は完備律を満たさず、ゆえに\(R\)は全順序ではありません。\(\mathbb{N} \)は\(\mathbb{N} \)自身の部分集合ですが、これは\(\mathbb{N} \)が\(\mathbb{N} \)の全順序部分集合ではないことを意味します。

ただし、半順序集合の部分集合を適切な形で選ぶことにより、全順序部分集合を取り出すことができます。

例(全順序集合であるような半順序集合の部分集合)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。先に示したように、\(R\)は半順序である一方で全順序ではありません。\(\mathbb{N} \)の非空な部分集合\begin{equation*}A=\left\{ 3,9,27,81\right\}
\end{equation*}に注目します。先の命題より、半順序\(R\)の\(A\)への制限\(R_{A}\)は半順序です。加えて、\(A\)の要素\(3,9,27,81\)はいずれも\(3\)の倍数であるため、\(A\)から2つの要素を任意に選んだとき、一方は他方の倍数です。つまり、\(x,y\in A\)を任意に選んだとき、\begin{equation*}x|y\vee y|x
\end{equation*}すなわち、\begin{equation*}
R\left( x,y\right) \vee R\left( y,x\right)
\end{equation*}が成り立つため\(R\)は完備律を満たします。したがって、\(A\)は\(\mathbb{N} \)の全順序部分集合です。

実は、半順序集合が任意に与えられたとき、全順序部分集合を常にとることができます。

命題(半順序集合の全順序部分集合)
半順序集合\(A\)が任意に与えられたとき、その全順序部分集合が存在する。
証明

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

 

演習問題

問題(順序部分集合の特徴づけ)
半順序集合\(\left( A,\leq \right) \)と\(A\)の非空な部分集合\(X\)が与えられたとき、\(\leq \)を\(X\)に制限した半順序\(\leq _{X}\)は、\begin{equation*}\leq _{X}=\leq \cap \left( X\times X\right)
\end{equation*}という関係を満たすことを示してください。

解答を見る

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

半順序
n次元空間上の標準的順序

n次元空間上に定義される標準的順序と呼ばれる二項関係は半順序である一方で全順序ではありません。

半順序
半順序(半順序集合)

反射律、反対称律、推移律を満たす二項関係を半順序や順序などと呼びます。また、半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素以下であると言います。半順序を定義した上で、半順序の具体例を提示します。

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

非対称律と推移律を満たす二項関係を狭義半順序や狭義順序などと呼びます。また、狭義半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素より小さいと言います。狭義半順序を定義した上で、狭義半順序の具体例を提示します。

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

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

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

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

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

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

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

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

最大値・最小値
順序部分集合の最大元・最小元

非空な順序部分集合のある要素が、他の任意の要素以上である場合、それを最大元と呼びます。また、非空な順序部分集合のある要素が、他の任意の要素以下である場合、それを最小元と呼びます。

極大値・極小値
順序部分集合の極大元・極小元

非空な順序部分集合のある要素よりも大きい要素がその集合の中に存在しない場合、その要素を極大元と呼びます。また、非空な順序部分集合のある要素よりも小さい要素がその集合の中に存在しない場合、その要素を極小元と呼びます。

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

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

DISCUSSION

質問とコメント

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

関係