WIIS

順序集合

狭義全順序(狭義全順序集合)の定義と具体例

目次

Mailで保存
Xで共有

狭義全順序関係

集合\(A\)上の二項関係\(R\)が与えられているものとします。つまり、\begin{equation*}R\subset A\times A
\end{equation*}です。特に、集合\(A\)上の二項関係\(R\)が狭義半順序であることとは、非対称律推移律を満たすこと、すなわち、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ \left( x,y\right) \in
R\Rightarrow \left( y,x\right) \not\in R\right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left\{ \left[ \left( x,y\right)
\in R\wedge \left( y,z\right) \in R\right] \Rightarrow \left( x,z\right) \in
R\right\}
\end{eqnarray*}が成り立つことを意味します。以上の性質に加えて\(R\)が三分律を満たす場合には、すなわち、\begin{equation*}\left( S_{3}\right) \ \forall x,y\in A:\left( x,y\right) \in R,\ \left(
y,x\right) \in R,\ x=y\text{の中の1つだけが成り立つ}
\end{equation*}を満たす場合には、このような二項関係\(R\)を狭義全順序(strict total order)や狭義線型順序(strict linear order)などと呼びます。狭義全順序を規定する以上の3つの性質(非対称律・推移律・三分律)を総称して狭義全順序の公理(axiom of strict total order)と呼びます。狭義順序という用語は狭義半順序と狭義全順序のどちらの意味でも使われるため、文脈から判断する必要があります。

多くの場合、狭義順序と同様に、狭義全順序を表す記号として\(<\)を採用します。つまり、集合\(A\)上の狭義全順序\(R\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}x<y\Leftrightarrow \left( x,y\right) \in R
\end{equation*}を満たすものとして記号\(x<y\)の意味を定義するということです。この場合、任意の\(x,y\in A\)について、\begin{equation*}\lnot \left( x<y\right) \Leftrightarrow \left( x,y\right) \not\in R
\end{equation*}という関係もまた成立することに注意してください。この記号\(<\)を用いて狭義全順序の公理を改めて表現すると、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:x<y,\ y<x,\ x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}となります。

集合\(A\)上の狭義全順序\(<\)が与えられたとき、要素\(x,y\in A\)について\(x<y\)が成り立つ場合には、\(x\)\(y\)より小さい(\(x\) is less than \(y\))とか、\(y\)\(x\)より大きい(\(y\) is greater than \(x\))などと言います。

集合\(A\)上に狭義全順序\(<\)が定義されている場合、これらの組\begin{equation*}\left( A,<\right)
\end{equation*}を狭義全順序集合(strict totally ordered set)と呼びます。ただし、狭義全順序集合について言及していることが文脈から明らかである場合には、狭義全順序集合をシンプルに、\begin{equation*}
A
\end{equation*}と表記できます。

 

狭義全順序の特徴づけ

集合\(A\)上の二項関係\(R\)が非対称律を満たすこととは、\begin{equation*}\forall x,y\in A:\left[ \left( x,y\right) \in R\Rightarrow \left( y,x\right)
\not\in R\right] \end{equation*}が成り立つことを意味し、非反射律を満たすことは、\begin{equation*}
\forall x\in A:\left( x,x\right) \not\in R
\end{equation*}が成り立つことを意味し、反対称律を満たすこととは、\begin{equation*}
\forall x,y\in A:\left\{ \left[ \left( x,y\right) \in R\wedge \left(
y,x\right) \in R\right] \Rightarrow x=y\right\}
\end{equation*}が成り立つことを意味します。

集合\(A\)上の二項関係\(R\)が非対称律を満たすことと、\(R\)が非反射律と反対称律をともに満たすことは必要十分です。以上を踏まえると、狭義全順序を以下のように定義することもできます。

命題(狭義全順序の特徴づけ)
集合\(A\)上の二項関係\(R\)が非反射律、反対称律、推移律、三分律を満たすことは、すなわち、\begin{eqnarray*}&&\left( a\right) \ \forall x\in A:\left( x,x\right) \not\in R \\
&&\left( b\right) \ \forall x,y\in A:\left\{ \left[ \left( x,y\right) \in
R\wedge \left( y,x\right) \in R\right] \Rightarrow x=y\right\} \\
&&\left( c\right) \ \forall x,y,z\in A:\left\{ \left[ \left( x,y\right) \in
R\wedge \left( y,z\right) \in R\right] \Rightarrow \left( x,z\right) \in
R\right\} \\
&&\left( d\right) \ \forall x,y\in A:\left( x,y\right) \in R,\ \left(
y,x\right) \in R,\ x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}をすべて満たすことは、\(R\)が\(A\)上の狭義全順序であるための必要十分条件である。
証明

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

