Ordnungsrelation

Bei einer Ordnungsrelation handelt es sich um eine zweistellige Relation auf einer Menge, die im Wesentlichen eine Verallgemeinerung der Kleinergleich-Relation \(\leq\) darstellt. Sie ermöglicht es, die Elemente einer Menge miteinander zu vergleichen und anzuordnen.

Ordnungsrelationen sind stets transitiv. Abhängig von der konkreten Art der Ordnung sind Ordnungsrelationen darüber hinaus zudem antisymmetrisch, asymmetrisch, irreflexiv und/oder reflexiv.

Definition

Totalordnung

Eine auf einer Menge \(A\) definierte zweistellige Relation \(R \subseteq A \times A\) wird (schwache) Totalordnung (oder auch totale Ordnung, lineare Ordnung oder einfach (schwache) Ordnung) genannt, wenn sie die folgenden Eigenschaften besitzt:

• Die Relation \(R\) ist antisymmetrisch, d. h. es gilt:
  \[ \forall a,b \in A \text{ mit } a \neq b: (a,b) \in R \Rightarrow (b,a) \notin R. \]
• Die Relation \(R\) ist reflexiv, d. h. es gilt:
  \[ \forall a \in A: (a,a) \in R. \]
• Die Relation \(R\) ist transitiv, d. h. es gilt:
  \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R. \]
• Die Relation \(R\) ist total, d. h., es gilt:
  \[ \forall a,b \in A: (a,b) \in R \vee (b,a) \in R. \]

Strenge Totalordnung

Eine auf einer Menge \(A\) definierte zweistellige Relation \(R \subseteq A \times A\) wird strenge (oder auch starke) Totalordnung genannt, wenn sie die folgenden Eigenschaften besitzt:

• Die Relation \(R\) ist transitiv, d. h. es gilt:
  \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R. \]
• Die Relation \(R\) ist trichotom, d. h. es gilt:
  \[ \forall a,b \in A: \bigl( (a,b) \in R \cap (b,a) \notin R \bigr) \vee \bigl( (b,a) \in R \cap (a,b) \notin R \bigr) \vee a=b. \]

Da eine strenge Totalordnung nicht reflexiv ist, handelt es sich nicht um eine (schwache) Totalordnung.

Halbordnung

Eine auf einer Menge \(A\) definierte zweistellige Relation \(R \subseteq A \times A\) wird Halbordnung (oder auch Partialordnung, Teilordnung oder partielle Ordnung) genannt, wenn sie die folgenden Eigenschaften besitzt:

• Die Relation \(R\) ist antisymmetrisch, d. h. es gilt:
  \[ \forall a,b \in A \text{ mit } a \neq b: (a,b) \in R \Rightarrow (b,a) \notin R. \]
• Die Relation \(R\) ist reflexiv, d. h. es gilt:
  \[ \forall a \in A: (a,a) \in R. \]
• Die Relation \(R\) ist transitiv, d. h. es gilt:
  \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R. \]

Gegenüber der Totalordnung ist die Halbordnung dahingehend abgeschwächt, dass die Elemente \(a \in A\) zwar stets mit sich selbst in Relation stehen müssen, jedoch nicht notwendigerweise mit allen anderen Elementen. Die Relation ist also nur reflexiv statt total.

Halbordnungen können mithilfe von Hasse-Diagrammen visualisiert werden.

Strenge Halbordnung

Eine auf einer Menge \(A\) definierte zweistellige Relation \(R \subseteq A \times A\) wird strenge Halbordnung genannt, wenn sie die folgenden Eigenschaften besitzt:

• Die Relation \(R\) ist antisymmetrisch, d. h. es gilt:
  \[ \forall a,b \in A \text{ mit } a \neq b: (a,b) \in R \Rightarrow (b,a) \notin R. \]
• Die Relation \(R\) ist irreflexiv, d. h. es gilt:
  \[ \forall a \in A: (a,a) \notin R. \]
• Die Relation \(R\) ist transitiv, d. h. es gilt:
  \[ \forall a,b,c \in A: (a,b) \in R \wedge (b,c) \in R \Rightarrow (a,c) \in R. \]

Teilweise wird die Antisymmetrie für eine strenge Halbordnung nicht explizit gefordert, da sie sich aus der Transitivität und Irreflexivität implizit ergibt. Alternativ zu den obenstehenden Bedingungen können die Antisymmetrie und die Irreflexivität auch durch die gleichwertige Asymmetrie ersetzt werden.

Da eine strenge Halbordnung nicht reflexiv ist, handelt es sich nicht um eine Halbordnung.

Striktordnung

Eine auf einer Menge \(A\) definierte zweistellige Relation \(R \subseteq A \times A\) wird strenge Ordnung oder Striktordnung genannt, wenn sie transitiv und asymmetrisch ist. Wie üblich fasst Asymmetrie die Eigenschaften antisymmetrisch und irreflexiv zusammen.

Es handelt sich bei strengen Total- und strengen Halbordnungen um Striktordnungen.

Quasiordnung

Eine auf einer Menge \(A\) definierte zweistellige Relation \(R \subseteq A \times A\) wird Quasiordnung genannt, wenn sie transitiv und reflexiv ist.

Es handelt sich bei Total- und Halbordnungen, aber auch bei Äquivalenzrelationen, um Quasiordnungen.

Beispiele

• Bei der Kleinergleich- bzw. Größergleich-Relation \(\leq\) bzw. \(\geq\) handelt es sich um Totalordnungen.
• Bei der Kleiner- bzw. Größer-Relation \(\lt\) bzw. \(\gt\) handelt es sich um strenge Totalordnungen.
• Bei der Teilmengenbeziehung \(\subseteq\) handelt es sich um eine Halbordnung.
• Bei der echten Teilmengenbeziehung \(\subset\) handelt es sich um eine strenge Halbordnung.
• Bei der Teilbarkeitsrelation \(\mid\) auf natürlichen Zahlen handelt es sich um eine Halbordnung.
• Bei der Teilbarkeitsrelation \(\mid\) auf ganzen Zahlen handelt es sich um eine Quasiordnung.
• Bei der Kongruenzrelation \(\equiv\) handelt es sich um eine Quasiordnung.