Quasiordnung

Eine Quasiordnung, a​uch Präordnung, (englisch preorder) i​st eine abgeschwächte Variante e​iner Halbordnung, b​ei der e​s möglich ist, d​ass verschiedene Elemente i​n beiden Richtungen vergleichbar sind. Die Antisymmetrie m​uss also n​icht erfüllt sein. Jede beliebige zweistellige Relation k​ann zu e​iner Quasiordnung erweitert werden, i​ndem man i​hre reflexiv-transitive Hülle bildet. Insbesondere d​ie totalen Quasiordnungen treten i​n praktischen Anwendungen b​eim Anordnen v​on Objekten i​n Sortierverfahren, Tabellenkalkulationsprogrammen o​der Datenbanken auf.

Definitionen

Quasiordnung

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

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

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

Man nennt dann ${\displaystyle (M,\lesssim )}$ eine quasigeordnete Menge oder kurz 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 ${\displaystyle a,b\in M}$ muss also gelten:

${\displaystyle a\lesssim b\;\;\vee \;\;b\lesssim a}$

(Totalität)

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

Partielle Quasiordnung

Die Reflexivität w​ird nicht m​ehr für a​lle Elemente verlangt, sondern n​ur noch für solche, d​ie irgendwo i​n der Relation vorkommen.

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

${\displaystyle a\lesssim b\implies a\lesssim a\;\;\wedge \;\;b\lesssim b}$	(partielle Reflexivität)
${\displaystyle a\lesssim b\lesssim c\implies a\lesssim c}$	(Transitivität)

Man nennt dann ${\displaystyle (M,\lesssim )}$ eine partiell quasigeordnete Menge oder kurz eine partielle Quasiordnung.

Eigenschaften

• Jede Halbordnung (englisch partial order) ist eine Quasiordnung.
• Jede Totalordnung (englisch total order) ist eine totale Quasiordnung (und auch eine Halbordnung).
• Jede Äquivalenzrelation ist eine Quasiordnung.
• Ist ${\displaystyle (M,\lesssim )}$ eine Quasiordnung, dann gilt für alle ${\displaystyle a,b\in M}$
        ${\displaystyle a\lesssim b\iff \forall x\in M\colon (x\lesssim a\Rightarrow x\lesssim b)}$.
  Diese Eigenschaft ist sogar charakterisierend für Quasiordnungen: jede Relation ${\displaystyle \lesssim }$ mit dieser Eigenschaft ist eine Quasiordnung.
• Ist ${\displaystyle (M,\lesssim )}$ eine Quasiordnung, dann gilt ${\displaystyle a\lesssim b\wedge b\lesssim a}$ genau dann, wenn für alle ${\displaystyle x}$
        ${\displaystyle x\lesssim a\iff x\lesssim b}$
  gilt.
• Beim Vergleich zweier quasigeordneter Elemente ${\displaystyle a}$ und ${\displaystyle b}$ gibt es maximal vier Möglichkeiten:

${\displaystyle a\lesssim b\wedge b\not \lesssim a}$	${\displaystyle a}$ ist (echt) kleiner als ${\displaystyle b}$.
${\displaystyle a\lesssim b\wedge b\lesssim a}$	${\displaystyle a}$ ist äquivalent zu (bei den antisymmetrischen Quasiordnungen: gleich) ${\displaystyle b}$.
${\displaystyle a\not \lesssim b\wedge b\lesssim a}$	${\displaystyle a}$ ist (echt) größer als ${\displaystyle b}$.
${\displaystyle a\not \lesssim b\wedge b\not \lesssim a}$	${\displaystyle a}$ und ${\displaystyle b}$ sind nicht vergleichbar.

Bei den totalen unter den Quasiordnungen kommt das vierte Ergebnis nicht vor – es bleiben maximal drei Möglichkeiten, und man spricht von einer Trichotomie der Ordnung.

• Der wechselseitige Einschluss ${\displaystyle a\lesssim b\wedge b\lesssim a}$ ist bei einer partiellen Quasiordnung eine partielle Äquivalenzrelation, also symmetrisch und transitiv.

Beispiele und Gegenbeispiele

