Präordnung

Eine Quasiordnung (auch Präordnung genannt) ist eine abgeschwächte Variante einer partiellen Ordnung, bei der es möglich ist, dass verschiedene Elemente in beiden Richtungen vergleichbar sind. Die Antisymmetrie muss also nicht erfüllt sein.

Jede beliebige zweistellige Relation kann zu einer Quasiordnung erweitert werden, indem man die reflexiv-transitive Hülle betrachtet.

Definition

Eine zweistellige Relation $\lesssim$ auf einer Menge $M\$ heißt eine Quasiordnung, wenn sie reflexiv und transitiv ist. Für alle $a, b, c \in M$ muss also gelten

$a\lesssim a$

$a\lesssim b \lesssim c \implies a\lesssim c$

Man nennt dann $(M,\lesssim)$ eine quasigeordnete Menge oder ebenfalls kurz eine Quasiordnung.

Eine Quasiordnung heißt total (Präferenzordnung), wenn je zwei Elemente immer vergleichbar sind. Für alle $a, b \in M$ muss also gelten:

$a\lesssim b$ oder $b\lesssim a$

Das Komplement einer totalen Quasiordnung ist eine strenge schwache Ordnung, und umgekehrt.

Beispiele

• Die Teilbarkeitsrelation | ist eine Quasiordnung auf der Menge der ganzen Zahlen. Sie ist keine partielle Ordnung, da zum Beispiel 3 | -3, aber auch -3 | 3 gilt. Betrachtet man die Teilbarkeit auf der Menge der natürlichen Zahlen, liegt eine partielle Ordnung vor.
• Vergleicht man komplexe Zahlen anhand ihres Betrags, erhält man eine totale Quasiordnung. Deren Definition lautet also: $a \lesssim b:\Longleftrightarrow |a| \le |b|$. Dies ist keine partielle Ordnung, da zum Beispiel die Zahlen 1 und i gegenseitig vergleichbar sind, also $1 \lesssim\mathrm{i}$ und $\mathrm{i}\lesssim 1$ gilt.
• Auf der Knotenmenge eines gerichteten Graphen erhält man eine Quasiordnung durch die Festlegung
  $a \lesssim b:\Longleftrightarrow$ es gibt einen gerichteten Weg von a nach b (b ist also von a aus erreichbar).
  Diese Quasiordnung ist genau dann eine partielle Ordnung, wenn der Graph zyklenfrei ist, also keine oder nur triviale Zyklen enthält.
  Tatsächlich lässt sich jede endliche Quasiordnung auf diese Weise aus einem geeigneten Graphen gewinnen.

Induzierte Äquivalenzrelation

Eine Quasiordnung $\lesssim$ auf einer Menge M erzeugt eine Äquivalenzrelation $\sim$ auf M durch die Festlegung

$a\sim b : \Longleftrightarrow a\lesssim b$ und $b\lesssim a$.

Zwei Elemente sind also äquivalent, wenn sie gegenseitig vergleichbar sind.

Weiterhin erhält man eine strenge Halbordnung $<\$ auf M vermöge

$a < b : \Longleftrightarrow a\lesssim b$ und $a \ \not\sim \ b$.

Zusammenfassend gilt der folgende Zusammenhang zwischen den drei hier betrachteten Relationen:

$a \lesssim b \Longleftrightarrow a\sim b$ oder $a < b\$,

wobei die zwei Bedingungen auf der rechten Seite sich gegenseitig ausschließen.

Beispiele

• Vergleicht man komplexe Zahlen anhand ihres Betrags (siehe oben), dann sind zwei Zahlen genau dann äquivalent, wenn ihr Betrag gleich ist. Die Äquivalenzklassen sind also die Kreise um den Nullpunkt in der komplexen Ebene. Eine Zahl ist „kleiner“ als eine zweite, wenn sie auf dem Kreis mit kleinerem Radius liegt (Radius 0 ist zugelassen).

• Bei der durch einen gerichteten Graphen gegebenen Quasiordnung (siehe oben) sind zwei Knoten genau dann äquivalent, wenn sie gleich sind oder auf einem gemeinsamen Zyklus liegen. Weiterhin gilt a < b, wenn es zwar einen gerichteten Weg von a nach b, aber keinen gerichteten Weg von b nach a gibt. Die drei Äquivalenzklassen beim nebenstehenden Graphen sind also {A}, {B, C, D, E}, {F}. Außerdem gilt für die induzierte strenge Halbordnung: A < B, C, D, E < F.
• Die Teilbarkeitsrelation ist auch eine Quasiordnung auf jedem Integritätsbereich. Zwei Elemente sind genau dann äquivalent (im Sinne der Quasiordnung), wenn sie assoziiert sind, also durch Multiplikation mit einer Einheit auseinander hervorgehen.

Faktormenge

Auf der Faktormenge $M/\sim$ (also der Menge der Äquivalenzklassen) erhält man eine wohldefinierte Halbordnung durch die Festlegung

$[x] \le [y] : \Longleftrightarrow x \lesssim y$

(wobei hier die Klasse von x mit [x] bezeichnet wird).

Beispiele

• Beim Vergleich komplexer Zahlen anhand ihres Betrags (siehe oben) ist die Halbordnung auf der Faktormenge isomorph zur gewöhnlichen Ordnung ≤ auf den nichtnegativen reellen Zahlen.
• Bei der Teilbarkeitsrelation auf den ganzen Zahlen (siehe oben) ist die Halbordnung auf der Faktormenge isomorph zur Teilbarkeitsrelation auf der Menge der natürlichen Zahlen (einschließlich 0).

Siehe auch

• gerichtete Menge
• reflexiv-transitive Hülle
• Wohlquasiordnung