Idee
De lexicografische volgorde is een veralgemening van de volgorde waarin woorden in een woordenboek staan, volgens de volgorde van de letters waarin de spelling van twee woorden het eerst verschilt.
Definitie
Definitie
Zie {L i} iâI{L_i}}_{i in I} als een goed geordende familie van lineair geordende verzamelingen. De lexicografische orde op het product van verzamelingen L=â iâIL iL = \prod_{i \in I} L_i is de lineaire orde als volgt gedefinieerd: als x,yâLx, y \in L en xâ yx \neq y, dan x<yx \lt y iff x i<y ix_i \lt y_i waarbij ii het minste element is in de verzameling {jâI:x jâ y j}{j \in I: x_j \neq y_j\}.
Hoewel dit begrip het meest voorkomt voor lineaire ordes, kan het ook worden toegepast op meer algemene relaties. Men kan de constructie bijvoorbeeld toepassen op verzamelingen met een transitieve relatie <lt, waarbij men de trichotomie-aanname laat vallen.
Vaak wordt deze notie ook uitgebreid naar deelverzamelingen van â iâIL i\prod_{i \in I} L_i. Bijvoorbeeld, de vrije monoïde S *S^^ast op een lineair geordende verzameling SS kan worden ingebed in een telbare macht
waarbij 1+S1 + S het resultaat is van het vrijelijk toevoegen van een bodemelement ee aan SS, en voor elke eindige lijst (s 1,â¦,s k)(s_1, \ldots, s_k) geldt
Dan is de lexicografische volgorde op S *S^ast die van de inbedding in de lexicografisch geordende verzameling (1+S) â(1 + S)^mathbb{N}.
Opmerking
De beslissing om een bodemelement ee vrij te adjuncteren is natuurlijk puur een conventie, gebaseerd op de gewone woordenboekconventie dat het Scrabble-woord AAH na AA moet komen. Als alternatief kunnen we evengoed oordelen dat ee een vrij toegevoegd top-element is, zodat AA na AAH komt; dit zou de âanti-woordenboekâ conventie genoemd kunnen worden.
Corecursieve definitie
als LL lineair geordend is en de onderliggende verzameling C=L âC = L^\mathbb{N} beschouwt men als de eindcoalgebra voor de functor LÃâ:SetâSetL \times – \colon Set \naar Set, met coalgebra structuur â¨h,tâ©:CâLÃCh,tâ© – \colon CâLtot LâLîtimes C, dan kan de lexicografische volgorde op CC kerncursief worden gedefinieerd:
- c<câ²c \lt c’ als h(c)<h(câ²)h(c) \lt h(c’) of (h(c)=h(câ²)h(c) = h(c’) en t(c)<t(câ²)t(c) \lt t(c’)).
Voor het speciale geval L=âL = \mathbb{N} is de eindcoalgebra â â âmathbb{N}^\mathbb{N} met deze lexicografische orde orde-isomorf met het reële interval [0,â)[0, \infty). Dit isomorfisme wordt hier nader beschreven.