辞書式順序
整列順序の入った添字集合 I で添字づけられた全順序集合の族 (Ai)i ∈ I が与えられたとする。このとき、直積集合 ∏i ∈ I Ai 上に以下のようにして定められる順序は ∏i ∈ I Ai 上の辞書式順序と呼ばれる:
( a i ) i < ( b i ) i ⟺ a j < b j ( j = min { i ∈ I ∣ a i ≠ b i } ) . {\displaystyle (a_{i})_{i}<(b_{i})_{i}\iff a_{j}<b_{j}\quad (j=\min \left\{i\in I\mid a_{i}\neq b_{i}\right\}).}
上の定義は I が特に有限集合 {1, ... , n} の場合にも適用できる。その場合には次のように言いかえることができる。すなわち A1, ... , An を全順序集合とするとき、直積集合 A1 × ... × An 上の辞書式順序とは次のようになる: a = (a1, ... , an) と b = (b1, ... , bn) を A1 × ... × An の元とする。
「先頭の文字」a1 と b1 が異なり、a1 < b1 ならば a < b、
反対に a1 > b1 ならば a > b とし、
a1 = b1 だったならば a2 と b2 を同様に比べる、
という操作を繰り返して a と b の間の大小関係が決定される。
辞書式順序の重要な性質に整列性を保つというものがある。つまり、順序集合 A と B が整列順序集合ならば辞書式順序をいれた直積集合も整列順序集合になる。