Elemente der Ordnungstheorie

Die Theorie der partiellen und linearen Ordnungen ist so reichhaltig, dass sie als eigene Teildisziplin der Mathematik angesehen werden kann. Beziehungen ergeben sich insbesondere zur diskreten Mathematik, zur Algebra und zur Mengenlehre. Wir stellen einige Motive im Stil eines kurzen Rundgangs vor und betrachten Wohlordnungen, Bäume und Verbände. Wir beginnen mit den Wohlordnungen. Sie verallgemeinern die Ordnung der natürlichen Zahlen:

Definition (Wohlordnung)

Eine lineare Ordnung < auf A heißt eine Wohlordnung, falls gilt:

(W) ∀B ⊆ A (B ≠ ∅ → ∃a a = min(B)).

In einer Wohlordnung besitzt jede nichtleere Teilmenge ein kleinstes Element. Diese Eigenschaft ist entscheidend für induktive Beweise und rekursive Definitionen.

Beispiele

(1)	Jede endliche lineare Ordnung ist eine Wohlordnung. Bis auf die Namen der Elemente gibt es nur die Wohlordnungen { 0, …, n − 1 } mit n  ∈  ℕ. Die erste unendliche Wohlordnung ist ℕ.

(2)

Ist (A, <) eine Wohlordnung und a* beliebig mit a*  ∉  A, so können wir eine Relation <* auf A* = A ∪ { a* } definieren durch

a <* b falls a < b oder b = a*.(Enderweiterung um a*)

Wir fügen also ein neues Element a* an die alte Ordnung an (ganz so, wie wir oft einen symbolischen Wert ∞ an ℕ angefügt haben). Die Relation <* ist eine Wohlordnung auf A*. Wir können an sie ein neues Element a** anfügen, dann a*** usw. Die technisch nichttriviale Durchführung dieser einfachen Idee führt zu den transfiniten Zahlen, die ein Herzstück der heutigen Mengenlehre bilden.

(3)	Sind (A, <) und (B, <) Wohlordnungen, so sind die lexikographischen Ordnungen <_lex (spaltenweise) und <^lex (zeilenweise) Wohlordnungen auf A × B (Übung).

(4)

Ist (A, <) eine Wohlordnung, so ist die Short-Lex-Ordnung eine Wohlordnung auf Seq_A (vgl. obiges Argument der Existenz eines Minimums). Die Ordnung lässt sich als Summe der lexikographischen Ordnungen auf A, A², …, ansehen). Dagegen ist <_lex bereits im Fall A = { 0, 1 } keine Wohlordnung. Denn die Menge

B = { 1, 01, 001, 0001, … }

hat kein Minimum bzgl. <_lex. Analoges gilt für <_KB.

Der Begriff der Wohlordnung führt zu einer sehr allgemeinen Definition eines Baumes:

Definition (Baum)

Eine partielle Ordnung (A, <) heißt ein (ordnungstheoretischer) Baum, falls gilt:

(T) Für alle a  ∈  A ist { b  ∈  A | b < a } wohlgeordnet unter <.

Ist A endlich, so ist die Bedingung äquivalent dazu, dass für jedes Element a der Ordnung die Menge der kleineren Elemente linear geordnet ist. Ein Baum darf sich nach oben (im Sinne von größer werdend), nicht aber nach unten verzweigen. Ein Baum kann unendlich hoch sein und sogar eine transfinite Höhe erreichen. In diesem Sinne sind die Bäume noch einmal eine Verallgemeinerung der transfiniten Zahlen: Im Vergleich zu diesen Zahlen verzichten wir auf die Eindeutigkeit des Nachfolgers und erlauben an jeder Stelle beliebige (auch unendliche) Verzweigungen.

Zeichnen wir in einem graphentheoretischen Baum eine Wurzel aus und tragen wir den Baum von der Wurzel ausgehend stufenweise von unten nach oben auf, so entsteht ein Diagramm, das wir als das Hasse-Diagramm eines ordnungstheoretischen Baumes ansehen können. Umgekehrt können wir jeden endlichen ordnungstheoretischen Baum als Hasse-Diagramm zeichnen und dieses Diagramm als graphentheoretischen Baum (mit einer natürlichen Wurzel) ansehen.

Schließlich betrachten wir noch einen algebraischen Begriff:

Definition (Verband)

Eine partielle Ordnung (A, <) heißt ein Verband, falls für alle a, b  ∈  A gilt:

(V) sup({ a, b }) und inf({ a, b }) existieren.

Für alle a, b  ∈  A setzen wir

a ∨ b = sup({ a, b }), a ∧ b = inf({ a, b }).

Wir sagen auch kurz, dass je zwei Elemente ein Supremum und Infimum besitzen. Verbände erhalten dadurch eine gitter- oder netzartige Struktur. Nicht zufällig wird ein Verband im Englischen mit lattice bezeichnet.

Beispiele

(1)	Ein wichtiges Beispiel für einen Verband ist die Teilbarkeitsrelation auf den natürlichen Zahlen. Für alle a, b ≥ 1 ist a ∧ b der größte gemeinsame Teiler und a ∨ b das kleinste gemeinsame Vielfache der beiden Zahlen. Für ∧ und ∨ gelten die Distributivgesetze.

(2)	Sei A eine beliebige Menge. Dann bildet die Inklusion auf ℘(A) einen Verband. Für alle Teilmengen B und C von A gilt B ∧ C = B ∩ C, B ∨ C = B ∪ C.