Totale Ordnung

Eine totale Ordnung (auf Englisch: total order oder linear order) ist eine Relation, die alle Eigenschaften einer Teilordnung erfüllt (reflexiv, antisymmetrisch, transitiv) und darüber hinaus total ist, d.h. jedes Paar von Elementen vergleichbar ist.

Formale Definition

Sei R eine Relation auf einer Menge A. R ist eine totale Ordnung, wenn:

• Reflexiv: ∀a ∈ A: (a,a) ∈ R.
• Antisymmetrisch: ∀a,b ∈ A: (a,b) ∈ R ∧ (b,a) ∈ R ⇒ a = b.
• Transitiv: ∀a,b,c ∈ A: (a,b) ∈ R ∧ (b,c) ∈ R ⇒ (a,c) ∈ R.
• Totalität (Vergleichbarkeit): ∀a,b ∈ A: (a,b) ∈ R ∨ (b,a) ∈ R.

Die Totalität stellt sicher, dass für beliebige zwei verschiedene Elemente eines dem anderen vorausgeht.

Beispiele für totale Ordnungen

• Die ≤-Relation auf ganzen Zahlen: reflexiv, antisymmetrisch, transitiv und total.
• Alphabetische Ordnung auf Wörtern: Beliebige zwei Wörter können verglichen werden.
• Chronologische Ordnung auf Daten: Beliebige zwei Daten, eine ist früher als die andere.

Gegenbeispiele (Nicht-totale Ordnungen)

• Teilbarkeitsrelation auf natürlichen Zahlen: reflexiv, antisymmetrisch, transitiv, aber nicht total (z.B. 2 und 3 unvergleichbar).
• Teilmengenrelation ⊆ auf Mengen: Teilordnung, aber nicht total (z.B. {1} und {2} unvergleichbar).
• Freund von-Relation unter Menschen: nicht antisymmetrisch.

Total vs. Teilordnung

Jede totale Ordnung ist auch eine Teilordnung, aber nicht jede Teilordnung ist total. Der Unterschied ist die Vergleichbarkeit: Teilordnungen können unvergleichbare Elemente haben, totale Ordnungen vergleichen jedes Paar.

Zusammenfassung

Eine totale Ordnung ist eine Relation, die eine geordnete Sequenz auf der Menge erzeugt: reflexiv, antisymmetrisch, transitiv und total. Sie ist eines der wichtigsten Konzepte in der Mathematik, da Zahlen, Buchstaben, Daten und viele andere Daten natürlich in totaler Ordnung stehen.

Übungsaufgabe