# Definition:Antilexicographic Order

## Definition

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

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

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

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

### General Definition

We can define the **antilexicographic order** of any finite number of ordered sets as follows:

Let $S_1, S_2, \ldots, S_n$ all be ordered sets.

Then we define $T_n$ as the **antilexicographic order** on $S_1, S_2, \ldots, S_n$ as:

- $\forall n \in \N_{>0}: T_n = \begin {cases}

S_1 & : n = 1 \\ T_{n - 1} \otimes^a S_n & : n > 1 \end {cases}$

### Family of Ordered Sets

Let $\struct {I, \preceq}$ be an ordered set such that its dual $\struct {I, \succeq}$ is well-ordered.

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 **antilexicographic order** on $D$ is defined as:

- $\ds \struct {D, \preccurlyeq_D} := {\bigotimes_{i \mathop \in I} }^a \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 \\

\exists i \in I: \paren {\forall j > i: \map u j = \map v j \text { and } \map u i \preccurlyeq_i \map v i} \end {cases}$

## Also known as

**Antilexicographic order** can also be referred to as **colexicographic order**.

Some sources classify the **antilexicographic order** as a variety of order product.

Hence the term **antilexicographic product** can occasionally be seen.

Some sources which focus more directly on real analysis refer to this merely as the **ordered product**, or **order product**.

This is because the other types of **order product** as documented on $\mathsf{Pr} \infty \mathsf{fWiki}$ are not of such importance in that context.

Such sources may even define the **order product** on a totally ordered set, ignoring its definition on the general ordered set.

The mathematical world is crying out for a less unwieldy term to use.

Some sources suggest **AntiLex** or **CoLex**, but this has yet to filter through to general usage.

## Examples

### Unit Square with Open Side

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

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

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

- $\tuple {0, 0}$

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

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

## Also see

- Results about
**the antilexicographic 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

- 1968: A.N. Kolmogorov and S.V. Fomin:
*Introductory Real Analysis*... (previous) ... (next): $\S 3.4$: Ordered sums and products of ordered sets - 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