lexicographic order

Maintenence will be carried out on the nLab server at Carnegie Mellon University between 03:00 GMT and 09:00 GMT on the 23rd of March. Between these times both the nLab and the nForum are expected to be completely down. Apologies for the inconvenience.



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} iI\{L_i\}_{i \in I} be a well-ordered family of linearly ordered sets. The lexicographic order on the product of sets L= iIL iL = \prod_{i \in I} L_i is the linear 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: 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 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 \hookrightarrow (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.

Revised on July 10, 2015 23:08:35 by Todd Trimble (