Lineare Ordnungen
Die Ordnungen auf den Zahlenmengen sind durch die paarweise Vergleichbarkeit zweier Elemente ausgezeichnet. Für alle x, y ∈ ℝ gilt x < y oder x = y oder y < x. Dagegen sind in der Anfangsstückordnung auf den endlichen 0-1-Folgen die Elemente 10 und 01 nicht miteinander vergleichbar: non(01 < 10), non(01 = 10), non(10 < 01). Wir definieren allgemein:
Definition (vergleichbare Elemente, lineare Ordnung)
Sei < eine Ordnung auf A. Sind a, b ∈ A mit
a < b oder a = b oder b < a,
so heißen die Elemente a und b vergleichbar bzgl. <. Andernfalls heißen a und b unvergleichbar. Sind alle a, b ∈ A vergleichbar, so heißt < eine lineare oder totale Ordnung auf A.
Die lineare Ordnung der positiven Brüche mit Zähler und Nenner kleiner gleich 4.
Vereinbaren wir Wachstum von links nach rechts, so können wir die Pfeile oder Linien zwischen den Elementen auch weglassen (vgl. die Zahlengerade).
Spiraldarstellung der linearen Ordnung der positiven Brüche mit Zähler und Nenner kleiner gleich 8
Eine Relation < auf A ist also genau dann eine lineare Ordnung, wenn sie zusätzlich zu (P1) und (P2) die folgende Eigenschaft besitzt:
(P3) ∀a, b ∈ A (a < b ∨ a = b ∨ b < a)(Vergleichbarkeit, Linearität für <)
Analog ist eine Relation ≤ auf A genau dann eine lineare Ordnung (des nichtstrikten Typs), wenn sie neben (Q1), (Q2) und (Q3) erfüllt:
(Q4) ∀a, b ∈ A (a ≤ b ∨ b ≤ a)(Vergleichbarkeit, Linearität für ≤)
Die Vergleichbarkeit lässt sich also als zusätzliches (drittes oder viertes) Ordnungsaxiom ansehen. Bei der Übersetzung zwischen einer strikten und nichtstrikten Ordnung gehen (P3) und (Q4) ineinander über.
Gitter-Darstellung der linearen Ordnung der positiven Brüche mit Zähler und Nenner kleiner gleich 8: Die Brüche sind gekürzt und nach ihrem Zähler und Nenner auf einem Koordinatengitter angeordnet. Wir können zwei Brüche dieses Gitters nach ihrer Größe vergleichen, indem wir Geraden durch den Nullpunkt durch sie legen.
Brüche mit flacheren Geraden sind größer, denn die Gerade durch den Punkt (a, b) hat die Steigung b/a.
Wir untersuchen unsere Beispiele auf Linearität.
Beispiele
Die Ordnungen auf den Zahlenmengen sind linear. Die Inklusion auf der Potenzmenge ℘(A) von A ist linear, wenn A leer ist oder genau ein Element besitzt (da ℘({ }) = { { } } und ℘({ a }) = { { } , { a } }). Andernfalls ist die Inklusion nicht linear. Denn sind a, b ∈ A verschieden, so sind die Teilmengen { a } und { b } von A unvergleichbar bzgl. der Inklusion. Die Teilbarkeitsrelation auf ℕ ist nicht linear, da zum Beispiel 2 und 3 unvergleichbar sind. Die Anfangsstückordnung auf den endlichen 0-1-Folgen S ist nicht linear. Die Ordnung eines Wurzelbaumes ist genau dann linear, wenn es einen in der Wurzel beginnenden Weg gibt, der alle Ecken besucht. Analog ist die Weg-Ordnung eines gerichteten kreisfreien Graphen G genau dann linear, wenn es einen Weg in G gibt, der alle Ecken besucht.
Neben den Ordnungen auf den Zahlen gibt es viele weitere Beispiele für lineare Ordnungen. Eine wichtige Klasse beschreibt die folgende allgemeine Konstruktion.
Definition (lexikographische Ordnung)
Seien (A, <), (B, <) lineare Ordnungen. Wir setzen für alle Elemente (a, b), (c, d) ∈ A × B:
(a, b) <lex (c, d) falls a < c ∨ (a = c ∧ b < d).
Die Relation <lex heißt die (spaltenweise) lexikographische Ordnung auf A × B.
Die lexikographische Ordnung ist eine lineare Ordnung auf A × B (Übung).
Damit ist für jede lineare Ordnung (A, <) eine lineare Ordnung auf den Produktmengen A2 = A × A, A3 = A2 × A usw. definiert. Speziell erzeugt die übliche lineare Ordnung von ℝ eine lineare Ordnung auf der Menge ℂ = ℝ2 der komplexen Zahlen. Bei dieser Ordnung werden zwei komplexe Zahlen nach ihrem Realteil und bei gleichem Realteil nach ihrem Imaginärteil verglichen. Diese Ordnung ist nicht mit der komplexen Arithmetik verträglich. Wir kommen bei der Diskussion angeordneter Körper hierauf zurück.
Die lexikographische Ordnung auf A × A mit A = { 1, …, 8 } und der üblichen Ordnung auf A. Die Produktmenge wird spaltenweise von unten nach oben durchlaufen.
Die lexikographische Ordnung auf A × B können wir visualisieren, indem wir A × B als abstraktes Koordinatensystem zeichnen, mit der linearen Ordnung A als waagrechter und der linearen Ordnung B als senkrechter Achse. Wachsen A und B wie üblich von links nach rechts bzw. von unten nach oben, so ist <lex die Ordnung, die entsteht, wenn wir alle Senkrechten von links nach rechts anordnen und die Punkte jeder Senkrechten von unten nach oben durchlaufen. Alternativ können wir natürlich auch die zweite Komponente bevorzugen und eine zeilenweise lexikographische Ordnung durch
(a, b) <lex (c, d) falls b < d ∨ (b = d ∧ a < c).
definieren. Das kartesische Produkt A × B wird nun anschaulich Zeile für Zeile durchlaufen.
Neben der spalten- oder zeilenweisen Aufzählung eines Produkts A × B gibt es viele weitere Möglichkeiten, alle Elemente von A × B linear anzuordnen. Für endliche Mengen können wir zum Beispiel Diagonalen, Rechtecke oder Spiralen bilden und diese nach Wunsch anordnen. Wir begnügen uns an dieser Stelle mit zwei wichtigen Beispielen. Das erste ist:
Eine Diagonalaufzählung des Produkts A × A mit A = { 1, …, 8 }
Die Diagonalaufzählung des Diagramms ist durch das Cantorsche Paarungspolynom π : ℕ2 → ℕ mit
π(a, b) = (a + b)(a + b + 1)/2 + a für alle (a, b) ∈ ℕ2
definiert. Die Paare (a, b) ∈ A2 werden nach ihrem π-Wert geordnet (von klein nach groß). Wir beobachten hierzu, dass der erste Summand der π-Funktion konstant auf den Diagonalen von A2 ist. Der zweite Summand legt die Position auf den Diagonalen fest. Definieren wir π durch „+ b“ anstelle von „+ a“, so werden die Diagonalen in der anderen Richtung durchlaufen.
Ein zweites Beispiel ist:
Eine Maximums-Aufzählung des Produkts A × A mit A = { 1, …, 8 }
Bei der Maximums-Aufzählung des Diagramms vergleichen wir zwei Paare (a, b) und (c, d) nach ihren Maxima max(a, b) und max(c, d). Bei gleichem Maximum ordnen wir die Paare lexikographisch (mit der spaltenweisen Version der lexikographischen Ordnung).