Idea
El orden lexicográfico es una generalización del orden en el que se listan las palabras en un diccionario, según el orden de las letras en el que difiere primero la ortografía de dos palabras.
Definición
Definición
Sea {L i} iâI\{L_i\}_{i \in I} una familia bien ordenada de conjuntos linealmente ordenados. El orden lexicográfico sobre el producto de conjuntos L=â iâIL iL = \prod_{i \in I} L_i es el orden lineal definido como sigue: si x,yâLx, y \Nen L y xâ yx \neq y, entonces x<yx \lt y iff x i<y ix_i \lt y_i donde ii es el menor elemento del conjunto {jâI:x jâ y j}\j \in I: x_j \neq y_j\}.
Aunque esta noción se ve más a menudo para los órdenes lineales, puede aplicarse también hacia relaciones más generales. Por ejemplo, se podría aplicar la construcción a conjuntos dotados de una relación transitiva <\lt, dejando de lado el supuesto de tricotomía.
A menudo esta noción se extiende también a subconjuntos de â iâIL i\d_{i \in I} L_i. Por ejemplo, el monoide libre S *S^\\ast sobre un conjunto linealmente ordenado SS puede ser embebido en una potencia contable
donde 1+S1 + S es el resultado de adjuntar libremente un elemento inferior ee a SS, y para cada lista finita (s 1,â¦,s k)(s_1, \ldots, s_k) tenemos
Entonces el orden lexicográfico en S *S^\ast es el heredado de su incrustación en el conjunto lexicográficamente ordenado (1+S) â(1 + S)^\mathbb{N}.
Observación
La decisión de adjuntar libremente un elemento inferior ee es, por supuesto, puramente una convención, basada en la convención ordinaria del diccionario de que la palabra de Scrabble AAH debe ir después de AA. Alternativamente, también podríamos considerar que ee es un elemento superior libremente adjunto, de modo que AA viene después de AAH; esto podría llamarse la convención «anti-diccionario».
Definición corecursiva
Si LL está ordenada linealmente y el conjunto subyacente C=L âC = L^\mathbb{N} se considera como la coalgebra terminal para el functor LÃâ:SetâSetL \times – \colon Set \to Set, con estructura de coalgebra â¨h,tâ©:CâLÃC\langle h, t \colon C \a L \times C, entonces el orden lexicográfico en CC puede ser definido corecursivamente:
- c<câ²c \lt c’ si h(c)<h(câ²)h(c) \lt h(c’) o (h(c)=h(câ²)h(c) = h(c’) y t(c)<t(câ²)t(c) \lt t(c’)).
Para el caso especial L=âL = \mathbb{N}, la álgebra terminal â â\mathbb{N}^\mathbb{N} con este orden lexicográfico es isomorfa de orden al intervalo real [0,â)[0, \infty). Este isomorfismo se describe con mayor precisión aquí.