Definition:Antilexicographic Order

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Antilexicographic_Order&oldid=519825"