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.

Title	lexicographic order
Canonical name	LexicographicOrder
Date of creation	2013-03-22 15:14:05
Last modified on	2013-03-22 15:14:05
Owner	matte (1858)
Last modified by	matte (1858)
Numerical id	13
Author	matte (1858)
Entry type	Definition
Classification	msc 06A99
Defines	dictionary order