# Definition:Lexicographic Order

## Definition

Let $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ be ordered sets.

The **lexicographic order** $\struct {S_1, \preccurlyeq_1} \otimes^l \struct {S_2, \preccurlyeq_2}$ on $\struct {S_1, \preccurlyeq_1}$ and $\struct {S_2, \preccurlyeq_2}$ is the ordered set $\struct {T, \preccurlyeq_l}$ where:

- $T := S_1 \times S_2$, that is, the Cartesian product of $S_1$ and $S_2$

- $\preccurlyeq_l$ is the relation defined on $T$ as:
- $\tuple {x_1, x_2} \preccurlyeq_l \tuple {y_1, y_2} \iff \tuple {x_1 \prec_1 y_1} \lor \paren {x_1 = y_1 \land x_2 \preccurlyeq_2 y_2}$

### Tuples of Equal Length

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$

### General Definition

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

For $n \in \N: n > 0$, we define $T_n$ as the set of all ordered $n$-tuples:

- $\tuple {x_1, x_2, \ldots, x_n}$

of elements $x_j \in S$.

Let $\ds T = \bigcup_{n \mathop \ge 1} T_n$.

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

- $\tuple {x_1, x_2, \ldots, x_m} \preccurlyeq_l \tuple {y_1, y_2, \ldots, y_n}$ if and only if:
- $\exists k: 1 \le k \le \map \min {m, n}: \paren {\forall j: 1 \le j < k: x_j = y_j} \land x_k \prec y_k$

- or:
- $m \le n$ and $\forall j: 1 \le j \le m: x_j = y_j$.

### Family of Ordered Sets

Let $\struct {I, \preceq}$ be a well-ordered set.

For each $i \in I$, let $\struct {S_i, \preccurlyeq_i}$ be an ordered set.

Let $\ds D = \prod_{i \mathop \in I} S_i$ be the Cartesian product of the family $\family {\struct {S_i, \preccurlyeq_i} }_{i \mathop \in I}$ indexed by $I$.

Then the **lexicographic order** on $D$ is defined as:

- $\ds \struct {D, \preccurlyeq_D} := {\bigotimes_{i \mathop \in I} }^l \struct {S_i, \preccurlyeq_i}$

where $\preccurlyeq_D$ is defined as:

- $\forall u, v \in D: u \preccurlyeq_D v \iff \begin {cases} u = v \\ \map u i \preccurlyeq_i \map v i & \text {for the $\preceq$-smallest $i \in I$ such that $\map u i \ne \map v i$} \end {cases}$

## Ordinals

The **lexicographic order** is a relation on ordered pairs of ordinals denoted $\preccurlyeq_l$.

$\preccurlyeq_l$ is the set of all ordered pairs $\tuple {\tuple {\alpha, \beta}, \tuple {\gamma, \delta} }$ such that:

- $(1): \quad$ Each $\alpha, \beta, \gamma, \delta$ is a member of the ordinal class
- $(2): \quad$ $\alpha \in \gamma$ or $\alpha = \gamma \land \beta \in \delta$

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

## Examples

### Unit Square with Open Side

Consider the **lexicographic product** of the real intervals $\hointr 0 1$ and $\closedint 0 1$ under the usual ordering:

- $\struct {T, \preccurlyeq_l} := \struct {\hointr 0 1, \le} \otimes^l \struct {\closedint 0 1, \le}$

$\struct {T, \preccurlyeq_l}$ has one minimal element:

- $\tuple {0, 0}$

which is also the smallest element: of $\struct {T, \preccurlyeq_l}$.

$\struct {T, \preccurlyeq_l}$ has no greatest element and no maximal elements.

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

## Sources

- 1960: Paul R. Halmos:
*Naive Set Theory*... (previous) ... (next): $\S 14$: Order - 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 14$: Orderings: Exercise $14.19 \ \text{(a)}$ - 1982: P.M. Cohn:
*Algebra Volume 1*(2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.5$: Ordered Sets: Exercise $4$ - 1996: Winfried Just and Martin Weese:
*Discovering Modern Set Theory. I: The Basics*... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations - 2000: James R. Munkres:
*Topology*(2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 3$: Relations