狭義全順序の記号\(<\)を用いて上の命題の主張を表現すると、狭義全順序の公理は、\begin{eqnarray*}&&\left( a\right) \ \forall x\in A:\lnot \left( x<x\right) \\
&&\left( b\right) \ \forall x,y\in A:\left[ \left( x<y\wedge y<x\right)
\Rightarrow x=y\right] \\
&&\left( c\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right)
\Rightarrow x<z\right] \\
&&\left( d\right) \ \forall x,y\in A:x<y,\ y<x,\ x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}と必要十分であるということになります。

 

狭義全順序と狭義半順序の違い

集合\(A\)上の狭義半順序\(<\)は非対称律と推移律\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \end{eqnarray*}を満たす二項関係として定義されます。これらの性質に加えて、三分律\begin{equation*}
\left( S_{3}\right) \ \forall x,y\in A:x<y,\ y<x,\ x=y\text{の中の1つだけが成り立つ}
\end{equation*}を満たす場合、\(<\)を狭義全順序と呼びます。三分律を加えることにより何が変わるのでしょうか。

狭義半順序\(<\)が三分律を満たさない場合には、三分律の否定である以下の命題\begin{equation*}\exists x,y\in A:x<y,\ y<x,\ x=y\text{がいずれも成り立たない}
\end{equation*}が成り立つ可能性があります。つまり、狭義半順序\(<\)のもとでは\(x<y\)と\(y<x\)と\(x=y\)がいずれも成立しないような\(A\)の要素\(x,y\)が存在する事態は起こり得るため、\(A\)の要素どうしを比較できるとは限りません。一方、狭義半順序\(<\)が三分律を満たす場合には、すなわち\(<\)が狭義全順序である場合には、\(A\)の任意の要素\(x,y\)に対して\(x<y\)または\(y<x\)または\(x=y\)の中の1つが成り立つため、\(A\)の要素どうしを必ず比較できます。集合\(A\)上の狭義全順序とは、\(A\)上の任意の2つの要素を比較可能であるような狭義半順序です。

集合\(A\)上の狭義半順序\(<\)が与えられたとき、そこから、任意の\(x,y\in A\)に対して、\begin{equation*}x\leq y\Leftrightarrow \left( x<y\vee x=y\right)
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(\leq \)は半順序になります。狭義全順序は狭義半順序であるため、\(<\)が狭義全順序である場合も同様にして\(\leq \)が定義可能です。さて、2つの要素\(x,y\in A\)を任意に選ぶと、\(x<y\)と\(y<x\)と\(x=y\)の真理値の組み合わせに応じて論理的には以下の真理値表にあるような\(\left(a\right) \)から\(\left( h\right) \)までの8通りの場合が起こり得ます。ただし、\(1\)は真を表す真理値であり、\(0\)は偽を表す真理値です。

$$\begin{array}{cccccc}
\hline
\quad & x<y & y<x & x=y & x\leq y & y\leq x \\ \hline
\left( a\right) & 1 & 1 & 1 & 1 & 1 \\ \hline
\left( b\right) & 1 & 1 & 0 & 1 & 1 \\ \hline
\left( c\right) & 1 & 0 & 1 & 1 & 1 \\ \hline
\left( d\right) & 1 & 0 & 0 & 1 & 0 \\ \hline
\left( e\right) & 0 & 1 & 1 & 1 & 1 \\ \hline
\left( f\right) & 0 & 1 & 0 & 0 & 1 \\ \hline
\left( g\right) & 0 & 0 & 1 & 1 & 1 \\ \hline
\left( h\right) & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

ただし、\(<\)が三分律を満たす場合には、すなわち\(<\)が狭義全順序である場合には\(x<y\)と\(y<x\)と\(x=y\)の中の複数の条件は同時に成立しないため、\(\left( a\right) ,\left( b\right) ,\left( c\right),\left( e\right) \)のケースが起こる可能性は排除されます。同時に、やはり三分律より\(x<y\)と\(y<x\)と\(x=y\)の中のどれか1つが必ず成立するため、\(\left(h\right) \)のケースが起こる可能性は排除されます。つまり、2つの要素\(x,y\in A\)を任意に選んだとき、狭義全順序\(\leq \)のもとでは\(\left( a\right) ,\left( b\right),\left( c\right) ,\left( e\right) ,\left( h\right) \)は成り立たず、したがって\(\left( d\right) ,\left( f\right) ,\left( g\right) \)の中のどれか1つが成り立つこと、すなわち、\begin{equation*}x\leq y,\quad y\leq x
\end{equation*}の少なくとも一方が成り立つことが明らかになりました。つまり、\(\leq \)は完備律を満たすということです。

命題(三分律の含意)
集合\(A\)上の狭義全順序\(<\)が与えられたとき、任意の\(x,y\in A\)に対して、\begin{equation*}x\leq y\Leftrightarrow \left( x<y\vee x=y\right)
\end{equation*}を満たすものとして定義される\(A\)上の半順序\(\leq \)は完備律を満たす。すなわち、\begin{equation*}\forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}が成り立つ。

 

狭義全順序の具体例:実数の狭義大小関係