• Vergleicht man komplexe Zahlen anhand ihres Betrags, erhält man eine totale Quasiordnung. Deren Definition lautet also: ${\displaystyle a\lesssim b:\Longleftrightarrow |a|\leq |b|}$. Dies ist keine Halbordnung, da zum Beispiel die Zahlen ${\displaystyle 1}$ und ${\displaystyle \mathrm {i} }$ gegenseitig vergleichbar sind, also ${\displaystyle 1\lesssim \mathrm {i} }$ und ${\displaystyle \mathrm {i} \lesssim 1}$ gilt.
• Auf der Knotenmenge eines gerichteten Graphen erhält man eine Quasiordnung durch die Festlegung
  ${\displaystyle a\lesssim b:\Longleftrightarrow }$ es gibt einen gerichteten Weg von ${\displaystyle a}$ nach ${\displaystyle b}$ (${\displaystyle b}$ ist also von ${\displaystyle 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, kommt die Antisymmetrie hinzu, so dass eine Halbordnung vorliegt.
• Ist das Vergleichen von (reellen oder rationalen) Zahlen mit einer Schwankungsbreite (Messabweichung, Ungenauigkeit) behaftet, dann handelt es sich nicht um eine Quasiordnung, da die zugehörige Duplikatrelation (siehe unten) 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.
• Die auf Computern üblichen IEEE-Gleitkommazahlen sind mit der Ordnung <= eine partielle Quasiordnung. Sie ist nicht voll reflexiv, weil für NaN-Werte jeder Vergleich falsch ist. Daher ist auch == auch nur eine partielle Äquivalenzrelation. Sie ist auch keine Halbordnung, weil +0.0 == −0.0, also +0.0 <= −0.0 und +0.0 >= −0.0 gilt, die beiden aber nicht identisch sind: Die Berechnung 1.0/(+0.0) ergibt positive Unendlichkeit und 1.0/(−0.0) die negative; die natürlich verschieden sind.

Induzierte Äquivalenzrelation und Striktordnung

Eine Quasiordnung ${\displaystyle \lesssim }$ auf einer Menge ${\displaystyle M\ }$ erzeugt eine Äquivalenzrelation – die „kanonische“, das heißt die zu ${\displaystyle \lesssim }$ gehörige, ausgezeichnete Äquivalenzrelation –   ${\displaystyle \sim }$ auf ${\displaystyle M\ }$ durch die Festlegung

${\displaystyle 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. Ist ${\displaystyle \lesssim }$ bereits eine Äquivalenzrelation, entsteht durch diese Konstruktion wieder ${\displaystyle \lesssim }$ .

Die Nebenklasse von ${\displaystyle a}$ ist die Menge

${\displaystyle {\bar {a}}:=\{x\mid x\sim a\}}$ .

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

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

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

Zwischen d​er Ursprungsrelation u​nd den 2 induzierten Relationen besteht d​er folgende Zusammenhang:

${\displaystyle a\lesssim b\Longleftrightarrow a\sim b\vee a<b\ }$,

wobei d​ie zwei Bedingungen a​uf der rechten Seite s​ich 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).

Ein gerichteter Graph

• 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 ${\displaystyle a<b}$, wenn es zwar einen gerichteten Weg von ${\displaystyle a}$ nach ${\displaystyle b}$, aber keinen gerichteten Weg von ${\displaystyle b}$ nach ${\displaystyle a}$ gibt. Die drei Äquivalenzklassen beim nebenstehenden Graphen sind also ${\displaystyle \left\{A\right\},\left\{B,C,D,E\right\},\left\{F\right\}.}$ Außerdem gilt für die induzierte strenge Halbordnung: ${\displaystyle 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 oder Faktormenge ${\displaystyle M/\!\sim }$   (also der Menge der Äquivalenzklassen) erhält man die kanonische Halbordnung durch die wohldefinierte Festlegung

${\displaystyle [x]\leq [y]:\Longleftrightarrow x\lesssim y}$

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

Ist d​ie gegebene Quasiordnung total, d​ann ist d​as Ergebnis e​ine Totalordnung.

Beispiele:

• Beim Vergleich komplexer Zahlen anhand ihres Betrags (siehe oben) ist die Halbordnung auf der Quotientenmenge isomorph zur gewöhnlichen (totalen) Ordnung ${\displaystyle \leq \ }$ 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).

Spiegelung

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

${\displaystyle a\lesssim _{2}b:\Longleftrightarrow \ b\lesssim a\;\;}$ (siehe auch Umkehrrelation).

Normalerweise n​immt man d​ann die Schreibweise:

${\displaystyle a\gtrsim b:\Longleftrightarrow \ b\lesssim a}$ .

Ist d​ie gegebene Quasiordnung total, d​ann ist a​uch das Ergebnis total.

Ist s​ie eine Halbordnung, s​o auch d​as Ergebnis.

Die Spiegelung d​er Spiegelung i​st das Original.

Komposition (Zusammensetzung, Hintereinanderschaltung)

Komponentenweise Zusammensetzung

Auf zwei quasigeordneten Mengen ${\displaystyle (M_{1},\lesssim _{1})}$ und ${\displaystyle (M_{2},\lesssim _{2})}$ kann die Zusammensetzung komponentenweise-kleiner-oder-gleich ${\displaystyle \lesssim _{1}\!\oplus \!\lesssim _{2}}$ auf der Menge ${\displaystyle M_{1}\!\times \!M_{2}}$ der Paare wie folgt definiert werden:

${\displaystyle {\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 ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{1}\!\oplus \!\lesssim _{2})}$ ist wieder eine Quasiordnung.

Asymmetrie bleibt erhalten. Totalität g​eht jedoch verloren, d​as heißt, b​ei zwei totalen Quasiordnungen bleibt n​ur eine Quasiordnung, b​ei zwei Totalordnungen n​ur eine Halbordnung übrig. (Beispiel: (1,0) i​st nicht vergleichbar m​it (0,1).)

Eine Art Kommutativität ist vorhanden, denn ${\displaystyle (M_{2}\!\times \!M_{1},\lesssim _{2}\!\oplus \!\lesssim _{1})}$ ist isomorph zu ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{1}\!\oplus \!\lesssim _{2})}$ .

