WIIS

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

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

目次

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

狭義全順序関係

集合\(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*}が成り立つ場合には、\(<\)を狭義全順序(strict total order)や狭義線型順序(strict linear order)などと呼びます。ただし、狭義全順序を狭義順序(strict order)と呼ぶ場合もあります。狭義順序という用語は狭義半順序と狭義全順序のどちらの意味でも使われるため、文脈から判断する必要があります。

繰り返しになりますが、狭義全順序とは完全律を満たす狭義半順序として定義されます。三分律を加えることにより何が変わるのでしょうか。集合\(A\)の2つの要素\(x,y\)を任意に選んだとき、狭義半順序\(<\)のもとでは\(x<y\)や\(y<x\)や\(x=y\)などが成り立つとは限らず、したがって\(x\)と\(y\)の間の大小を比較できるとは限りません。一方、狭義半順序\(<\)が完全律を満たす場合には\(x<y\)と\(y<x\)と\(x=y\)の中のどれか1つだけが必ず成り立つことが保証されるため、\(x\)と\(y\)の大小を常に比較できます。三分律は集合\(A\)の任意の異なる2つの要素が比較可能であることを保証します。言い換えると、集合\(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 \)は半順序になります。狭義全順序は狭義半順序であるため、\(<\)が狭義全順序である場合も同様です。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*}が成り立つ。

集合\(A\)上に狭義全順序\(<\)が定義されているとき、これを狭義全順序集合(strict totally ordered set)や狭義線型順序集合(strict linearly ordered set)などと呼び、\begin{equation*}\left( A,<\right)
\end{equation*}で表記します。ただし、全順序集合について言及していることが文脈から明らかである場合にはシンプルに\(A\)で表記することもできます。順序集合という用語は半順序集合と全順序集合のどちらの意味でも使われるため、文脈から判断する必要があります。

 

狭義全順序の具体例

以下が狭義全順序の具体例です。

例(実数の狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は狭義全順序です(演習問題)。
例(狭義全順序)
集合\(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\)は狭義全順序です(演習問題)。

 

狭義全順序ではない二項関係の具体例

逆に、集合\(A\)上の二項関係\(R\)が非対称律、推移律、そして三分律の中の少なくとも1つを満たさない場合、\(R\)は狭義全順序ではありません。

例(親子関係)
ヒトの集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{は}y\text{の子供}
\end{equation*}を満たすものとして\(R\)を定義します。ヒト\(x,y,z\in A\)を任意に選んだとき、\(x\)は\(y\)の子供であるとともに\(y\)が\(z\)の子供であるとき\(x\)は\(z\)の子供ではありません。したがって\(R\)は推移律を満たしません。したがって\(R\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。
例(実数の相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。\(x=y\)を満たす実数\(x,y\in \mathbb{R} \)について、\begin{equation*}x=y\wedge y=x
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。
例(実数の非相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\not=y
\end{equation*}を満たすものとして\(R\)を定義します。\(1,2\in \mathbb{R} \)に注目したとき、\begin{equation*}1\not=2\wedge 2\not=1\wedge 1=1
\end{equation*}が成り立つため\(R\)は推移性を満たしません。したがって\(R\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。
例(実数の大小関係)
すべての実数からなる集合\(\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\)を定義します。\(x=y\)を満たす実数\(x,y\in \mathbb{R} \)について、\begin{equation*}x\leq y\wedge y\leq x
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。
例(集合の包含関係)
すべての集合を要素として持つ集合族\(\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\)を定義します。\(A=B\)を満たす集合\(A,B\in \mathfrak{A}\)について、\begin{equation*}A\subset B\wedge B\subset A
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。
例(恒等関係)
集合\(A\)上の恒等関係\(\Delta_{A}\)は、任意の\(\left( x,y\right) \in A\times A\)について、\begin{equation*}\Delta _{A}\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして定義されます。\(x=y\)を満たす要素\(x,y\in A\)に注目したとき、恒等関係の定義より、\begin{equation*}\left( x,y\right) \in \Delta _{A}\wedge \left( y,x\right) \in \Delta _{A}
\end{equation*}が成り立つため\(\Delta _{A}\)は非対称律を満たしません。したがって\(\Delta _{A}\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。
例(全体関係)
関係\(R\)が集合\(A\)上の全体関係であるものとします。つまり、\begin{equation*}R=A\times A
\end{equation*}です。このとき、\begin{equation*}
\exists x,y\in A:\left[ \left( x,y\right) \in A\times A\wedge \left(
y,x\right) \in A\times A\right] \end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではなく、ゆえに狭義全順序でもありません。

以下は狭義半順序である一方で狭義全順序ではない二項関係の例です。

例(集合の狭義包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)が与えられたとき、それぞれの\(\left( A,B\right) \in \mathfrak{A}\times \mathfrak{A}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\varsubsetneq B
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(\varsubsetneq \)は狭義の包含関係(真部分集合)を表す記号であり、これは包含関係\(\subset \)を用いて、\begin{equation*}A\varsubsetneq B\Leftrightarrow A\subset B\wedge A\not=B
\end{equation*}として定義されます。\(R\)は狭義半順序です。その一方で、例えば、2つの集合\(\left\{ 1,2\right\},\left\{ 2,3\right\} \)について\(\left\{ 1,2\right\}\varsubsetneq \left\{ 2,3\right\} \)と\(\left\{ 2,3\right\}\varsubsetneq \left\{ 1,2\right\} \)はともに成り立たず、さらに\(\left\{1,2\right\} \not=\left\{ 2,3\right\} \)であるため、\(R\)は三分律を満たしません。したがって\(R\)は狭義全順序ではありません。
例(空関係)
関係\(R\)が集合\(A\)上の空関係であるものとします。つまり、\begin{equation*}R=\phi
\end{equation*}です。\(R\)は狭義半順序です。加えて、異なる2つの要素\(x,y\in A\)に注目したとき、\(\left( x,y\right) \in \phi \)と\(\left( y,x\right) \in \phi \)はともに成り立たず、さらに\(x\not=y\)であるため、\(R\)は三分律を満たしません。したがって\(R\)は狭義全順序ではありません。

 

演習問題

問題(実数の狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)が狭義全順序であることを示してください。
証明

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

問題(狭義全順序)
集合\(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\)が狭義全順序であることを示してください。
証明

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

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

関連知識

大小関係
実数の大小関係

実数の集合 R 上に実数どうしの大小関係を比較する順序を定義した上で、それが全順序としての性質満たすことを公理として定めます。

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

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

狭義大小関係
実数の狭義大小関係

実数の集合 R 上に定義された大小関係を用いて、狭義大小関係と呼ばれる新たな順序を間接的に定義します。狭義大小関係は非対称律、推移律、三分律を満たす狭義全順序です。

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

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

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

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

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

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

DISCUSSION

質問とコメント

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

関係