lexicographic order

The *lexicographic order* is a generalization of the order in which words are listed in a dictionary, according to the order of letters where the spelling of two words first differs.

Let $\{L_i\}_{i \in I}$ be a well-ordered family of linearly ordered sets. The **lexicographic order** on the product of sets $L = \prod_{i \in I} L_i$ is the linear order defined as follows: if $x, y \in L$ and $x \neq y$, then $x \lt y$ iff $x_i \lt y_i$ where $i$ is the least element in the set $\{j \in I: x_j \neq y_j\}$.

While this notion is most often seen for linear orders, it can be applied also toward more general relations. For example, one might apply the construction to sets equipped with a transitive relation $\lt$, dropping the trichotomy assumption.

Often this notion is extended to subsets of $\prod_{i \in I} L_i$ as well. For instance, the free monoid $S^\ast$ on a linearly ordered set $S$ can be embedded in a countable power

$i \colon S^\ast \hookrightarrow (1 + S)^\mathbb{N} = \prod_{n \in \mathbb{N}} (1 + S)$

where $1 + S$ is the result of freely adjoining a bottom element $e$ to $S$, and for each finite list $(s_1, \ldots, s_k)$ we have

$i(s_1, \ldots, s_k) = (s_1, s_2, \ldots, s_k, e, e, e, \ldots).$

Then the lexicographic order on $S^\ast$ is the one inherited from its embedding into the lexicographically ordered set $(1 + S)^\mathbb{N}$.

The decision to freely adjoin a *bottom* element $e$ is of course purely a convention, based on the ordinary dictionary convention that the Scrabble word AAH should come after AA. Alternatively, we could equally well deem that $e$ is a freely adjoined top element, so that AA comes after AAH; this might be called the “anti-dictionary” convention.

if $L$ is linearly ordered and the underlying set $C = L^\mathbb{N}$ is regarded as the terminal coalgebra for the functor $L \times - \colon Set \to Set$, with coalgebra structure $\langle h, t \rangle \colon C \to L \times C$, then the lexicographic order on $C$ may be defined corecursively:

- $c \lt c'$ if $h(c) \lt h(c')$ or ($h(c) = h(c')$ and $t(c) \lt t(c')$).

For the special case $L = \mathbb{N}$, the terminal coalgebra $\mathbb{N}^\mathbb{N}$ with this lexicographic order is order-isomorphic to the real interval $[0, \infty)$. This isomorphism is described more precisely here.

Given a well-ordered family of well-ordered sets $\{L_i\}_{i: \alpha}$, the product $\prod_{i: \alpha} L_i$ with the lexicographic order is also well-ordered.

Represent elements of the set $\prod_{i: \alpha} L_i$ as sections $w: \alpha \to \sum_{i: \alpha} L_i$ of the canonical projection $\pi: \sum_{i: \alpha} L_i \to \sum_{i: \alpha} 1 \cong \alpha$. If $S \subseteq \prod_{i: \alpha} L_i$ is an inhabited subset, then its least element $s$ is defined recursively as follows: given $j \in \alpha$ and elements $s(i)$ for $i \lt j$, the element $s(j) \in L_j$ is the least element of the (nonempty!) set

$\{x \in L_j: \exists_{w \in S} \left(\forall_{i \lt j} w(i) = s(i)\right) \wedge w(j) = x\}.$

With the section $s: \alpha \to \sum_{i: \alpha} L_i$ thus defined, if $w \in S$ and $w \lt s$ in lexicographic order, with $j \in \alpha$ the least element such that $w(j) \lt s(j)$, then $w(i) = s(i)$ for all $i \lt j$, and we reach a contradiction in view of how $s(j)$ was defined. Hence $s$ is the minimal element of $S$.

Last revised on August 8, 2018 at 18:22:42. See the history of this page for a list of all contributions to it.