Quasiordnung

4 Typen von Ordnungsrelationen in Beziehung:   A ${ \rightarrow }$ B: A ist B; A ${ \color{Green}\downarrow }$ B: aus A wird B bei Quotientenbildung; A ${ \color{Red}\uparrow }$ B: aus A wird B bei Erweiterung; A ${ \color{Blue}\rightarrow }$ B: aus A wird B bei komponentenweiser Komposition

Eine Quasiordnung (auch Präordnung genannt) ist eine abgeschwächte Variante einer Halbordnung, 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 ihre reflexiv-transitive Hülle bildet.

Definitionen

Quasiordnung

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

$a\lesssim a$	(Reflexivität)
$a\lesssim b \lesssim c \implies a\lesssim c$	(Transitivität)

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

Eine Halbordnung (englisch partial order) ist eine Quasiordnung.

totale Quasiordnung

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

$a\lesssim b \vee b\lesssim a$

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

Eine Totalordnung (englisch total order) ist eine totale Quasiordnung (und auch eine Halbordnung).

Eine Halbordnung kann in eine Totalordnung eingebettet werden.

Beispiele und Gegenbeispiele

• 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 Halbordnung, 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 Halbordnung, wenn der Graph zyklenfrei (azyklisch) 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.
• Die Teilbarkeitsrelation | ist eine Quasiordnung auf der Menge der ganzen Zahlen. Sie ist keine Halbordnung, da zum Beispiel 3 | -3, aber auch -3 | 3 gilt. Betrachtet man die Teilbarkeit auf der Menge der natürlichen Zahlen, liegt eine Halbordnung vor.
• Ist das Vergleichen von (reellen oder rationalen) Zahlen mit einer Schwankungsbreite (Ungenauigkeit) behaftet, dann handelt es sich nicht um eine Quasiordnung, da die zugehörige Duplikatrelation keine Äquivalenzrelation ist.
• Dagegen ist das Vergleichen nach Abschneiden von Dezimal- oder Binärstellen, oder allgemeiner nach Rundung, eine totale Quasiordnung.
• Die Normen für die alphabetische Sortierung im Deutschen sind bei der Groß-/Kleinschreibung und der Behandlung von Umlauten Beispiele für totale Quasiordnungen, die keine Totalordnungen sind.

Induzierte Äquivalenzrelation und Striktordnung

Eine Quasiordnung $\lesssim$ auf einer Menge $M \$ erzeugt eine Äquivalenzrelation – die „kanonische“, d. h. die zu $\lesssim$ gehörige, ausgezeichnete Äquivalenzrelation –   ∼ auf $M \$ durch die Festlegung

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

Zwei Elemente sind also äquivalent, wenn sie gegenseitig vergleichbar sind. Diese Äquivalenzrelation sei der Kürze halber als Duplikatrelation der Quasiordnung bezeichnet.

Weiterhin erhält man die kanonische Striktordnung $<\$ auf $M \$ vermöge

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

Ist $\lesssim$ total, dann ist $<\$ eine strenge schwache Ordnung. Generell ist das Komplement einer totalen Quasiordnung eine strenge schwache Ordnung, und umgekehrt.

Zwischen der Ursprungsrelation und den 2 induzierten Relationen besteht der folgende Zusammenhang:

$a \lesssim b \Longleftrightarrow a\sim b \vee 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ätsring. Zwei Elemente sind genau dann äquivalent (im Sinne der Quasiordnung), wenn sie assoziiert sind, also durch Multiplikation mit einer Einheit auseinander hervorgehen.

Quotientenmenge

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

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

(wobei die Klasse von $x \$ mit $[x] \$ bezeichnet ist).

Ist die gegebene Quasiordnung total, dann ist das Ergebnis eine Totalordnung.

Beispiele

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

Verfeinerung

Eine Quasiordnung $(M,\lesssim_1)$ heißt feiner als die Quasiordnung $(M,\lesssim_2)$, wenn aus

$a \lesssim_1 b \;\; \Rightarrow \;\; a \lesssim_2 b \;\;\; \forall a,b \in M$ folgt.

