Definition:Lexicographic Order/Family

Definition

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}$

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

• 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