Lexicographic Order

order-theory

Definition

Lexicographic Order

Let $\Sigma$ be a totally ordered set under $<$. For two finite sequences $A=(a_1,\dots ,a_m)$ and $B=(b_1,\dots ,b_n)$ over $\Sigma$, $A$ is lexicographically smaller than $B$, written $A{<}_{\text{lex}}B$, iff either:

1. $A$ is a proper prefix of $B$: $m<n$ and $a_i=b_i$ for all $i\in \{1,\dots ,m\}$, or
2. at the first position $k$ where $A$ and $B$ differ, $a_k<b_k$.

Intuition

Intuition

Lexicographic order works like dictionary ordering. Compare the first elements; if they differ, the smaller element determines the order. If they match, discard them and compare the rest. If one sequence runs out of elements first, it is smaller.

Early positions carry infinite weight: a difference at position $1$ overrides any agreement at all later positions.

Recursive Characterisation

Let $A=h_A::T_A$ and $B=h_B::T_B$ where $h$ denotes the head and $T$ the tail. Then:

$$A{<}_{\text{lex}}B⟺\{\begin{array}{ll}\text{true}& \text{if }A=\epsilon \text{ and }B\ne \epsilon \\ \text{false}& \text{if }B=\epsilon \\ \text{true}& \text{if }{h}_A<h_B\\ \text{false}& \text{if }{h}_B<h_A\\ T_A{<}_{\text{lex}}{T}_B& \text{if }{h}_A=h_B\end{array}$$

Examples

Mismatch at first position

$(1,1000){<}_{\text{lex}}(2,0)$ because $1<2$. The elements after position 1 are irrelevant.

Prefix rule

$(1,2){<}_{\text{lex}}(1,2,0)$. The first two elements match and the first sequence is a strict prefix.

Empty sequence

$(){<}_{\text{lex}}(5)$. The empty sequence is the smallest element.

Mismatch after common prefix

$(3,4,1){<}_{\text{lex}}(3,4,8)$ because $1<8$ at the first differing position.