Idee
Die lexikografische Ordnung ist eine Verallgemeinerung der Reihenfolge, in der Wörter in einem Wörterbuch aufgelistet werden, und zwar nach der Reihenfolge der Buchstaben, bei denen sich die Schreibweise zweier Wörter zuerst unterscheidet.
Definition
Sei {L i} iâI\{L_i\}_{i \in I} eine wohlgeordnete Familie von linear geordneten Mengen. Die lexikographische Ordnung auf dem Produkt der Mengen L=â iâIL iL = \prod_{i \in I} L_i ist die wie folgt definierte lineare Ordnung: wenn x,yâLx, y \in L und xâ yx \neq y, dann x<yx \lt y iff x i<y ix_i \lt y_i wobei ii das kleinste Element in der Menge {jâI:x jâ y j}\{j \in I: x_j \neq y_j\} ist.
Während dieser Begriff am häufigsten für lineare Ordnungen gesehen wird, kann er auch auf allgemeinere Beziehungen angewendet werden. Zum Beispiel könnte man die Konstruktion auf Mengen anwenden, die mit einer transitiven Relation <\lt ausgestattet sind, und dabei die Trichotomie-Annahme fallen lassen.
Oft wird dieser Begriff auch auf Teilmengen von â iâIL i\prod_{i \in I} L_i erweitert. Zum Beispiel kann das freie Monoid S *S^\ast auf einer linear geordneten Menge SS in eine abzählbare Potenz eingebettet werden
wobei 1+S1 + S das Ergebnis des freien Anfügens eines unteren Elements ee an SS ist, und für jede endliche Liste (s 1,â¦,s k)(s_1, \ldots, s_k) haben wir
Dann ist die lexikographische Ordnung auf S *S^\ast diejenige, die von seiner Einbettung in die lexikographisch geordnete Menge (1+S) â(1 + S)^\mathbb{N} geerbt wird.
Bemerkung
Die Entscheidung, ein unteres Element ee frei anzufügen, ist natürlich eine reine Konvention, die auf der gewöhnlichen Wörterbuchkonvention beruht, dass das Scrabble-Wort AAH nach AA kommen sollte. Alternativ könnte man ee auch als frei angefügtes oberes Element betrachten, so dass AA nach AAH kommt; dies könnte man als âanti-dictionaryâ-Konvention bezeichnen.
Korekursive Definition
wenn LL linear geordnet ist und die zugrundeliegende Menge C=L âC = L^\mathbb{N} als die terminale Coalgebra für den Funktor LÃâ:SetâSetL \times – \colon Set \to Set, mit Coalgebra-Struktur â¨h,tâ© betrachtet wird:CâLÃC\langle h, t \rangle \colon C \to L \times C, dann kann die lexikographische Ordnung auf CC korekursiv definiert werden:
- c<câ²c \lt c‘ wenn h(c)<h(câ²)h(c) \lt h(c‘) oder (h(c)=h(câ²)h(c) = h(c‘) und t(c)<t(câ²)t(c) \lt t(c‘)).
Für den Spezialfall L=âL = \mathbb{N} ist die terminale Kohlegebra â â\mathbb{N}^\mathbb{N} mit dieser lexikographischen Ordnung ordnungsisomorph zum reellen Intervall [0,â)[0, \infty). Dieser Isomorphismus wird hier genauer beschrieben.