Quasiordnung

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.

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, wenn je zwei Elemente immer vergleichbar sind. Für alle $a,b\in M$ muss also gelten:

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

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|\leq |b|$. Dies ist keine partielle Ordnung, denn zum Beispiel sind 1 und i gegenseitig vergleichbar.
• 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 keine oder nur triviale Zyklen enthält.
  Tatsächlich lässt sich jede endliche Quasiordnung auf diese Weise aus einem geeigneten Graphen gewinnen.

Eigenschaften

Aus jeder quasigeordneten Menge kann man durch Faktorisierung eine halbgeordnete Menge gewinnen:

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

$a\sim b$ genau dann, wenn $a\lesssim b$ und $b\lesssim a$.

Auf der Menge $M/\sim$ der Äquivalenzklassen ist die induzierte Quasiordnung sogar antisymmetrisch, also eine Halbordnung.