nLab lexicographic order




In order theory, the lexicographic order is a generalization of the order in which words are listed in a dictionary, according to the order of the first letters for which the spelling of two words differs.



Let {L i} iI\{L_i\}_{i \in I} be a well-ordered family of strictly totally ordered sets. The lexicographic order on the Cartesian product of sets L= iIL iL = \prod_{i \in I} L_i is the strict total order defined as follows: if x,yLx, y \in L and xyx \neq y, then x<yx \lt y iff x i<y ix_i \lt y_i where ii is the least element in the set {jI:x jy j}\{j \in I \colon x_j \neq y_j\}.

While this notion is most often seen for strict total 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 iIL i\prod_{i \in I} L_i as well. For instance, the free monoid S *S^\ast on a linearly ordered set SS can be embedded in a countable power

i:S *(1+S) = n(1+S), i \;\colon\; S^\ast \xhookrightarrow{\phantom{--}} (1 + S)^\mathbb{N} \;=\; \prod_{n \in \mathbb{N}} (1 + S) \,,

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

i(s 1,,s k)=(s 1,s 2,,s k,e,e,e,).i(s_1, \ldots, s_k) = (s_1, s_2, \ldots, s_k, e, e, e, \ldots).

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


The decision to freely adjoin a bottom element ee 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 ee is a freely adjoined top element, so that AA comes after AAH; this might be called the “anti-dictionary” convention.

Corecursive definition

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

  • c<cc \lt c' if h(c)<h(c)h(c) \lt h(c') or (h(c)=h(c)h(c) = h(c') and t(c)<t(c)t(c) \lt t(c')).

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


A category theoretic analysis of lexicographic order:

Last revised on June 8, 2024 at 18:42:38. See the history of this page for a list of all contributions to it.