Definition:Lexicographic Order

From ProofWiki

Jump to: navigation, search

Definition

Let $\left({S, \preceq}\right)$ be a poset.

For $n \in \N: n > 0$, we define $T_n$ as the set of all ordered $n$-tuples:

$\left({x_1, x_2, \ldots, x_n}\right)$

of elements $x_j \in S$.

We define the ordering $\preceq$ on $T_n$ as follows:

$\left({x_1, x_2, \ldots, x_n}\right) \prec \left({y_1, y_2, \ldots, y_n}\right)$ iff:

$\exists k: 1 \le k \le n$ such that $\forall 1 \le j < k: x_j = y_j$ but $x_k \prec y_k$ in $S$.

Next, let $\displaystyle T = \bigcup_{n \ge 1} T_n$.

We define the ordering $\preceq$ on $T$ as follows:

$\left({x_1, x_2, \ldots, x_m}\right) \prec \left({y_1, y_2, \ldots, y_n}\right)$ iff:

$\exists k: 1 \le k \le \min \left({m, n}\right)$ such that $\forall 1 \le j < k: x_j = y_j$ but $x_k \prec y_k$ in $S$

or:

$m < n$ and $\forall 1 \le j < m: x_j = y_j$.

This ordering is called lexicographic (or lexicographical) order(ing).