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 . Mengen sind geordnet durch . Aber diese Ordnungen verhalten sich unterschiedlich!
Partielle Ordnung
Eine Relation auf einer Menge heißt partielle Ordnung, wenn sie:
Reflexiv: für alle
Antisymmetrisch: Wenn und , dann
Transitiv: Wenn und , dann
Beispiele: auf , und auf Potenzmengen.
Totale Ordnung
Eine partielle Ordnung heißt total, wenn je zwei Elemente vergleichbar sind:
Für alle : oder
Beispiel: auf ist total – jede zwei Zahlen sind vergleichbar.
Gegenbeispiel: auf Mengen ist nicht total.
und sind nicht vergleichbar: Weder noch umgekehrt.
Zusammenfassung
Partielle Ordnung = reflexiv + antisymmetrisch + transitiv
Totale Ordnung: Je zwei Elemente sind vergleichbar
auf Zahlen ist total, auf Mengen ist partiell
Übungen
Welche Relation ist eine totale Ordnung?