# Definition:Lexicographic Order/General Definition

Jump to navigation
Jump to search

## Contents

## Definition

Let $\left({S, \preceq}\right)$ be an ordered set.

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

- $\left({x_1, x_2, \ldots, x_n}\right)$

of elements $x_j \in S$.

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

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

- $\left({x_1, x_2, \ldots, x_m}\right) \preccurlyeq \left({y_1, y_2, \ldots, y_n}\right)$ if and only if:
- $\exists k: 1 \le k \le \min \left({m, n}\right): \left({\forall j: 1 \le j < k: x_j = y_j}\right) \land x_k \prec y_k$

- or:
- $m \le n$ and $\forall j: 1 \le j \le m: 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

or:

- all elements are equal up to the length of the shorter one.

## Also known as

**Lexicographic order** can also be known as the more unwieldy **lexicographical ordering**.

## 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{(e)}$