Die Relation feiner ordnet alle die Quasiordnungen auf einer Menge ihrerseits wieder in einer Halbordnung.

Die gröbste Quasiordnung ist die triviale (Quasi)ordnung $\tau := (M \! \times \! M)$, bei der alle Elemente äquivalent sind.

Ferner ist (in diesem mengentheoretischen Sinn) eine Halbordnung feiner als ihre totale Einbettung (denn eine echte Totalisierung macht zusätzliche Beziehungen erforderlich). Jedoch gibt es zu Totalordnungen keine echt feineren totalen Quasiordnungen.

Beispiel

• Sei $\N$ die Grundmenge, $(\N,\le)$ die übliche Kleiner-Gleich-Relation und

$m \lesssim_2 n : \Longleftrightarrow \lfloor \tfrac{m}{2} \rfloor \le \lfloor \tfrac{n}{2} \rfloor \;$ (Gaußklammer).

     Dann ist $(\N,\le)$ feiner als $(\N,\lesssim_2)$, da stets

$m \le n \;\; \Rightarrow \;\; m \lesssim_2 n$.

Spiegelung

Eine Quasiordnung $(M,\lesssim)$ kann gespiegelt werden:

$a \lesssim_2 b :\Longleftrightarrow\ b \lesssim a \;\;$ (siehe auch Umkehrrelation).

Normalerweise nimmt man dann die Schreibweise:

$a \gtrsim b :\Longleftrightarrow\ b \lesssim a$.

Ist die gegebene Quasiordnung total, dann ist auch das Ergebnis total.

Ist sie eine Halbordnung, so auch das Ergebnis.

Die Spiegelung der Spiegelung ist das Original.

Komposition (Zusammensetzung, Hintereinanderschaltung)

komponentenweise Zusammensetzung

Auf zwei quasigeordneten Mengen $(M_1,\lesssim_1)$ und $(M_2,\lesssim_2)$ kann die Zusammensetzung komponentenweise-kleiner-oder-gleich $\lesssim_1 \! \oplus \! \lesssim_2$ auf der Menge $M_1 \! \times \! M_2$ der Paare wie folgt definiert werden:

${\left(a_1, a_2\right)} \;\; \lesssim_1 \! \oplus \! \lesssim_2 \;\; {\left(b_1, b_2\right)}\;\;\; :\Longleftrightarrow\;\;\; a_1 \lesssim_1 b_1 \wedge a_2 \lesssim_2 b_2$

Die Zusammensetzung $(M_1 \! \times \! M_2,\lesssim_1 \! \oplus \! \lesssim_2)$ ist wieder eine Quasiordnung.

Asymmetrie bleibt erhalten. Totalität geht jedoch verloren, d. h. bei zwei totalen Quasiordnungen bleibt nur eine Quasiordnung, bei zwei Totalordnungen nur eine Halbordnung übrig. (Beispiel: (1,0) ist nicht vergleichbar mit (0,1).)

Eine Art Kommunitativität ist vorhanden, denn $(M_2 \! \times \! M_1,\lesssim_2 \! \oplus \! \lesssim_1)$ ist isomorph zu $(M_1 \! \times \! M_2,\lesssim_1 \! \oplus \! \lesssim_2)$.

lexikographische Zusammensetzung

Auf zwei quasigeordneten Mengen $(M_1,\lesssim_1)$ und $(M_2,\lesssim_2)$ kann die lexikographische Zusammensetzung $\lesssim_1 \! \otimes \! \lesssim_2$ auf der Menge $M_1 \! \times \! M_2$ der Paare wie folgt definiert werden:

${\left(a_1, a_2\right)} \;\; \lesssim_1 \! \otimes \! \lesssim_2 \;\; {\left(b_1, b_2\right)}\;\;\; :\Longleftrightarrow\;\;\; a_1 <_1 b_1 \vee (a_1 \sim_1 b_1 \wedge a_2 \lesssim_2 b_2)$

