Namespaces
Variants
Actions

Lexicographic order

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 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://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