# Lexicographic order

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An order on a direct product of partially ordered sets (cf. Partially ordered set), where the set of indices is well-ordered (cf. Totally well-ordered set), defined as follows: If , then if and only if either for all or there is an such that and for all . A set ordered by the lexicographic order is called the lexicographic, or ordinal, product of the sets . If all the sets coincide ( for all ), then their lexicographic product is called an ordinal power of and is denoted by . One also says that is ordered by the principle of first difference (as words are ordered in a dictionary). Thus, if is the series of natural numbers, then means that, for some , The lexicographic order is a special case of an ordered product of partially ordered sets (see ). The lexicographic order can be defined similarly for any partially ordered set of indices (see ), but in this case the relation on the set is not necessarily an order in the usual sense (cf. Order (on a set)).

A lexicographic product of finitely many well-ordered sets is well-ordered. A lexicographic product of chains is a chain.

For a finite , the lexicographic order was first considered by G. Cantor

in the definition of a product of order types of totally ordered sets.

The lexicographic order is widely used outside mathematics, for example in ordering words in dictionaries, reference books, etc.

How to Cite This Entry:
Lexicographic order. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lexicographic_order&oldid=13984
This article was adapted from an original article by T.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article