nLab lexicographic order

Contents

Contents

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} iI\{L_i\}_{i \in I} be a well-ordered family of strictly totally ordered sets. The lexicographic order on the 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: 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 \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}.

Remark

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.

Last revised on December 24, 2023 at 21:19:47. See the history of this page for a list of all contributions to it.