Lexikographische Zusammensetzung

Für zwei quasigeordnete Mengen ${\displaystyle (M_{1},\lesssim _{1})}$ und ${\displaystyle (M_{2},\lesssim _{2})}$ wird die lexikographische Zusammensetzung ${\displaystyle \lesssim _{1}\!\otimes \!\lesssim _{2}}$ auf der Menge ${\displaystyle M_{1}\!\times \!M_{2}}$ der Paare wie folgt definiert:

${\displaystyle {\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 ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{1}\!\otimes \!\lesssim _{2})}$ ist wieder eine Quasiordnung.

Sind die gegebenen Quasiordnungen alle total (auf ihren jeweiligen Komponentmengen), und nur dann, entsteht wieder eine totale Quasiordnung. Sind sie allesamt Halbordnungen, entsteht wieder eine Halbordnung; sind sie Totalordnungen, entsteht wieder eine Totalordnung.

Die folgenden Quasiordnungen für variabel lange Symbolsequenzen (Wörter) lassen sich nach dem lexikographischen Prinzip ableiten. Sei dazu ${\displaystyle (M,\lesssim )}$ quasigeordnet und seien ${\displaystyle l_{a}:=\operatorname {length} (a)}$ und ${\displaystyle l_{b}:=\operatorname {length} (b)}$ die Längen zweier Wörter

${\displaystyle a,b\in M^{*}:=\bigcup _{l\in \mathbb {N} _{0}}\underbrace {M\times \dotsb \times M} _{l{\text{-mal}}}}$       (Kleenesche Hülle von ${\displaystyle M}$)

und sei ${\displaystyle m:=\operatorname {min} (l_{a},l_{b})}$.

1. Dann wird ${\displaystyle M^{*}\ }$ durch
         ${\displaystyle a\lesssim \ b\;:\Longleftrightarrow \ \operatorname {left} (a,m)<\operatorname {left} (b,m)\,\,\,\vee \,\,\,{\bigl (}\operatorname {left} (a,m)\sim \operatorname {left} (b,m)\,\wedge \,l_{a}\leq l_{b}{\bigr )}}$
   quasigeordnet, wobei für die Ordnung der gleich langen Wörter ${\displaystyle \operatorname {left} (a,m),\operatorname {left} (b,m)}$ der Einfachheit halber wieder   ${\displaystyle <}$   für   ${\displaystyle \sim \!\otimes \!\sim \!\otimes \!\dotsb \!\otimes \!<\!\otimes \,?\otimes \!\dotsb \!\otimes \,?}$   und   ${\displaystyle \sim }$   für   ${\displaystyle \sim \!\otimes \!\dotsb \!\otimes \!\sim }$   geschrieben ist. M. a. .W.: Ist ${\displaystyle i}$ der kleinste Index mit ${\displaystyle a_{i}\not \sim b_{i},}$ dann gilt ${\displaystyle a<b\Longleftrightarrow a_{i}<b_{i}.}$ Außerdem ist das leere Wort ${\displaystyle <}$ als alle nicht-leeren Wörter.
   Die so zusammengesetzte Ordnung nennt man wieder lexikographisch. Sie entspricht der Zusammensetzung
         ${\displaystyle (M^{*},\lesssim \!\otimes \dotsb \otimes \!\lesssim )=:(M^{*},\lesssim )}$
   aus lauter gleichen Komponenten ${\displaystyle (M,\lesssim )}$ .