Die Zusammensetzung $(M_1 \! \times \! M_2,\lesssim_1 \! \otimes \! \lesssim_2)$ ist wieder eine Quasiordnung. (Für die Ordnung der gleich langen Wörter unten sei der Einfachheit halber wieder $\lesssim_1 \! \otimes \! \lesssim_2 \,\, =: \,\, \lesssim$ gesetzt.)

Nach dem lexikographischen Prinzip lassen sich folgende Quasiordnungen für variabel lange Symbolsequenzen ableiten:

Sei $(M,\lesssim)$ quasigeordnet und seien $l_a := \operatorname{length}(a)$ und $l_b := \operatorname{length}(b)$ die Längen zweier Wörter $a,b \in M^*$ (Kleenesche Hülle) und $m := \operatorname{min}(l_a,l_b)$, dann kann $M^*\$ sowohl durch:

$a \lesssim_l b \; :\Longleftrightarrow\ l_a<l_b \,\,\, \vee \,\,\, (l_a=l_b \, \wedge \, \operatorname{left}(a,m) \lesssim \operatorname{left}(b,m))$

als auch durch:

$a \lesssim \ b \; :\Longleftrightarrow\ \operatorname{left}(a,m) <\ \operatorname{left}(b,m) \,\,\, \vee \,\,\, (\operatorname{left}(a,m) \sim \operatorname{left}(b,m) \, \wedge \, l_a \le l_b)$

quasigeordnet werden. Letztere Zusammensetzung nennt man wieder lexikographisch.

Sind die gegebenen Quasiordnungen alle total (auf ihren jeweiligen Komponentmengen), und nur dann, entsteht wieder eine totale Quasiordnung.

Sind sie allesamt sogar Totalordnungen, entsteht wieder eine Totalordnung.

Assoziativität

Die genannten Zusammensetzungen verhalten sich assoziativ, d. h. $(\lesssim_1 \! \oplus \! \lesssim_2) \oplus \! \lesssim_3 \,\,\, = \,\,\, \lesssim_1 \! \oplus (\lesssim_2 \! \oplus \! \lesssim_3)$ und $(\lesssim_1 \! \otimes \! \lesssim_2) \otimes \! \lesssim_3 \,\,\, = \,\,\, \lesssim_1 \! \otimes (\lesssim_2 \! \otimes \! \lesssim_3)$.

Bemerkung

Bei den Tabellenkalkulationsprogrammen entspricht eine „Spalte“ einer Komponentmenge $M_i \$. Die in diesen Programmen häufig angebotene Sortierfunktion entspricht einer lexikographischen Zusammensetzung mit zu spezifizierender Rangfolge der Spalten, wobei es i. d. R. zu jeder Spalte eine „Standard“-Ordnung gibt, die meist eine totale Quasiordnung, seltener eine echte Totalordnung (und dann höchstens auf der entspr. Spalte) ist. Es kann die „aufsteigende“ oder „absteigende“ Sortierreihenfolge gewählt werden.

Urbild einer Ordnungsrelation

Sei $M_0 \$ eine nicht-leere Menge, $(M,\lesssim)$ eine quasigeordnete Menge und $f\colon\, M_0 \to M$ eine beliebige Abbildung. Dann kann vermöge

$a_0 \lesssim_f b_0 :\Longleftrightarrow f(a_0) \lesssim f(b_0)$

die Menge $(M_0,\lesssim_f)$ quasigeordnet werden.

Ist $(M,\lesssim)$ total quasigeordnet, so ist es auch $(M_0,\lesssim_f)$.

Ist $(M,\lesssim)$ eine Halbordnung, so ist $(M_0,\lesssim_f)$ eine Halbordnung genau dann, wenn $f \$ injektiv ist.

Bemerkung

Seit 1991 gibt es für die digitale Codierung der Alphabete die internationale Norm des Unicode, die sich immer stärker durchzusetzen scheint. Über die Anordnung der Zeichen ist damit noch nicht allzuviel ausgesagt, da hier neben Sonderproblematiken wie den Umlauten z. B. auch die Beachtung/Nichtbeachtung der Groß-/Kleinschreibung und Sonderzeichen die Abbildung zu einer nicht-injektiven machen kann.

Erweiterung

