# 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 [3]). The lexicographic order can be defined similarly for any partially ordered set of indices $L$ (see [1]), 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.

#### References

[1] | G. Birkhoff, "Lattice theory" , Colloq. Publ. , 25 , Amer. Math. Soc. (1973) |

[2] | K. Kuratowski, A. Mostowski, "Set theory" , North-Holland (1968) |

[3] | L.A. Skornyakov, "Elements of lattice theory" , A. Hilger (1977) (Translated from Russian) |

[4a] | G. Cantor, "Beiträge zur Begründung der transfiniten Mengenlehre I" Math. Ann. , 46 (1895) pp. 481–512 |

[4b] | G. Cantor, "Beiträge zur Begründung der transfiniten Mengenlehre II" Math. Ann , 49 (1897) pp. 207–246 |

[5] | F. Hausdorff, "Grundzüge der Mengenlehre" , Leipzig (1914) (Reprinted (incomplete) English translation: Set theory, Chelsea (1978)) |

#### Comments

The question of which totally ordered sets $(X,{\prec})$ admit a function $f:X \rightarrow \mathbb{R}$ such that $x \prec x'$ if and only if $f(x) > f(x')$, is of interest in mathematical economics (utility function, cf. [a1]). The lexicographic order on $\mathbb{R}^2$ shows that not all totally ordered sets admit a utility function.

#### References

[a1] | G. Debreu, "Theory of values" , Yale Univ. Press (1959) |

**How to Cite This Entry:**

Lexicographic order.

*Encyclopedia of Mathematics.*URL: http://www.encyclopediaofmath.org/index.php?title=Lexicographic_order&oldid=34796