半順序関係
集合\(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\)を半順序（partial order）や順序（order）などと呼びます。半順序を規定する以上の3つの性質（反射律・反対称律・推移律）を総称して順序の公理（axiom of 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]
\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*}を半順序集合（partially ordered set）や順序集合（ordered set）などと呼びます。ただし、半順序集合について言及していることが文脈から明らかである場合には、半順序集合をシンプルに、\begin{equation*}
A
\end{equation*}と表記できます。
半順序の具体例：半順序の逆関係
半順序集合\(\left( A,\leq \right) \)が与えられた状況を想定します。その上で、半順序\(\leq \)の逆関係を、\begin{equation*}\geq \subset A\times A
\end{equation*}と表記します。逆関係の定義より、任意の\(x,y\in A\)について、以下の関係\begin{equation*}x\geq y\Leftrightarrow y\leq x
\end{equation*}が成り立ちます。つまり、もとの半順序\(\leq \)のもとで\(y\)が\(x\)以下である場合、そしてその場合にのみ逆関係\(\geq \)のもとで\(x\)は\(y\)以上になります。
半順序\(\leq \)の逆関係\(\geq \)は半順序です。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\geq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\geq y\wedge y\geq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\geq y\wedge y\geq
z\right) \Rightarrow x\geq z\right]
\end{eqnarray*}が成り立ちます。
半順序の具体例：実数の大小関係
実数どうしを比較する通常の大小関係\(\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]
\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*}が成り立ちます。
半順序の具体例：自然数の整除関係
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*}が成り立ちます。
半順序の具体例：恒等関係
集合\(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*}が成り立ちます。
半順序ではない二項関係の具体例
逆に、集合\(A\)上の二項関係\(R\)が順序の公理を満たさない場合、すなわち\(R\)が反射律、反対称律、そして推移律の中の少なくとも1つを満たさない場合、\(R\)は半順序ではありません。
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではありません（演習問題）。
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。この\(R\)は\(\mathbb{R} \)上の半順序ではありません（演習問題）。
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではありません（演習問題）。
\end{equation*}が成り立ちますが、以上の事実は\(\phi \)が\(A\)上の二項関係であることを意味します。空集合\(\phi \)を二項関係とみなした場合、これを空関係と呼びます。空関係\(\phi \)は\(A\)上の半順序ではありません（演習問題）。
\end{equation*}が成り立ちますが、以上の事実は\(A\times A\)が\(A\)上の二項関係であることを意味します。直積\(A\times A\)を二項関係とみなした場合、これを全体関係と呼びます。全体関係\(A\times A\)は\(A\)上の半順序ではありません（演習問題）。
演習問題
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではないことを示してください。
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。ただし、\(<\)は狭義の大小関係であり、\(x<y\)は\(x\)が\(y\)よりも小さいことを意味します。この\(R\)は\(\mathbb{R} \)上の半順序ではないことを示してください。
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではないことを示してください。
\end{equation*}が成り立ちますが、これは\(\phi \)が\(A\)上の二項関係であることを意味します。空集合\(\phi \)を二項関係とみなした場合、これを空関係と呼びます。空関係\(\phi \)は\(A\)上の半順序ではないことを示してください。
\end{equation*}が成り立ちますが、これは直積\(A\times A\)が\(A\)上の二項関係であることを意味します。直積\(A\times A\)を二項関係とみなした場合、これを全体関係と呼びます。全体関係\(A\times A\)は\(A\)上の半順序ではないことを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】