Ist $(M_1,\lesssim)$ eine Quasiordnung und $M_2 \$ eine beliebige nicht-leere Menge, so kann $\lesssim$ wie folgt auf die Menge $M_1 \! \times \! M_2$ erweitert werden:

${\left(a_1, a_2\right)} \lesssim_2 {\left(b_1, b_2\right)} \;\;\; :\Longleftrightarrow \;\;\; a_1 \lesssim b_1$.

Wie $\lesssim$ ist auch $(M_1 \! \times \! M_2,\lesssim_2)$ eine Quasiordnung.

Ist $\lesssim$ total, so ist das Ergebnis wieder eine totale Quasiordnung.

Antisymmetrie geht i. A. verloren, d. h. wenn die gegebene Quasiordnung $\lesssim$ eine Halbordnung (bzw. Totalordnung) ist, ist das Ergebnis nur dann wieder eine Halbordnung (bzw. Totalordnung), wenn $M_2 \$ aus genau einem Element besteht. Besteht $M_2 \$ aus mehreren Elementen, so ist das Ergebnis nur noch eine Quasiordnung (bzw. totale Quasiordnung).

$\lesssim_2$ ist die Quasiordnung   $(\lesssim \! \otimes \, \tau)$   (mit der trivialen Ordnung $\tau\$ auf $M_2 \,$). Man kann sich $\lesssim$ als eine Vergleichsfunktion vorstellen, die auf ihren Schlüsselfeldern in $M_1 \$ operiert. Die Ergebnisordnung kann also ohne Verlust an Genauigkeit wieder mit   $(M_1 \! \times \! M_2, \lesssim)$   bezeichnet werden.

Zusammensetzung auf der Grundmenge

Hat man auf einer Menge $M \$ mehrere Quasiordnungen $\lesssim_1, \lesssim_2, ...$, so kann man ähnlich wie oben die lexikographischen Zusammensetzungen $(M,\lesssim_1 \! \otimes \! \lesssim_2 \! \otimes ...)$ bilden gemäß

$a \lesssim_1 \! \otimes \! \lesssim_2 b \;\;\; :\Longleftrightarrow\;\;\; a <_1 b \vee (a \sim_1 b \wedge a \lesssim_2 b)$.

Sie bilden eine (nicht-kommutative) Halbgruppe mit dem (beidseitig) neutralen Element $\tau\$.

$(M,\lesssim_1 \! \otimes \! \lesssim_2 \! )$ ist eine Verfeinerung von $(M,\lesssim_1 \! )$. D. h. auch, dass eine einer (auf ganz $M \$ totalen) Totalordnung nachgeschaltete Quasiordnung nichts mehr ändert.

Beispiel

Sei $M := \mathbb N$ die Menge der natürlichen Zahlen, $\lesssim_1 \; := \; <_{\varphi}$ mit der (nicht-injektiven) Eulerschen φ-Funktion und $\lesssim_2 \; := \; <$ die übliche Kleinerrelation, dann ordnet (die Totalordnung)   $(\lesssim_1 \! \otimes \! \lesssim_2) \; = \; (<_{\varphi} \! \otimes \! <)$   die Zahlen

    $\; 2,3,4,5,6,7,\;\; 8,\; 9,10,11,12$ um

    zu   $2,3,4,6,5,8,10,12,\;\, 7,\;\, 9,11 \$ wegen

    $\; 1,2,2,2,4, 4,\;\; 4,\;\; 4,\;\, 6,\; 6,10$ für die φ-Werte.

Einschränkung

In naheliegender Weise wird von einer Quasiordnung $(M_1,\lesssim)$ die Einschränkung $(M_2,\lesssim)$ auf eine Teilmenge $M_2 \subseteq M_1$ gebildet.

Bemerkung

Die Definitionsbereiche sind i. d. R. konzeptionell unendliche Mengen. Insoweit können Aussagen über die Eigenschaften der Ordnungsrelationen (insbesondere über die Transitivität) nur aus mathematischen Überlegungen stammen. Die Belegungen in den Anwendungen der Informatik sind natürlich stets endlich.

Siehe auch

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