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<b$ if $a_{1}<b_{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) $<a<b<\\cdots<y<z$ 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

•
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.