Namespaces
Variants
Actions

Difference between revisions of "Lexicographic order"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (ce)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
An order on a [[Direct product|direct product]]
+
{{TEX|done}}{{MSC|06A}}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583301.png" /></td> </tr></table>
+
A [[partial order]] on a [[direct product]]
 +
$$
 +
X = \prod_{\alpha \in L} X_\alpha
 +
$$
 +
of [[partially ordered set]]s $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\ .
 +
$$
  
of partially ordered sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583302.png" /> (cf. [[Partially ordered set|Partially ordered set]]), where the set of indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583303.png" /> is well-ordered (cf. [[Totally well-ordered set|Totally well-ordered set]]), defined as follows: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583304.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583305.png" /> if and only if either <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583306.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583307.png" /> or there is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583308.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l0583309.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833010.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833011.png" />. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833012.png" /> ordered by the lexicographic order is called the lexicographic, or ordinal, product of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833013.png" />. If all the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833014.png" /> coincide (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833015.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833016.png" />), then their lexicographic product is called an ordinal power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833017.png" /> and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833018.png" />. One also says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833019.png" /> is ordered by the principle of first difference (as words are ordered in a dictionary). Thus, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833020.png" /> is the series of natural numbers, then
+
The lexicographic order is a special case of an ordered product of partially ordered sets (see [[#References|[3]]]). The lexicographic order can be defined similarly for any partially ordered set of indices $L$ (see [[#References|[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)|Order (on a set)]]).
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833021.png" /></td> </tr></table>
 
 
 
means that, for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833022.png" />,
 
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833023.png" /></td> </tr></table>
 
 
 
The lexicographic order is a special case of an ordered product of partially ordered sets (see [[#References|[3]]]). The lexicographic order can be defined similarly for any partially ordered set of indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833024.png" /> (see [[#References|[1]]]), but in this case the relation on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833025.png" /> is not necessarily an order in the usual sense (cf. [[Order (on a set)|Order (on a set)]]).
 
  
 
A lexicographic product of finitely many well-ordered sets is well-ordered. A lexicographic product of chains is a [[Chain|chain]].
 
A lexicographic product of finitely many well-ordered sets is well-ordered. A lexicographic product of chains is a [[Chain|chain]].
  
For a finite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833026.png" />, the lexicographic order was first considered by G. Cantor
+
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.
 
 
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.
 
The lexicographic order is widely used outside mathematics, for example in ordering words in dictionaries, reference books, etc.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  K. Kuratowski,  A. Mostowski,  "Set theory" , North-Holland  (1968)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  L.A. Skornyakov,  "Elements of lattice theory" , A. Hilger  (1977)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4a]</TD> <TD valign="top">  G. Cantor,  "Beiträge zur Begründung der transfiniten Mengenlehre I"  ''Math. Ann.'' , '''46'''  (1895)  pp. 481–512</TD></TR><TR><TD valign="top">[4b]</TD> <TD valign="top">  G. Cantor,  "Beiträge zur Begründung der transfiniten Mengenlehre II"  ''Math. Ann'' , '''49'''  (1897)  pp. 207–246</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  G. Birkhoff,  "Lattice theory" , ''Colloq. Publ.'' , '''25''' , Amer. Math. Soc.  (1973)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  K. Kuratowski,  A. Mostowski,  "Set theory" , North-Holland  (1968)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  L.A. Skornyakov,  "Elements of lattice theory" , A. Hilger  (1977)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[4a]</TD> <TD valign="top">  G. Cantor,  "Beiträge zur Begründung der transfiniten Mengenlehre I"  ''Math. Ann.'' , '''46'''  (1895)  pp. 481–512</TD></TR>
 +
<TR><TD valign="top">[4b]</TD> <TD valign="top">  G. Cantor,  "Beiträge zur Begründung der transfiniten Mengenlehre II"  ''Math. Ann'' , '''49'''  (1897)  pp. 207–246</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  F. Hausdorff,  "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR>
 +
</table>
  
  
  
 
====Comments====
 
====Comments====
The question of which totally ordered sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833027.png" /> admit a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833028.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833029.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833030.png" />, is of interest in mathematical economics (utility function, cf. [[#References|[a1]]]). The lexicographic order on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058330/l05833031.png" /> shows that not all totally ordered sets admit a utility function.
+
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. [[#References|[a1]]]). The lexicographic order on $\mathbb{R}^2$ shows that not all totally ordered sets admit a utility function.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G. Debreu,  "Theory of values" , Yale Univ. Press  (1959)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G. Debreu,  "Theory of values" , Yale Univ. Press  (1959)</TD></TR></table>

Latest revision as of 09:37, 22 November 2014

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=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