全順序関係
集合\(A\)上の二項関係\(R\)が与えられているものとします。つまり、\begin{equation*}R\subset A\times A
\end{equation*}です。特に、集合\(A\)上の二項関係\(R\)が半順序であることとは、反射律、反対称律、そして推移律を満たすこと、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:\left( x,x\right) \in R \\
&&\left( O_{2}\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( O_{3}\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( O_{4}\right) \ \forall x,y\in A:\left[ \left( x,y\right) \in R\vee
\left( y,x\right) \in R\right]
\end{equation*}を満たす場合には、このような二項関係\(R\)を全順序（total order）や線型順序（linear order）などと呼びます。全順序を規定する以上の4つの性質（反射律・反対称律・推移律・完備律）を総称して全順序の公理（axiom of total order）と呼びます。
多くの場合、半順序と同様に、全順序を表す記号として\(\leq \)を採用します。つまり、集合\(A\)上の全順序\(R\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}x\leq y\Leftrightarrow \left( x,y\right) \in R
\end{equation*}を満たすものとして記号\(x\leq y\)の意味を定義するということです。この場合、任意の\(x,y\in A\)について、\begin{equation*}\lnot \left( x\leq y\right) \Leftrightarrow \left( x,y\right) \not\in R
\end{equation*}という関係もまた成立することに注意してください。この記号\(\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] \\
&&\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{eqnarray*}となります。
集合\(A\)上の全順序\(\leq \)が与えられたとき、要素\(x,y\in A\)について\(x\leq y\)が成り立つ場合には、\(x\)は\(y\)以下（\(x\) is less than or euqal to \(y\)）であるとか、\(y\)は\(x\)以上（\(y\) is greater than or eual to \(x\)）であるとか、\(x\)は\(y\)を超えない（\(x\) is not greaterthan \(y\)）などと言います。
集合\(A\)上に全順序\(\leq \)が定義されている場合、これらの組\begin{equation*}\left( A,\leq \right)
\end{equation*}を全順序集合（totally ordered set）や線型順序集合（linearly ordered set）などと呼びます。ただし、全順序集合について言及していることが文脈から明らかである場合には、全順序集合をシンプルに、\begin{equation*}
A
\end{equation*}と表記できます。
全順序と半順序の違い
集合\(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[ \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*}を満たす二項関係として定義されます。これらの性質に加えて、完備律\begin{equation*}
\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{equation*}を満たす場合、\(\leq \)を全順序と呼びます。完備律を加えることにより何が変わるのでしょうか。
半順序\(\leq \)が完備律を満たさない場合には、完備律の否定である以下の命題\begin{equation*}\exists x,y\in A:\lnot \left( x\leq y\right) \wedge \lnot \left( y\leq
x\right)
\end{equation*}が成り立つ可能性があります。つまり、半順序\(\leq \)のもとでは\(x\leq y\)と\(y\leq x\)がともに成立しないような\(A\)の要素\(x,y\)が存在する事態が起こり得るため、\(A\)の要素どうしを比較できるとは限りません。一方、半順序\(\leq \)が完備律を満たす場合には、すなわち\(\leq \)が全順序である場合には、\(A\)の任意の要素\(x,y\)に対して\(x\leq y\)または\(y\leq x\)の少なくとも一方が成り立つため、すなわち、\begin{equation}x\leq y\vee y\leq x \quad \cdots (1)
\end{equation}が成り立つため、\(A\)の要素どうしを必ず比較できます。\(\left( 1\right) \)が成り立つ場合、\(x\)と\(y\)は比較可能（comparable）であると言います。集合\(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 \)が完備律を満たす場合には、すなわち\(\leq \)が全順序である場合には\(x\leq y\)と\(y\leq x\)の少なくとも一方が成り立つことが保証されるため、\(\left( d\right) \)のケースが起こる可能性は排除されます。逆に、\(\leq \)が全順序でない場合には、\(\leq \)は完備律を満たすとは限らないため、\(\left( d\right) \)が起こる可能性を排除できません。
以上の議論より、\(\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つの要素を任意に選んだとき、両者の大小を必ず判定できます。
\end{equation*}の中のどれか1つ、そして1つだけが必ず成立する。
全順序の具体例：実数の大小関係
実数どうしを比較する通常の大小関係\(\leq \)は実数集合\(\mathbb{R} \)上に定義された二項関係です。実際、大小関係\(\leq \)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、以下の関係\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x\leq 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\)を大小関係\(\leq \)と同一視することにより、大小関係\(\leq \)を\(\mathbb{R} \)上の二項関係とみなすことができます。
実数集合\(\mathbb{R} \)上に定義された大小関係\(\leq \)は\(\mathbb{R} \)上の全順序です。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in \mathbb{R} :x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in \mathbb{R} :\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in \mathbb{R} :\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in \mathbb{R} :\left( x\leq y\vee y\leq x\right)
\end{eqnarray*}が成り立ちます。
全順序ではない半順序の具体例：集合の包含関係
全体集合\(U\)を任意に選んだ上で、その部分集合どうしの包含関係を判定する状況を想定します。任意の集合\(A,B\in 2^{U}\)について、以下の関係\begin{equation*}\left( A,B\right) \in R\Leftrightarrow A\subset 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\)を包含関係\(\subset \)と同一視することにより、包含関係\(\subset \)を\(2^{U}\)上の二項関係とみなすことができます。
集合\(U\)のべき集合\(2^{U}\)上に定義された包含関係\(\subset \)は\(2^{U}\)上の半順序である一方で全順序ではありません。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall A\in 2^{U}:A\subset A \\
&&\left( O_{2}\right) \ \forall A,B\in 2^{U}:\left[ \left( A\subset B\wedge
B\subset A\right) \Rightarrow A=B\right] \\
&&\left( O_{3}\right) \ \forall A,B,C\in 2^{U}:\left[ \left( A\subset
B\wedge B\subset C\right) \Rightarrow A\subset C\right]
\end{eqnarray*}が成り立つ一方で、\begin{equation*}
\left( O_{4}\right) \ \forall A,B\in 2^{U}:\left( A\subset B\vee B\subset
A\right)
\end{equation*}は成り立つとは限りません。以下の例より明らかです。
\left\{ 2,3\right\} &\in &2^{\mathbb{N} }
\end{eqnarray*}に注目したとき、\begin{eqnarray*}
\left\{ 1,2\right\} &\subset &\left\{ 2,3\right\} \\
\left\{ 2,3\right\} &\subset &\left\{ 1,2\right\}
\end{eqnarray*}はともに成立せず、したがって、\(2^{\mathbb{N} }\)上に定義された包含関係\(\subset \)は完備律を満たしません。
全順序ではない半順序の具体例：自然数の整除関係
2つの自然数\(m,n\in \mathbb{N} \)について、\(m\)が\(n\)の倍数（\(n\)が\(m\)の約数）であることを、\begin{equation*}n|m
\end{equation*}と表記するものと定めます。これを整除関係と呼びます。その上で、任意の自然数\(m,n\in \mathbb{N} \)について、以下の関係\begin{equation*}\left( m,n\right) \in R\Leftrightarrow n|m
\end{equation*}を満たすものとして\(\mathbb{N} \)上の二項関係\begin{equation*}R\subset \mathbb{N} \times \mathbb{N} \end{equation*}を定義します。つまり、自然数\(m,n\)について、\(m\)が\(n\)の倍数である場合、そしてその場合にのみ\(\left( m,n\right) \in R\)が成り立つものとして\(\mathbb{N} \)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を整除関係\(|\)と同一視することにより、整除関係\(|\)を\(\mathbb{N} \)上の二項関係とみなすことができます。
自然数集合\(\mathbb{N} \)上に定義された整除関係\(|\)は\(\mathbb{N} \)上の半順序である一方で全順序ではありません。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall m\in \mathbb{N} :m|m \\
&&\left( O_{2}\right) \ \forall m,n\in \mathbb{N} :\left[ \left( n|m\wedge m|n\right) \Rightarrow m=n\right] \\
&&\left( O_{3}\right) \ \forall l,m,n\in \mathbb{N} :\left[ \left( n|m\wedge m|l\right) \Rightarrow n|l\right]
\end{eqnarray*}が成り立つ一方で、\begin{equation*}
\left( O_{4}\right) \ \forall m,n\in \mathbb{N} :\left( n|m\vee m|n\right)
\end{equation*}は成り立つとは限りません。以下の例より明らかです。
2 &\in &\mathbb{N} \\
3 &\in &\mathbb{N} \end{eqnarray*}に注目したとき、\(2\)と\(3\)はお互いに一方が他方の倍数ではないため、\begin{eqnarray*}&&2|3 \\
&&3|2
\end{eqnarray*}はともに成立せず、したがって、\(\mathbb{N} \)上に定義された整除関係\(|\)は完備律を満たしません。
自然数集合\(\mathbb{N} \)上に定義された整除関係\(|\)は完備律を満たさないため全順序ではないことが明らかになりました。一方、整除関係\(|\)の定義域として\(\mathbb{N} \)とは異なる集合\(A\)を採用すれば、\(|\)は全順序になり得ます。以下の例より明らかです。
A=\left\{ 3,9,27,81\right\}
\end{equation*}上に整除関係\(|\)を定義すれば、これは\(A\)上の全順序になります（演習問題）。
全順序ではない半順序の具体例：恒等関係
集合\(A\)が与えられたとき、任意の要素\(x,y\in A\)について、以下の関係\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x=y
\end{equation*}を満たすものとして\(A\)上の二項関係\begin{equation*}R\subset A\times A
\end{equation*}を定義します。このような関係\(R\)を恒等関係（identity relation）と呼びます。つまり、要素\(x,y\)について、\(x\)と\(y\)が等しい場合、そしてその場合にのみ\(\left( x,y\right) \in R\)が成り立つものとして\(A\)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を相等関係\(=\)と同一視することにより、相等関係\(=\)を\(\mathbb{N} \)上の二項関係とみなすことができます。
集合\(A\)上に定義された恒等関係\(=\)は\(A\)上の半順序である一方で全順序ではありません。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x=x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x=y\wedge y=x\right)
\Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x=y\wedge
y=z\right) \Rightarrow x=z\right]
\end{eqnarray*}が成り立つ一方で、\begin{equation*}
\left( O_{4}\right) \ \forall x,y\in A:\left( x=y\vee y=x\right)
\end{equation*}は成り立つとは限りません。以下の例より明らかです。
y &=&x
\end{eqnarray*}はともに成立せず、したがって、\(A\)上に定義された恒等関係\(=\)は完備律を満たしません。
演習問題
x_{2}\leq y_{2}\right)
\end{equation*}を満たすものとして\(\mathbb{R} ^{2}\)上の二項関係\(R\)を定義します。ただし、\(x_{i},y_{i}\ \left( i=1,2\right) \)はそれぞれ点\(x,y\)の第\(i\)成分であり、\(\leq \)は\(\mathbb{R} \)上の大小関係です。\(R\)は全順序でしょうか。議論してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】