Ordnungen aus beliebigen Relationen
Sei R eine beliebige Relation auf einer Menge A. Wir konstruieren mit Hilfe von R eine partielle Ordnung ≤. Da R im Allgemeinen weder reflexiv noch antisymmetrisch noch transitiv ist, erscheint dies zunächst vielleicht unmöglich. Wir können die drei Eigenschaften aber durch eine Vergrößerung von R und eine Äquivalenzklassenbildung erreichen. Zuerst kümmern wir uns um die Transitivität. Hierzu definieren wir allgemein:
Definition (Verknüpfung zweier Relationen)
Sei A eine Menge, und seien R, S Relationen auf A. Dann definieren wir die Verknüpfung R ∘ S von R und S durch
R ∘ S = { (a, c) ∈ A2 | es gibt ein b ∈ A mit a R b und b S c }.
Speziell sind die Potenzen R1 = R, R2 = R ∘ R, …, Rn + 1 = Rn ∘ R, …definiert. Wir setzen zudem R0 = IdA = { (a, a) | a ∈ A }. Damit können wir definieren:
Definition (transitive Hülle)
Sei A eine Menge, und sei R eine Relation auf A. Dann definieren wir die transitive Hülle R+ von R durch
R+ = ⋃n ≥ 1 Rn = { (a, b) ∈ A2 | es gibt ein n ≥ 1 mit a Rn b }.
Die Relation R+ ist die kleinste Erweiterung von R, die transitiv ist. Setzen wir R* = R0 ∪ R+, so ist R* reflexiv und transitiv. Graphentheoretisch ist R* die reflexive Erreichbarkeitsrelation des gerichteten Graphen (A, R). Für alle n ≥ 0 und alle a, b ∈ A gilt a Rn b genau dann, wenn b durch einen Kantenzug der Länge n von a aus erreicht werden kann. Eine reflexive und transitive Relation auf einer Menge A heißt auch eine Präordnung oder Quasiordnung auf A. Zu einer partiellen Ordnung fehlt im Allgemeinen noch die Antisymmetrie. Diese können wir durch Einführung einer Äquivalenzrelation erzeugen. Wir setzen für alle a, b ∈ A:
a ∼ b falls a R* b und b R* a.
Nun definieren wir ≤ = ≤R auf der Faktorisierung A/∼ durch
[ a ] ≤ [ b ] falls a R* b.
Die Definition ist unabhängig von der Wahl der Repräsentanten und ≤ ist eine partielle Ordnung auf A/∼ (Übung).
Beispiel
Sei A = { 1, 2, 3, 4 } und R = { (1, 2), (2, 3), (3, 1), (3, 4) }. Dann ist
R* = R0 ∪ R+ = R ∪ R0 ∪ { (1, 3), (1, 4), (2, 1), (2, 4), (3, 2) }.
Es gilt A/∼ = { { 1, 2, 3 }, { 4 } } und { 1, 2, 3 } < { 4 }.