# Lexicographic order

2010 Mathematics Subject Classification: Primary: 06A [MSN][ZBL]

A partial order on a direct product $$X = \prod_{\alpha \in L} X_\alpha$$ of partially ordered sets $X_\alpha$, where the set of indices $L$ is well-ordered (cf. Totally well-ordered set), defined as follows: If $(x_\alpha), (y_\alpha) \in X$, then $(x_\alpha) \leq(y_\alpha) \in X$ if and only if either $x_\alpha = y_\alpha$ for all $\alpha \in L$ or there is an $\alpha \in L$ such that $x_\alpha < y_\alpha$ and $x_\beta = y_\beta$ for all $\beta < \alpha$. A set $X$ ordered by the lexicographic order is called the lexicographic, or ordinal, product of the sets $X_\alpha$. If all the sets $X_\alpha$ coincide ($X_\alpha = Y$ for all $\alpha \in L$), then their lexicographic product is called an ordinal power of $Y$ and is denoted by ${}^L Y$. One also says that $X$ is ordered by the principle of first difference (as words are ordered in a dictionary). Thus, if $L$ is the sequence of natural numbers, then $$(x_1,\ldots,x_n,\ldots) < (y_1,\ldots,y_n,\ldots)$$ means that, for some $k$, $$x_k < y_k \ \ \text { and } \ \ x_i = y_i \text{ for all } i<k\ .$$

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 $L$ (see ), but in this case the relation on the set $L$ 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 $L$, 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=34796
This article was adapted from an original article by T.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article