順序集合
実数全体の集合 R およびその部分集合(例えば、自然数全体の集合 N, 整数全体の集合 Z, 有理数全体の集合 Q)は、通常の大小関係により全順序集合となる。しかし、複素数全体の集合 C には複素数の乗法と"両立"する全順序は存在しない(順序体でない)。単に全順序を入れるだけであれば、直積集合 R × R に辞書式順序を定めることができる。
自然数全体の成す集合は整除関係を順序として半順序集合である。
集合の冪集合に対して、包含関係による順序を入れると半順序集合となる。これはもとの集合の元の個数が2個以上であれば全順序でない。例えば {1, 2, 3} の冪集合
{ ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } {\displaystyle {\bigl \{}\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}{\bigr \}}}
P を有限集合とし、「<」を P 上の狭義の半順序とするとき、以下のようにして P を自然に単純有向グラフと見なせる:
頂点:P の元
a ∈ P から b ∈ P への辺がある ⇔ a < b であり、しかも a < c < b を満たす c ∈ P が存在しない
(すなわち b は a を被覆している)
この有向グラフを図示したものをハッセ図という。
ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。例えばこの図で {x} と {x, y, z} は比較可能だが、{x} と {y} は比較不能である。また単集合の族 {{x}, {y}, {z}} は反鎖である。さらに {x} は {x, z} によって被覆されるが、{x, y, z} には被覆されない。
なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に (V, E) を閉路を持たない有限な単純有向グラフとすると、V 上に以下の順序を入れることで V を半順序集合と見なせる:
a < b ⇔ a から b への道がある
したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。
一方、等しいことを許容しない順序は狭義の(半)順序と呼ばれ、以下のように定義される:
a < b ⟺ ( a ≤ b ∧ a ≠ b ) {\displaystyle a<b\iff (a\leq b\land a\neq b)} ...(1)
狭義の逆順序「>」も同様に定義される。
狭義の順序「<」の対義語として、等しいことも許容する順序「≤」のことを広義の(半)順序(もしくは弱い意味 (weak) の(半)順序、反射的 (reflexive) な(半)順序)という。
(1) 式で定義された「<」を「≤」の反射的簡約 (reflexive reduction) という。
「≤」が半順序であるとき、その反射的簡約「<」は任意の a, b, c ∈ P に対して以下を満たす:
非反射性:¬(a < a);
非対称性:a < b ならば ¬(b < a); (非反射性と推移性から従う)
推移性:a < b かつ b < c ならば a < c
以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質(非対称性は非反射性と推移性より得られるので条件としては不要)を満たすものを狭義の順序として定義し、広義の順序を
a ≤ b ⟺ a < b ∨ a = b {\displaystyle a\leq b\iff a<b\lor a=b} ...(2)
により定義することもできる。この場合、(2) 式で定義された「≤」を「<」の反射閉包(英語版)という。「<」が前述の3条件を満たせば反射閉包「≤」が半順序であることを簡単に示すことができる。