Idea
A ordem lexicográfica é uma generalização da ordem em que as palavras são listadas num dicionário, de acordo com a ordem das letras em que a ortografia de duas palavras primeiro difere.
Definição
Definição
Deixe {L i} iâI{L_i}_{i } ser uma família bem ordenada de conjuntos ordenados linearmente. A ordem lexicográfica no produto dos conjuntos L=â iâIL iL = {i {i } L_i é a ordem linear definida como se segue: se x,yâLx, y {\i}in L e xâ yx {\i}neq y, então x<yx {\i}lt y iff x i<y ix_i {jâI:x jâ y j}{j {j }in I: x_j {j {j }neq y_j}.
Embora esta noção seja mais frequentemente vista para ordens lineares, também pode ser aplicada para relações mais gerais. Por exemplo, pode-se aplicar a construção a conjuntos equipados com uma relação transitória <\lt, abandonando a hipótese de tricotomia.
ften this notion is extended to subsets of â iâIL i\d_{i } in I} L_i as well. Por exemplo, o monóide livre S *S^ast num conjunto ordenado linearmente SS pode ser incorporado num poder de contagem
onde 1+S1 + S é o resultado de um elemento inferior livremente adjacente a SS, e para cada lista finita (s 1,â¦,s k)(s_1, \ldots, s_k) temos
Então a ordem lexicográfica em S *S^\ é a herdada da sua incorporação no conjunto lexicograficamente ordenado (1+S) â(1 + S)^\mathbb{N}.
Remark
A decisão de juntar livremente um elemento inferior ee é, evidentemente, puramente uma convenção, baseada na convenção ordinária do dicionário de que a palavra Scrabble AAH deve vir depois de AA. Alternativamente, poderíamos igualmente considerar que ee é um elemento superior livremente adjunto, de modo que AA vem depois de AAH; isto poderia ser chamado a convenção âanti-dictionaryâ.
Definição corecursiva
se LL estiver ordenado linearmente e o conjunto subjacente C=L âC = L^\mathbb{N} é considerado como a álgebra de carvão terminal para o functor LÃââ:SetâSetL {\i}times – {\i1}colon Set {\i}to Set, com estrutura de álgebra de carvão â¨h,tâ©:CâLÃÃC\\\a h, t Ângulo h, t Ângulo CâLÃC\a CâLÃÃ?s C, depois a ordem lexicográfica em CC pode ser definida corecursivamente:
- #li> c<câ²c \lt c’ se h(c)<h(câ²)h(c) \lt h(c’) ou (h(c)=h(câ²)h(c) = h(c’) e t(c)<t(câ²)t(c) \lt t(c’))
Para o caso especial L=âL = \mathbb{N}, a coalgebra terminal â\mathbb{N}^\mathbb{N} com esta ordem lexicográfica é ordem-isomórfica ao intervalo real [0,â)[0, \i, \i, \i, \i, \i, \i). Este isomorfismo é descrito com mais precisão aqui.