実数どうしを比較する通常の狭義大小関係\(<\)は実数集合\(\mathbb{R} \)上に定義された二項関係です。実際、狭義大小関係\(<\)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、以下の関係\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x<y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\begin{equation*}R\subset \mathbb{R} \times \mathbb{R} \end{equation*}を定義可能です。つまり、実数\(x,y\)について、\(x\)が\(y\)より小さい場合、そしてその場合にのみ\(\left( x,y\right) \in R\)が成り立つものとして\(\mathbb{R} \)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を狭義大小関係\(<\)と同一視することにより、狭義大小関係\(<\)を\(\mathbb{R} \)上の二項関係とみなすことができます。

実数集合\(\mathbb{R} \)上に定義された狭義大小関係\(<\)は\(\mathbb{R} \)上の狭義全順序です。つまり、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:x<y,\ y<x,\ x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立ちます。

命題(狭義大小関係は狭義全順序)
実数集合\(\mathbb{R} \)上に定義された狭義大小関係\(<\)は\(\mathbb{R} \)上の狭義全順序である。
証明

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

 

狭義全順序ではない狭義半順序の具体例:狭義の包含関係

2つの集合\(A,B\)について、\(A\)が\(B\)の部分集合である一方で\(A\)は\(B\)とは異なる集合である場合、すなわち、\begin{equation*}A\subset B\wedge A\not=B
\end{equation*}が成り立つ場合、\(A\)を\(B\)の真部分集合と呼びます。その上で、\(A\)が\(B\)の真部分集合であることを、\begin{equation*}A\varsubsetneq B
\end{equation*}で表記します。これを狭義包含関係と呼びます。

全体集合\(U\)を任意に選んだ上で、その部分集合どうしの狭義包含関係(真部分集合)を判定する状況を想定します。任意の集合\(A,B\in 2^{U}\)について、以下の関係\begin{equation*}\left( A,B\right) \in R\Leftrightarrow A\varsubsetneq B
\end{equation*}を満たすものとして\(2^{U}\)上の二項関係\begin{equation*}R\subset 2^{U}\times 2^{U}
\end{equation*}を定義します。ただし、\(2^{U}\)は\(U\)のべき集合、すなわち\(U\)のすべての部分集合を要素として持つ集合族です。つまり、\(U\)の部分集合\(A,B\)について、\(A\)が\(B\)の真部分集合である場合、そしてその場合にのみ\(\left( A,B\right) \in R\)が成り立つものとして\(2^{U}\)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を狭義包含関係\(\varsubsetneq \)と同一視することにより、狭義包含関係\(\varsubsetneq \)を\(2^{U}\)上の二項関係とみなすことができます。

集合\(U\)のべき集合\(2^{U}\)上に定義された狭義包含関係\(\varsubsetneq \)は\(2^{U}\)上の狭義半順序である一方で狭義全順序ではありません。つまり、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall A,B\in 2^{U}:\left[ A\varsubsetneq
B\Rightarrow \lnot \left( B\varsubsetneq A\right) \right] \\
&&\left( S_{2}\right) \ \forall A,B,C\in 2^{U}:\left[ \left( A\varsubsetneq
B\wedge B\varsubsetneq C\right) \Rightarrow A\varsubsetneq C\right] \end{eqnarray*}が成り立つ一方で、\begin{equation*}
\left( S_{3}\right) \ \forall A,B\in 2^{U}:A\varsubsetneq B,\ B\varsubsetneq
A,\ A=B\text{の中の1つだけが成り立つ}
\end{equation*}は成り立つとは限りません。以下の例より明らかです。

例(狭義の包含関係は狭義全順序ではない)
全体集合\(U\)がすべての自然数からなる集合\(\mathbb{N} \)であるものとします。その上で、以下の2つの集合\begin{eqnarray*}\left\{ 1,2\right\} &\in &2^{\mathbb{N} } \\
\left\{ 2,3\right\} &\in &2^{\mathbb{N} }
\end{eqnarray*}に注目したとき、\begin{eqnarray*}
\left\{ 1,2\right\} &\varsubsetneq &\left\{ 2,3\right\} \\
\left\{ 2,3\right\} &\varsubsetneq &\left\{ 1,2\right\} \\
\left\{ 1,2\right\} &=&\left\{ 2,3\right\}
\end{eqnarray*}はいずれも成立せず、したがって、\(2^{\mathbb{N} }\)上に定義された狭義包含関係\(\varsubsetneq \)は三分律を満たしません。

 

演習問題

問題(狭義全順序)
集合\(A=\left\{ 1,2,3\right\} \)上の二項関係\(R\)が、\begin{equation*}R=\left\{ \left( 1,2\right) ,\left( 1,3\right) ,\left( 2,3\right) \right\}
\end{equation*}と定義されているものとします。\(R\)が狭義全順序であることを示してください。
解答を見る

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

問題(空関係)
関係\(R\)が集合\(A\)上の空関係であるものとします。つまり、\begin{equation*}R=\phi
\end{equation*}です。\(R\)は狭義半順序である一方で狭義全順序ではないことを示してください。
解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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