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: aaa \leq a für alle aa

Antisymmetrisch: Wenn aba \leq b und bab \leq a, dann a=ba = b

Transitiv: Wenn aba \leq b und bcb \leq c, dann aca \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: aba \leq b oder bab \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:abba\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?

Lektion 4.4 · Relationen und Funktionen
• • •

Ordnungsrelationen

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: aaa \leq a für alle aa

Antisymmetrisch: Wenn aba \leq b und bab \leq a, dann a=ba = b

Transitiv: Wenn aba \leq b und bcb \leq c, dann aca \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: aba \leq b oder bab \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:abba\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