Definition:Lexicographic Order/Tuples of Equal Length

From ProofWiki
Jump to navigation Jump to search

Definition

Let $n \in \N_{>0}$.

Let $\left({S_1, \preceq_1}\right), \left({S_2, \preceq_2}\right), \ldots, \left({S_n, \preceq_n}\right)$ be ordered sets.

Let $\displaystyle S = \prod_{k \mathop = 1}^n S_k = S_1 \times S_2 \times \cdots \times S_n$ be the Cartesian product of $S_1$ to $S_n$.


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

$\left({x_1, x_2, \ldots, x_n}\right) \preccurlyeq \left({y_1, y_2, \ldots, y_n}\right)$ if and only if:
$\exists k: 1 \le k \le n: \left({\forall j: 1 \le j < k: x_j = y_j}\right) \land \left({x_k \prec_k y_k}\right)$
or:
$\forall j: 1 \le j \le n: 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.


Cartesian Space

The definition can be refined to apply to a Cartesian $n$-space:


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

Let $n \in \N_{>0}$.

Let $S^n$ be the cartesian $n$th power of $S$:

$S^n = \underbrace{S \times S \times \cdots \times S}_{n \text{ times} }$


The lexicographic order on $S^n$ is the relation $\preccurlyeq$ defined on $S^n$ as:

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


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.