Definition:Lexicographic Order/General Definition

From ProofWiki
Jump to navigation Jump to search


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

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

Let $\displaystyle T = \bigcup_{n \mathop \ge 1} T_n$.

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

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

That is, if and only if:

the elements of a pair of $n$-tuples are either all equal


they are all equal up to a certain point, and on the next one they are comparable and they are different


all elements are equal up to the length of the shorter one.

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.