# lexicographic order

Let $A$ be a set equipped with a total order $<$, and let $A^{n}=A\times\cdots\times A$ be the $n$-fold Cartesian product of $A$. Then the lexicographic order $<$ on $A^{n}$ is defined as follows:

If $a=(a_{1},\ldots,a_{n})\in A^{n}$ and $b=(b_{1},\ldots,b_{n})\in A^{n}$, then $a if $a_{1} or

 $\displaystyle a_{1}$ $\displaystyle=$ $\displaystyle b_{1},$ $\displaystyle\vdots$ $\displaystyle a_{k}$ $\displaystyle=$ $\displaystyle b_{k},$ $\displaystyle a_{k+1}$ $\displaystyle<$ $\displaystyle b_{k+1}$

for some $k=1,\ldots,n-1$.

## Examples

• The lexicographic order yields a total order on the field of complex numbers.

• The lexicographic order of words of finite length consisting of letters ${}^{\prime}\ \ {}^{\prime}$ (space) $ is the dictionary order. To compare words of different length, one simply pads the shorter with ${}^{\prime}\ \ {}^{\prime}$s from the right. For example, $\operatorname{prove}<\operatorname{proved}<\operatorname{proven}$.

## Properties

Title lexicographic order LexicographicOrder 2013-03-22 15:14:05 2013-03-22 15:14:05 matte (1858) matte (1858) 13 matte (1858) Definition msc 06A99 dictionary order