Lektion 4.4

Ordnungsrelationen

12 min Lesezeit

Neben Äquivalenzen ist "Ordnung" ein weiterer fundamentaler Begriff. Ordnungsrelationen beschreiben, wann etwas "kleiner" oder "früher" ist.

Die natürlichen Zahlen sind geordnet durch ≤\leq. Mengen sind geordnet durch ⊆\subseteq. Aber diese Ordnungen verhalten sich unterschiedlich!

Definition

Partielle Ordnung

Eine Relation ≤\leq auf einer Menge AA heißt partielle Ordnung, wenn sie:

Reflexiv: a≤aa \leq a für alle aa

Antisymmetrisch: Wenn a≤ba \leq b und b≤ab \leq a, dann a=ba = b

Transitiv: Wenn a≤ba \leq b und b≤cb \leq c, dann a≤ca \leq c

Beispiele: ≤\leq auf N\mathbb{N}, und ⊆\subseteq auf Potenzmengen.

Ordnung: reflexiv, antisymmetrisch, transitiv\text{Ordnung: reflexiv, antisymmetrisch, transitiv}
Definition

Totale Ordnung

Eine partielle Ordnung ≤\leq heißt total, wenn je zwei Elemente vergleichbar sind:

Für alle a,ba, b: a≤ba \leq b oder b≤ab \leq a

Beispiel: ≤\leq auf R\mathbb{R} ist total – jede zwei Zahlen sind vergleichbar.

Gegenbeispiel: ⊆\subseteq auf Mengen ist nicht total.
{1,2}\{1, 2\} und {2,3}\{2, 3\} sind nicht vergleichbar: Weder {1,2}⊆{2,3}\{1,2\} \subseteq \{2,3\} noch umgekehrt.

total: ∀a,b:a≤b∨b≤a\text{total: } \forall a, b: a \leq b \lor b \leq a

Zusammenfassung

  • Partielle Ordnung = reflexiv + antisymmetrisch + transitiv

  • Totale Ordnung: Je zwei Elemente sind vergleichbar

  • ≤\leq auf Zahlen ist total, ⊆\subseteq auf Mengen ist partiell

Übungen

Aufgabe 1Multiple Choice

Welche Relation ist eine totale Ordnung?