Definition:Lexicographic Order/General Definition
Jump to navigation
Jump to search
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$.
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 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.
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)}$