Jump to content

Order Theory/Lexicographic order

From Wikibooks, open books for an open world

Definition (lexicographic order):

Let be preordered sets, where is well-ordered. Define an order on , the Cartesian product, by

.

Proposition (lexicographic order induced by posets is poset):

Whenever

Proposition (lexicographic order induced by total orders is total):

Whenever is a well-ordered set and are totally ordered sets, the lexicographic order on is total.

Proof: Let any two elements and of be given. Then either , or there exists a smallest so that . Since is total, either or , and thus either or .