順序集合
自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 f: N → P(N) を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である(すなわち、x が y を割るならば x の各素因数は y の素因数にもなる)が単射ではない(例えば 12 も 6 もこの写像で {2, 3} に写る)し、順序を反映もしない(例えば 12 は 6 を割らない)。少し設定を変えて、各自然数にその素冪因子の集合を対応させる写像 g: N → P(N) を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない(実際、たとえば単集合 {4} に移る数は無い)が終域を g の値域 g(N) に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な分配束(英語版)と呼ばれる半順序集合のクラスに対して一般化することができる(バーコフの表現定理(英語版)の項を参照)。
上では順序を記号 ≤ で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 ≤ と区別するため、順序の記号として ≺ {\displaystyle \prec } や ≪ {\displaystyle \ll } を使うこともある。
全順序を線型順序ともいい、全順序集合を鎖と呼ぶこともある。また半順序集合の部分集合 A で A の任意の異なる2元が比較不能であるものを反鎖(英語版)という。半順序集合のことを部分順序集合と呼ぶこともあるが部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。
半順序集合の元 a が他の元 b によって被覆される(英語版) (a <: b) とは、a は b よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう。つまり a <: b {\displaystyle a<:b} とは次の3つがすべて成り立つことである: a ≤ b , a ≠ b , ¬ [ ∃ c s.t. a < c < b ] . {\displaystyle a\leq b,\quad a\neq b,\quad \neg [\exists \ c\ {\text{s.t.}}\ a<c<b].}
「大きい、もしくは等しい」ことを意味する順序関係は「≤」の逆順序と呼ばれ、
a ≥ b ⟺ b ≤ a {\displaystyle a\geq b\iff b\leq a}
により定義される。
任意の半順序集合(および前順序集合)は、任意の射集合が高々一つの元からなる圏と見なすことができる。具体的には、射の集合を x ≤ y ならば hom(x, y) = {(x, y)}(それ以外の場合は空集合)とし、(y, z)∘(x, y) = (x, z) と定義する。2つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏は同型射について閉じて(英語版)いる。
半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。