Lexicographic Order

order-theory

Definition

Lexicographic Order

Let be a totally ordered set under . For two finite sequences and over , is lexicographically smaller than , written , iff either:

1. is a proper prefix of : and for all , or
2. at the first position where and differ, .

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 overrides any agreement at all later positions.

Recursive Characterisation

Let and where denotes the head and the tail. Then:

Examples

Mismatch at first position

because . The elements after position 1 are irrelevant.

Prefix rule

. The first two elements match and the first sequence is a strict prefix.

Empty sequence

. The empty sequence is the smallest element.

Mismatch after common prefix

because at the first differing position.