Endliche Folgen

 Gegeben eine lineare Ordnung auf A liefert die lexikographische Ordnung eine lineare Ordnung auf A², A³, …, Aⁿ, … Oft ist es von Interesse, endliche Folgen variabler Länge miteinander vergleichen zu können. Wir definieren hierzu:

 Die leere Folge ( ) ist immer ein Element von Seq_A. Identifizieren wir a  ∈  A mit der Folge (a)  ∈  Seq_A der Länge 1, so können wir A ⊆ Seq_A annehmen. Die Anfangsstückrelation ist eine partielle Ordnung auf Seq_A.

 Eine lineare Ordnung auf A können wir zu einer linearen Ordnung nach Seq_A liften, indem wir Folgen an der Stelle ihres kleinsten Unterschieds miteinander vergleichen und zudem angeben, wie wir Anfangsstücke behandeln. In einem Lexikon erscheint zum Beispiel s vor t, falls s ein echtes Anfangsstück von t ist. Diese Einordnung wird anschaulich, wenn wir eine endliche Folge als unendliche Folge auffassen, die in einem symbolischen Nullwert endet, der kleiner ist als alle Elemente von A. Setzen wir dagegen s durch einen symbolischen Wert ∞ fort, so ist s größer als t, falls s ⊲ t. Schließlich können wir auch die Länge als maßgebliches Vergleichkriterium heranziehen: Wir ordnen kürzere Folgen vor längeren ein und vergleichen gleichlange Folgen an der kleinsten Stelle eines Unterschieds. Die formalen Definitionen dieser drei Ordnungen lauten:

 Die partielle Ordnung (Seq_A, ⊲) können wir uns als einen unendlich hohen Baum mit der Wurzel ( ) vorstellen, der sich an jeder Stelle A-fach verzweigt. Auf der n-ten Stufe befinden sich alle Folgen in A der Länge n.

 Die Short-Lex-Ordnung können wir so beschreiben: Wir fügen die lexikographisch geordneten Stufen aneinander. Die beiden anderen Ordnungen sind komplizierter. Für A = { 0, 1 } sind bei <_lex und <_KB alle Nullfolgen 0, 00, 000, … kleiner als die Folge 1 der Länge 1 auf Stufe 1. Bei <_KB sind die Nullfolgen zudem umgekehrt geordnet, sodass 0 größer ist 00, 00 größer als 000 usw.

 Einen Eindruck von der Bauart der drei linearen Ordnungen können wir erhalten, indem wir uns auf die ersten Stufen von Seq_A beschränken. Ist A endlich, so können wir die Elemente des gestutzten Baumes entsprechend der gewählten linearen Ordnung durchzählen. In den folgenden Diagrammen betrachten wir wieder Folgen der Länge kleiner oder gleich 4 in der Menge A = { 0, 1 }.

 Die Linearisierung des unendlich hohen Folgenbaumes Seq_A ist für die endliche Menge A = { 0, 1 } deutlich komplexer. Die obigen Diagramme sind ein gewisses Abbild der Ordnungen, aber es gibt wesentliche Unterschiede. Am einfachsten ist die Short-Lex-Ordnung, bei der Elemente auf höheren Stufen immer später erscheinen als auf niedrigeren Stufen. Die Positionen bleiben fest, 110 ist das 14. Element der Ordnung <_shortlex auf ganz Seq_A. Bei den anderen Ordnungen ist dies nicht der Fall, 110 ist keineswegs das 26. Element von <_lex und auch nicht das 25. Element von <_KB auf Seq_A. Beim Hinzufügen neuer Stufen werden immer wieder Elemente eingewoben und nicht nur am Ende angehängt. Wir betrachten hierzu die Ordnung <_lex genauer, ähnliche Überlegungen gelten für <_KB.

 In der Ordnung < = <_lex gibt es unmittelbare Nachfolger: Für alle s ist die Verlängerung s0 der Folge s um 0 größer als s, und es gibt keine t mit s < t < s0. Damit beginnt die Ordnung mit den Folgen auf dem linken Ast von Seq_A:

(+)  ( )  <  0  <  00  <  000  <  …

Nun gibt es aber keine kleinste Folge, die größer ist als alle 0-Folgen in (+). Die 0-Folgen haben keinen unmittelbaren Nachfolger mehr. Um dies einzusehen betrachten wir die Folgen des Typs 0 … 01. Diese Folgen sind absteigend geordnet und größer als alle 0-Folgen:

(++)  ( )  <  0  <  00  <  000  <  …  <  …  <  0001  <  001  <  01  <  1

Während auf der linken Seite dieser Kette direkte Nachfolger gebildet werden, ist dies auf der rechten Seite nicht der Fall: 01 ist nicht der direkte Vorgänger der 1, 001 nicht der direkte Vorgänger von 01 usw. Es gilt

…  <  001  <  0010  <  00100  <  …  <  01  <  010  <  0100  <  …  <  1  <  10  <  100  <  …

mit direkten Nachfolgerbildungen. Damit ergibt sich folgendes Bild: In (++) liegt an jeder Stelle 1, 01, 001, … eine Kopie der Ordnung <_lex, die mit dem linken Ast oberhalb von 1, von 01, von 001 usw. beginnt. Die Ordnung beginnt strukturell mit einer Kopie von ℕ, danach folgen unendlich viele Kopien der gesamten Ordnung, die wie die negativen ganzen Zahlen angeordnet sind. Alternativ können wir auch so argumentieren: Die Fortsetzungen einer Folge s liefern zwei Ordnungen, die mit s0 bzw. s1 beginnen und Kopien von <_lex sind. Führen wir diese Aufspaltung beginnenden mit ( ) wiederholt durch, so erhalten wir

( ),  0,  ---,  1,  ---

( ),  0,  00,  ---,  01,  ---,  1,  ---

( ),  0,  00,  000,  ---,  001,  ---,  01,  ---,  1,  ---  usw.

wobei jeder Teil --- der Ordnung wie die ganze Ordnung <_lex aussieht.

 In unserer Diskussion haben wir uns auf A = { 0, 1 } beschränkt. Wir können aber mit einer beliebigen linearen Ordnungen auf einer endlichen oder unendlichen Menge A starten, den Baum aller Folgen mit dem „Alphabet“ A betrachten und diesen linear ordnen. Für A = ℤ hat eine Folge s in <_lex keinen direkten Nachfolger mehr, da … < s(a − 1) < sa < s(a + 1) < … für alle a  ∈  ℤ. Auch ℝ ist als Alphabet möglich. Wir erhalten so lineare Ordnungen aller endlichen reellen Folgen.