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<b$ if $a_1<b_1$ or \begin{eqnarray*} a_1 &=& b_1, \\ &\vdots & \\ a_k &=& b_k, \\ a_{k+1} &<& b_{k+1} \\ \end{eqnarray*}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 $\wspace$ (space) $<a<b<\cdots<y<z$ is the dictionary order. To compare words of different length, one simply pads the shorter with $\wspace$ s from the right. For example, $\operatorname{prove} < \operatorname{proved} < \operatorname{proven}$ .

Properties

• The lexicographic order is a total order.
• If the original set is well-ordered, the lexicographic ordering on the product is also a well-ordering.