2. Eine andere Zusammensetzung mit sehr ähnlichen ordnungstheoretischen Eigenschaften ist die quasi-lexikographische
         ${\displaystyle a\lesssim _{q}b\;:\Longleftrightarrow \ l_{a}<l_{b}\,\,\,\vee \,\,\,{\bigl (}l_{a}=l_{b}\,\wedge \,\operatorname {left} (a,m)\lesssim \operatorname {left} (b,m){\bigr )}}$[1]
   mit analogem Zeichen ${\displaystyle \lesssim }$ für die Ordnung gleich langer Wörter.

Assoziativität

Die Zusammensetzungen ${\displaystyle \oplus ,\otimes }$ verhalten sich assoziativ, das heißt ${\displaystyle {\bigl (}(M_{1},\lesssim _{1})\oplus (M_{2},\lesssim _{2}){\bigr )}\oplus (M_{3},\lesssim _{3})\;=\;(M_{1},\lesssim _{1})\oplus {\bigl (}(M_{2},\lesssim _{2})\oplus (M_{3},\lesssim _{3}){\bigr )}}$ und ${\displaystyle {\bigl (}(M_{1},\lesssim _{1})\otimes (M_{2},\lesssim _{2}){\bigr )}\otimes (M_{3},\lesssim _{3})\;=\;(M_{1},\lesssim _{1})\otimes {\bigl (}(M_{2},\lesssim _{2})\otimes (M_{3},\lesssim _{3}){\bigr )}}$  .

Bemerkungen:

1. Bei den Tabellenkalkulationsprogrammen entspricht eine „Spalte“ einer Komponentmenge ${\displaystyle M_{i}\ }$. Die in diesen Programmen häufig angebotene Sortierfunktion entspricht einer lexikographischen Zusammensetzung mit zu spezifizierender Rangfolge der Spalten, wobei es in der Regel zu jeder Spalte eine „Standard“-Ordnung gibt, die eine totale (fürs Sortieren erforderlich!) Quasiordnung ist. Es kann die „aufsteigende“ oder „absteigende“ Sortierreihenfolge gewählt werden.
2. Wenn die einzelnen Spalten stabil sortiert werden, dann kann die Gesamtsortierung in Einzelsortierungen der umgekehrten Rangfolge zerlegt werden.

Urbild einer Ordnungsrelation

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

${\displaystyle a_{0}\lesssim _{f}b_{0}:\Longleftrightarrow f(a_{0})\lesssim f(b_{0})}$

die Menge ${\displaystyle (M_{0},\lesssim _{f})}$ quasigeordnet werden.

Ist ${\displaystyle (M,\lesssim )}$ total quasigeordnet, so ist es auch ${\displaystyle (M_{0},\lesssim _{f})}$ .

