# Definition:Lexicographic Order/Tuples of Equal Length/Cartesian Space

Jump to navigation
Jump to search

## Definition

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$

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.

## 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
**Lexicographic Order**can be found here.

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.1$: Mathematical Induction: Exercise $15 \ \text{(d)}$