WIIS

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

全順序(全順序集合)

目次

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

全順序関係

集合\(A\)上の半順序\(\leq \)が与えられているものとします。つまり、\(\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] \end{eqnarray*}が成り立つということです。以上の条件に加えて\(\leq \)が完備律を満たす場合には、すなわち、\begin{equation*}\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}が成り立つ場合には、\(\leq \)を全順序(total order)や線型順序(linear order)などと呼びます。ただし、全順序を順序(order)と呼ぶ場合もあります。順序という用語は半順序と全順序のどちらの意味でも使われるため、文脈から判断する必要があります。

繰り返しになりますが、全順序とは完備律を満たす半順序として定義されます。完備律を加えることにより何が変わるのでしょうか。集合\(A\)の2つの要素\(x,y\)を任意に選んだとき、半順序\(\leq \)のもとでは\(x\leq y\)や\(y\leq x\)が成り立つとは限らず、したがって\(x\)と\(y\)の間の大小を比較できるとは限りません。一方、半順序\(\leq \)が完備律を満たす場合には\(x\leq y\)と\(y\leq x\)の少なくとも一方が成り立つこと、すなわち、\begin{equation}x\leq y\vee y\leq x \quad \cdots (1)
\end{equation}が成り立つことが保証されるため、\(x\)と\(y\)の大小を常に比較できます。\(\left( 1\right) \)が成り立つ場合、\(x\)と\(y\)は比較可能(comparable)であると言います。完備律は集合\(A\)の任意の2つの要素が比較可能であることを保証します。言い換えると、集合\(A\)上の全順序とは、\(A\)上の任意の2つの要素を比較可能であるような半順序です。

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

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

表:真理値表

\(\left( a\right) \)は\(x\)と\(y\)が等しい場合、\(\left( b\right) \)は\(x\)が\(y\)より小さい場合、\(\left( c\right) \)は\(y\)が\(x\)より小さい場合にそれぞれ相当する一方で、\(\left( d\right) \)では\(x\)と\(y\)の大小に関する情報が存在せず、この場合にはそもそも\(x\)と\(y\)を比較することさえできません。ただ、\(\leq \)が完備律を満たす場合には\(x\leq y\)と\(y\leq x\)の少なくとも一方が成り立つことが保証されるため、\(\left( d\right) \)のケースが起こる可能性は排除されます。つまり、半順序\(\leq \)が完備律を満たす場合には、すなわち\(\leq \)が全順序である場合には、2つの点\(x,y\in A\)を任意に選んだときに\(\left( a\right) ,\left( b\right),\left( c\right) \)の中のどれか1つが成り立つこと、すなわち、\begin{equation*}x=y,\quad x<y,\quad y<x
\end{equation*}の中のどれか1つが成り立つことが保証されます。つまり、\(<\)は三分律を満たすということです。全順序\(\leq \)のもとでは、集合\(A\)の2つの要素を任意に選んだとき、両者の大小を必ず判定できます。

命題(完備律の含意)
集合\(A\)上の全順序\(\leq \)が与えられたとき、任意の\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow \left[ x\leq y\wedge x\not=y\right] \end{equation*}を満たすものとして定義される\(A\)上の狭義順序\(<\)は三分律を満たす。すなわち、2つの要素\(x,y\in A\)を任意に選んだとき、\begin{equation*}x=y,\quad x<y,\quad y<x
\end{equation*}の中のどれか1つ、そして1つだけが必ず成立する。

