(0,1)-category

(0,1)-topos

# 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 $\left\{{L}_{i}{\right\}}_{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 iff ${x}_{i}<{y}_{i}$ where $i$ is the least element in the set $\left\{j\in I:{x}_{j}\ne {y}_{j}\right\}$.

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}^{*}↪\left(1+S{\right)}^{ℕ}=\prod _{n\in ℕ}\left(1+S\right)$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 $\left({s}_{1},\dots ,{s}_{k}\right)$ we have

$i\left({s}_{1},\dots ,{s}_{k}\right)=\left({s}_{1},{s}_{2},\dots ,{s}_{k},e,e,e,\dots \right).$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 $\left(1+S{\right)}^{ℕ}$.

### Corecursive definition

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

• $c if $h\left(c\right) or ($h\left(c\right)=h\left(c\prime \right)$ and $t\left(c\right)).
Revised on September 16, 2012 15:15:14 by Todd Trimble (67.81.93.25)