順序は日常生活でも自然に考えている概念です。
ここでは順序の数学的な定義を紹介します。
順序は順序関係であり、二項関係の一種です。順序関係の中で代表的なものを紹介します。
前順序(preorder)
集合 \(P\) 上の二項関係 \(\leq\) が前順序(preorder)であるとは, \(\leq\) が反射的かつ推移的であることをいう.
つまり, 任意の \(a, b, c\in P\) に対して
- \(a\leq a\)
- \(a\leq b,\ b\leq c\ \Longrightarrow\ a\leq c\)
を満たすことをいう.
このとき \((P,\,\leq)\) を前順序集合(preordered set)という.
半順序(partial order)
集合 \(P\) 上の二項関係 \(\leq\) が半順序(partial order)であるとは, \(\leq\) が前順序かつ反対称的であることをいう.
つまり, 任意の \(a, b, c\in P\) に対して
- \(a\leq a\)
- \(a\leq b,\ b\leq c\ \Longrightarrow\ a\leq c\)
- \(a\leq b,\ b\leq a\ \Longrightarrow\ a=b\)
を満たすことをいう.
このとき \((P,\,\leq)\) を半順序集合(partially ordered set, poset)という.
全順序(total order)
集合 \(P\) 上の二項関係 \(\leq\) が全順序(total order)であるとは, \(\leq\) が半順序かつ比較可能(comparable)であることをいう.
つまり, 任意の \(a, b, c\in P\) に対して
- \(a\leq a\)
- \(a\leq b,\ b\leq c\ \Longrightarrow\ a\leq c\)
- \(a\leq b,\ b\leq a\ \Longrightarrow\ a=b\)
- \(a\leq b\) または \(b\leq a\)
を満たすことをいう.
このとき \((P,\,\leq)\) を全順序集合(totally ordered set)という.
比較可能(comparable)であること
- \(\forall a, b\in P,\ a\leq b\ \vee \ b\leq a\)
は完全律(total)と呼ばれたりします。
これには反射律 \(a\leq a\) が含まれているため、全順序の定義に反射律の条件はいりませんが、分かりやすさを考えて加えたままにしています。
分かりやすさから、全順序、半順序、前順序の順で例を紹介します。
例（全順序）
自然数全体 \(\mathbf{N}\) 、整数全体 \(\mathbf{Z}\) 、有理数全体 \(\mathbf{Q}\) 、実数全体 \(\mathbf{R}\) は通常の大小関係によって全順序集合となります。
例（半順序）
自然数全体 \(\mathbf{N}\) に整除関係を順序とする、つまり
- \(n\) が \(m\) を割り切るとき \(n\leq m\)
とすると \(\mathbf{N}\) は半順序集合となります。
\(1\leq 2\leq 6,\ 1\leq 3\leq 6\) とかではありますが、 \(2\) と \(3\) に順序関係はありません。よって完全律を満たしません。
例（前順序）
整数全体 \(\mathbf{Z}\) に整除関係を順序とすると、これは前順序集合となります。
\(2\leq -2\) かつ \(-2\leq 2\) ではありますが、\(2\neq -2\) です。よって反対称律を満たしません。
コメント