Definition:Lexicographic Order/Tuples of Equal Length

Definition

Let $n \in \N_{>0}$.

Let $\struct {S_1, \preccurlyeq_1}, \struct {S_2, \preccurlyeq_2}, \ldots, \struct {S_n, \preccurlyeq_n}$ be ordered sets.

Let $\ds S = \prod_{k \mathop = 1}^n S_k = S_1 \times S_2 \times \cdots \times S_n$ be the Cartesian product of $S_1$ to $S_n$.

The lexicographic order on $S$ is the relation $\preccurlyeq_l$ defined on $S$ as:

$\tuple {x_1, x_2, \ldots, x_n} \preccurlyeq_l \tuple {y_1, y_2, \ldots, y_n}$ if and only if:

$\exists k: 1 \le k \le n: \paren {\forall j: 1 \le j < k: x_j = y_j} \land \paren {x_k \prec_k y_k}$

or:

$\forall j: 1 \le j \le n: x_j = y_j$

That is, if and only if:

the elements of a pair of $n$-tuples are either all equal

or:

they are all equal up to a certain point, and on the next one they are comparable and they are different.

Cartesian Space

The definition can be refined to apply to a Cartesian $n$-space:

Let $\struct {S, \preccurlyeq}$ be an ordered set.

Let $n \in \N_{>0}$.

Let $S^n$ be the cartesian $n$th power of $S$:

$S^n = \underbrace {S \times S \times \cdots \times S}_{\text {$n$ times} }$

The lexicographic order on $S^n$ is the relation $\preccurlyeq_l$ defined on $S^n$ as:

$\tuple {x_1, x_2, \ldots, x_n} \preccurlyeq_l \tuple {y_1, y_2, \ldots, y_n}$ if and only if:

$\exists k: 1 \le k \le n: \paren {\forall j: 1 \le j < k: x_j = y_j} \land \paren {x_k \prec y_k}$

or:

$\forall j: 1 \le j \le n: x_j = y_j$

Also known as

Lexicographic order can also be referred to as the more unwieldy lexicographical ordering.

Some sources refer to it as dictionary order.

Some sources classify the lexicographic order as a variety of order product.

Hence the term lexicographic product can occasionally be seen.

The mathematical world is crying out for a less unwieldy term to use.

Some sources suggest Lex, but this has yet to filter through to general usage.

Also see

• Results about the lexicographic order can be found here.

Linguistic Note

The term lexicographic order derives from the word lexicon, which is a linguistic term whose meaning is akin to dictionary.

The origin of its use in this context is apparent from the fact that the tuples are ordered in the way they would be if their terms are letters of the alphabet being ordered in standard alphabetical order.