Ist ${\displaystyle (M,\lesssim )}$ eine Halbordnung, so ist ${\displaystyle (M_{0},\lesssim _{f})}$ eine Halbordnung genau dann, wenn ${\displaystyle 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 allzu viel ausgesagt, da hier neben Sonderproblematiken wie den Umlauten zum Beispiel auch die Beachtung/Nichtbeachtung der Groß-/Kleinschreibung und Sonderzeichen die Abbildung zu einer nicht-injektiven machen kann.

Erweiterung

Ist ${\displaystyle (M_{1},\lesssim )}$ eine Quasiordnung und ${\displaystyle M_{2}\ }$ eine beliebige nicht-leere Menge, so kann ${\displaystyle \lesssim }$ wie folgt auf die Menge ${\displaystyle M_{1}\!\times \!M_{2}}$ erweitert werden:

${\displaystyle {\left(a_{1},a_{2}\right)}\lesssim _{2}{\left(b_{1},b_{2}\right)}\;\;\;:\Longleftrightarrow \;\;\;a_{1}\lesssim b_{1}}$ .

Wie ${\displaystyle \lesssim }$ ist auch ${\displaystyle (M_{1}\!\times \!M_{2},\lesssim _{2})}$ eine Quasiordnung.

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

Antisymmetrie geht im Allgemeinen verloren, das heißt, wenn die gegebene Quasiordnung ${\displaystyle \lesssim }$ eine Halbordnung (bzw. Totalordnung) ist, ist das Ergebnis nur dann wieder eine Halbordnung (bzw. Totalordnung), wenn ${\displaystyle M_{2}\ }$ aus genau einem Element besteht. Besteht ${\displaystyle M_{2}\ }$ aus mehreren Elementen, so ist das Ergebnis nur noch eine Quasiordnung (bzw. totale Quasiordnung).

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

Zusammensetzung auf der Grundmenge

Hat man auf einer Menge ${\displaystyle M}$ mehrere Quasiordnungen ${\displaystyle \lesssim _{1},\lesssim _{2},\ldots }$, so kann man ähnlich wie oben die lexikographischen Zusammensetzungen ${\displaystyle (M,\lesssim _{1}\!\otimes \!\lesssim _{2}\!\otimes ...)}$ bilden gemäß

${\displaystyle 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 ${\displaystyle \tau }$ .

${\displaystyle (M,\lesssim _{1}\!\otimes \!\lesssim _{2}\!)}$ ist eine Verfeinerung von ${\displaystyle (M,\lesssim _{1}\!)}$. Das heißt auch, dass eine einer (auf ganz ${\displaystyle M}$ totalen) Totalordnung nachgeschaltete Quasiordnung nichts mehr ändert.

Beispiel:

• Sei ${\displaystyle M:=\mathbb {N} }$ die Menge der natürlichen Zahlen, ${\displaystyle \lesssim _{1}\;:=\;<_{\varphi }}$ mit der (nicht-injektiven) Eulerschen ${\displaystyle \varphi }$-Funktion und ${\displaystyle \lesssim _{2}\;:=\;<}$ die übliche Kleinerrelation, dann ordnet die Totalordnung   ${\displaystyle (\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 ${\displaystyle \varphi }$-Werte.

Einschränkung einer Quasiordnung

In naheliegender Weise wird von einer Quasiordnung ${\displaystyle (M_{1},\lesssim )}$ die Einschränkung ${\displaystyle (M_{2},\lesssim )}$ auf eine Teilmenge ${\displaystyle M_{2}\subseteq M_{1}}$ gebildet.

Bemerkung:

• Die Definitionsbereiche sind in der Regel 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.

Intervalle

Ähnlich w​ie bei d​en Zahlen lässt s​ich allgemeiner b​ei quasigeordneten Mengen e​in Intervallbegriff einführen – i​n einer Notation, w​ie man s​ie von d​er Schule h​er kennt:

${\displaystyle [a,b]}$	${\displaystyle$ :=\{x\mid a\lesssim x\;\wedge \;x\lesssim b\}}
${\displaystyle {[}a,b{)}:=\,{[}a,b{[}}$	${\displaystyle$ :=\{x\mid a\lesssim x\;\wedge \;x<b\}}
${\displaystyle {(}a,b{]}:=\,{]}a,b{]}}$	${\displaystyle$ :=\{x\mid a<x\;\wedge \;x\lesssim b\}}
${\displaystyle (a,b):=\,{]}a,b{[}}$	${\displaystyle$ :=\{x\mid a<x\;\wedge \;x<b\}}

Die Duplikatsklasse von ${\displaystyle a}$ ist dann ${\displaystyle {\bar {a}}=[a,a]=:[a]}$ .

Für uneigentliche Intervalle g​ibt es d​ie Notationen:

${\displaystyle {[}a,\;{)}\;:=\,{[}a,\;{[}}$	${\displaystyle$ :=\,\{x\mid a\lesssim x\}}
${\displaystyle (a,\;)\,:=\,{]}a,\;{[}}$	${\displaystyle$ :=\,\{x\mid a<x\}}
${\displaystyle {(}\;,a{]}\;:=\,{]}\;,a{]}}$	${\displaystyle$ :=\,\{x\mid x\lesssim a\}}
${\displaystyle (\;,a)\,:=\,{]}\;,a{[}}$	${\displaystyle$ :=\,\{x\mid x<a\}}

Fußnoten

1. im Englischen quasi-lexicographic, radix, length-plus-lexicographic oder shortlex order

Siehe auch

• gerichtete Menge
• transitive Hülle
• Wohlquasiordnung