Teilordnung

Eine Relation heißt Teilordnung (auf Englisch: partial order), wenn drei Eigenschaften erfüllt sind: reflexiv, antisymmetrisch und transitiv. Diese Kombination stellt sicher, dass die Relation eine 'geordnete' Struktur erzeugt, obwohl nicht unbedingt eine totale Ordnung.

Formale Definition

Reflexiv: Jedes Element steht in Relation zu sich selbst.

Antisymmetrisch: Wenn ein Element mit einem anderen und umgekehrt in Relation steht, dann sind sie gleich.

Transitiv: Wenn a mit b und b mit c in Relation steht, dann steht a mit c in Relation.

Beispiele für Teilordnungen

• Die ≤-Relation auf ganzen Zahlen: reflexiv, antisymmetrisch, transitiv.
• Die Teilbarkeitsrelation auf natürlichen Zahlen: reflexiv, antisymmetrisch, transitiv.
• Die Teilmengenrelation ⊆ auf Mengen: reflexiv, antisymmetrisch, transitiv.

Gegenbeispiele (Nicht-Teilordnungen)

• Die <-Relation: Nicht reflexiv (keine Zahl ist kleiner als sie selbst).
• Die 'Freund von'-Relation unter Menschen: Nicht antisymmetrisch (wenn A Freund von B und B von A ist, sind sie immer noch unterschiedliche Personen).
• Die 'Geschwister von'-Relation unter Menschen: Nicht antisymmetrisch (Geschwister sind unterschiedliche Personen).

Teilweise Geordneter Satz (Poset)

Ein Satz mit einer Teilordnung heißt teilweise geordneter Satz (poset). In einem poset müssen nicht jedes Paar von Elementen vergleichbar sein, aber wo sie es sind, zeigt die Relation geordnetes Verhalten.

Zum Beispiel bei der Teilmengenrelation können die Mengen {1,2} und {2,3} nicht verglichen werden, weil keine Teilmenge der anderen ist. Daher ist die Struktur 'teilweise' geordnet, nicht vollständig.

Zusammenfassung

Eine Teilordnung ist somit eine Relation, die reflexiv, antisymmetrisch und transitiv ist. Diese Kombination ermöglicht es, eine teilweise Ordnung zwischen den Elementen des Satzes festzustellen, die in vielen mathematischen und informatischen Bereichen ein grundlegendes Konzept ist (z.B. Graphen, Hierarchien, Datastrukturen).

Übungsaufgabe