nLab
lexicographic order

Idea

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.

Definition

Definition

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\ne y$, then $x<y$ iff $x_i<y_i$ where $i$ is the least element in the set $\{j\in I:x_j\ne 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 $<$, 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^{*}$ on a linearly ordered set $S$ can be embedded in a countable power

$$i:S^{*}\hookrightarrow (1+S{)}^{\mathbb{N}}=\prod _{n\in \mathbb{N}}(1+S)$$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,\dots ,s_k)$ we have

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

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

Corecursive definition

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

• $c<c\prime$ if $h(c)<h(c\prime )$ or ($h(c)=h(c\prime )$ and $t(c)<t(c\prime )$).