集合\(A\)上に全順序\(\leq \)が定義されているとき、これを全順序集合(totally ordered set)や線型順序集合(linearly ordered set)などと呼び、\begin{equation*}\left( A,\leq \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\leq y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は全順序です(演習問題)。
例(自然数の整除関係)
集合\(A=\left\{ 3,9,27,81\right\} \)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。\(R\)は全順序です(演習問題)。ちなみに、同様の二項関係\(R\)をすべての自然数からなる集合\(\mathbb{N} \)上に定義したとき、これは半順序である一方で完備律を満たさないため全順序ではありません(後述)。

 

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

逆に、集合\(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\)を定義します。同じ学年に属する異なる2人の学生\(x,y\in A\)に注目したとき、\(x\)と\(y\)が同じ学年で、\(y\)と\(x\)が同じ学年である一方で、\(x\)と\(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\)を定義します。実数\(x\in \mathbb{R} \)を任意に選んだとき、\(x<x\)すなわち\(R\left( x,y\right) \)は成り立たないため\(R\)は反射律を満たしません。したがって\(R\)は半順序ではなく、ゆえに全順序でもありません。
例(空関係)
関係\(R\)が集合\(A\)上の空関係であるものとします。つまり、\begin{equation*}R=\phi
\end{equation*}です。\(x\in A\)を任意に選んだとき、\begin{equation*}\left( x,x\right) \not\in \phi
\end{equation*}が成り立つため\(R\)は反射律を満たしません。したがって\(R\)は半順序ではなく、ゆえに全順序でもありません。
例(全体関係)
関係\(R\)が集合\(A\)上の全体関係であるものとします。つまり、\begin{equation*}R=A\times A
\end{equation*}です。異なる2つの要素\(x,y\in A\)を任意に選んだとき、\begin{equation*}\left[ \left( x,y\right) \in A\times A\wedge \left( y,x\right) \in A\times A\right] \Rightarrow x=y
\end{equation*}は偽であるため\(R\)は反対称律を満たしません。したがって\(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\)を定義します。相似だが辺の長さが異なる2つの三角形\(x,y\in A\)に注目したとき、\(x\)と\(y\)が相似で、\(y\)と\(x\)が相似である一方で、\(x\)と\(y\)は異なる三角形であるため\(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\)を定義します。\(R\)は半順序です。その一方で、例えば、2つの集合\(\left\{ 1,2\right\} ,\left\{ 2,3\right\} \)について\(\left\{ 1,2\right\} \subset \left\{ 2,3\right\} \)と\(\left\{2,3\right\} \subset \left\{ 1,2\right\} \)はともに成り立たず、したがって\(R\)は完備律を満たさず、ゆえに\(R\)は全順序ではありません。
例(自然数の整除関係)
すべての自然数からなる集合\(\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\)は全順序ではありません。
例(恒等関係)
集合\(A\)上の恒等関係\(\Delta_{A}\)は、任意の\(\left( x,y\right) \in A\times A\)について、\begin{equation*}\Delta _{A}\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして定義されます。\(R\)は半順序です。その一方で、異なる2つの要素\(x,y\in A\)に注目したとき\(x\not=y\)かつ\(y\not=x\)が成り立つため、\(\Delta _{A}\)の定義より\(\Delta_{A}\left( x,y\right) \)と\(\Delta _{A}\left( y,x\right) \)はともに成り立ちません。したがって\(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\)を定義します。\(R\)が全順序であることを示してください。
証明

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

問題(自然数の整除関係)
集合\(A=\left\{ 3,9,27,81\right\} \)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。\(R\)が全順序であることを示してください。
証明

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

問題(標準的順序)
2次元ユークリッド空間\(\mathbb{R} ^{2}\)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} ^{2}\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x_{1}\leq y_{1}\wedge x_{2}\leq y_{2}
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x_{i},y_{i}\ \left( i=1,2\right) \)はそれぞれ点\(x,y\)の第\(i\)成分であり、\(\leq \)は\(\mathbb{R} \)上の大小関係です。\(R\)は全順序でしょうか。議論してください。
解答を見る

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

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

関連知識

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

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

大小関係
実数の大小関係

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

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

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

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

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

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

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

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

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

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

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

全順序
順序部分集合

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

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

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

DISCUSSION

質問とコメント

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

関係