Quasiordnung

Eine Quasiordnung, auch Präordnung, (englisch preorder) 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. Insbesondere die totalen Quasiordnungen treten in praktischen Anwendungen beim Anordnen von Objekten in Sortierverfahren, Tabellenkalkulationsprogrammen oder Datenbanken auf.

Definitionen

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 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.

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

(Totalität)

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

Partielle Quasiordnung

Die Reflexivität wird nicht mehr für alle Elemente verlangt, sondern nur noch für solche, die irgendwo in der Relation vorkommen.

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

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

Man nennt dann $(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 $(M,\lesssim )$ eine Quasiordnung, dann gilt für alle $a,b\in M$
$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 $\lesssim$ mit dieser Eigenschaft ist eine Quasiordnung.
Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim)} eine Quasiordnung, dann gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \lesssim b \wedge b \lesssim a} genau dann, wenn für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \lesssim a \iff x \lesssim b}
gilt.
Beim Vergleich zweier quasigeordneter Elemente Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} gibt es maximal vier Möglichkeiten:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \lesssim b \wedge b \not \lesssim a }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist (echt) kleiner als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} .
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \lesssim b \wedge b \lesssim a }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist äquivalent zu (bei den antisymmetrischen Quasiordnungen: gleich) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} .
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \not \lesssim b \wedge b \lesssim a }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist (echt) größer als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} .
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \not \lesssim b \wedge b \not \lesssim a }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \lesssim b:\Longleftrightarrow |a| \le |b|} . Dies ist keine Halbordnung, da zum Beispiel die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{i}} gegenseitig vergleichbar sind, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 \lesssim\mathrm{i}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathrm{i}\lesssim 1} gilt.
Auf der Knotenmenge eines gerichteten Graphen erhält man eine Quasiordnung durch die Festlegung
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \lesssim b:\Longleftrightarrow } es gibt einen gerichteten Weg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} ist also von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim} auf einer Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M \ } erzeugt eine Äquivalenzrelation – die „kanonische“, das heißt die zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim} gehörige, ausgezeichnete Äquivalenzrelation – Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sim} auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M \ } durch die Festlegung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim} bereits eine Äquivalenzrelation, entsteht durch diese Konstruktion wieder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim} .

Die Nebenklasse von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist die Menge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar a := \{x \mid x \sim a\}} .

Weiterhin erhält man die kanonische Striktordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle <\ } auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M \ } vermöge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a < b : \Longleftrightarrow a\lesssim b \wedge a \not\sim b} .

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim} total, dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle <\ } 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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).

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a < b} , wenn es zwar einen gerichteten Weg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} , aber keinen gerichteten Weg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} gibt. Die drei Äquivalenzklassen beim nebenstehenden Graphen sind also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left\{A\right\}, \left\{B, C, D, E\right\}, \left\{F\right\}.} Außerdem gilt für die induzierte strenge Halbordnung: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M/\!\sim} (also der Menge der Äquivalenzklassen) erhält man die kanonische Halbordnung durch die wohldefinierte Festlegung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [x] \le [y] : \Longleftrightarrow x \lesssim y }

(wobei die Klasse von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \ } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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).

Spiegelung

Eine Quasiordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim) } kann gespiegelt werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \lesssim_2 b :\Longleftrightarrow\ b \lesssim a \;\;} (siehe auch Umkehrrelation).

Normalerweise nimmt man dann die Schreibweise:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1,\lesssim_1) } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_2,\lesssim_2)} kann die Zusammensetzung komponentenweise-kleiner-oder-gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim_1 \! \oplus \! \lesssim_2} auf der Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_1 \! \times \! M_2} der Paare wie folgt definiert werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1 \! \times \! M_2,\lesssim_1 \! \oplus \! \lesssim_2)} ist wieder eine Quasiordnung.

Asymmetrie bleibt erhalten. Totalität geht jedoch verloren, das heißt, 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 Kommutativität ist vorhanden, denn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_2 \! \times \! M_1,\lesssim_2 \! \oplus \! \lesssim_1)} ist isomorph zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1 \! \times \! M_2,\lesssim_1 \! \oplus \! \lesssim_2)} .

Lexikographische Zusammensetzung

Für zwei quasigeordnete Mengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1,\lesssim_1) } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_2,\lesssim_2)} wird die lexikographische Zusammensetzung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim_1 \! \otimes \! \lesssim_2} auf der Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_1 \! \times \! M_2} der Paare wie folgt definiert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim)} quasigeordnet und seien Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_a := \operatorname{length}(a)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_b := \operatorname{length}(b)} die Längen zweier Wörter

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a,b \in M^* := \bigcup_{l \in \N_0} \underbrace{M \times \dotsb \times M}_{l\text{-mal}} } (Kleenesche Hülle von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} )

und sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m := \operatorname{min}(l_a,l_b)} .

Dann wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M^*\ } durch
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 \le l_b \bigr)}
quasigeordnet, wobei für die Ordnung der gleich langen Wörter Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{left}(a,m), \operatorname{left}(b,m) } der Einfachheit halber wieder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle < } für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sim \! \otimes \! \sim \! \otimes \! \dotsb \! \otimes \! < \! \otimes \, ? \otimes \! \dotsb \! \otimes \, ? } und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sim } für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \sim \! \otimes \! \dotsb \! \otimes \! \sim } geschrieben ist. M. a. .W.: Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i } der kleinste Index mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i \not\sim b_i, } dann gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a < b \Longleftrightarrow a_i < b_i . } Außerdem ist das leere Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle < } als alle nicht-leeren Wörter.
Die so zusammengesetzte Ordnung nennt man wieder lexikographisch. Sie entspricht der Zusammensetzung
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M^*, \lesssim \! \otimes \dotsb \otimes \! \lesssim) =: (M^*, \lesssim )}
aus lauter gleichen Komponenten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim) } .
Eine andere Zusammensetzung mit sehr ähnlichen ordnungstheoretischen Eigenschaften ist die quasi-lexikographische
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim } für die Ordnung gleich langer Wörter.

Assoziativität

Die Zusammensetzungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \oplus, \otimes } verhalten sich assoziativ, das heißt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Bei den Tabellenkalkulationsprogrammen entspricht eine „Spalte“ einer Komponentmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.
Wenn die einzelnen Spalten stabil sortiert werden, dann kann die Gesamtsortierung in Einzelsortierungen der umgekehrten Rangfolge zerlegt werden.

Urbild einer Ordnungsrelation

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_0 \ } eine nicht-leere Menge, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim) } eine quasigeordnete Menge und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\colon\, M_0 \to M} eine beliebige Abbildung. Dann kann vermöge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_0 \lesssim_f b_0 :\Longleftrightarrow f(a_0) \lesssim f(b_0)}

die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_0,\lesssim_f) } quasigeordnet werden.

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim) } total quasigeordnet, so ist es auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_0,\lesssim_f)} .

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim) } eine Halbordnung, so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_0,\lesssim_f) } eine Halbordnung genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1,\lesssim) } eine Quasiordnung und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_2 \ } eine beliebige nicht-leere Menge, so kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim } wie folgt auf die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_1 \! \times \! M_2} erweitert werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\left(a_1, a_2\right)} \lesssim_2 {\left(b_1, b_2\right)} \;\;\; :\Longleftrightarrow \;\;\; a_1 \lesssim b_1 } .

Wie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim } ist auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1 \! \times \! M_2,\lesssim_2) } eine Quasiordnung.

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim } total, so ist das Ergebnis wieder eine totale Quasiordnung.

Antisymmetrie geht im Allgemeinen verloren, das heißt, wenn die gegebene Quasiordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim } eine Halbordnung (bzw. Totalordnung) ist, ist das Ergebnis nur dann wieder eine Halbordnung (bzw. Totalordnung), wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_2 \ } aus genau einem Element besteht. Besteht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_2 \ } aus mehreren Elementen, so ist das Ergebnis nur noch eine Quasiordnung (bzw. totale Quasiordnung).

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim_2} ist die Quasiordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\lesssim \! \otimes \, \tau) } (mit der trivialen Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau\ } auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_2 \, } ). Man kann sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim } als eine Vergleichsfunktion vorstellen, die auf ihren Schlüsselfeldern in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M_1 \ } operiert. Die Ergebnisordnung kann also ohne Verlust an Genauigkeit wieder mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1 \! \times \! M_2, \lesssim)} bezeichnet werden.

Zusammensetzung auf der Grundmenge

Hat man auf einer Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} mehrere Quasiordnungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim_1, \lesssim_2, \ldots } , so kann man ähnlich wie oben die lexikographischen Zusammensetzungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim_1 \! \otimes \! \lesssim_2 \! \otimes ...)} bilden gemäß

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau} .

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim_1 \! \otimes \! \lesssim_2 \! )} ist eine Verfeinerung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M,\lesssim_1 \! )} . Das heißt auch, dass eine einer (auf ganz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} totalen) Totalordnung nachgeschaltete Quasiordnung nichts mehr ändert.

Beispiel:

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M := \mathbb N} die Menge der natürlichen Zahlen, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim_1 \; := \; <_{\varphi} } mit der (nicht-injektiven) Eulerschen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi} -Funktion und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lesssim_2 \; := \; < } die übliche Kleinerrelation, dann ordnet die Totalordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varphi} -Werte.

Einschränkung einer Quasiordnung

In naheliegender Weise wird von einer Quasiordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_1,\lesssim) } die Einschränkung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (M_2,\lesssim) } auf eine Teilmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 wie bei den Zahlen lässt sich allgemeiner bei quasigeordneten Mengen ein Intervallbegriff einführen – in einer Notation, wie man sie von der Schule her kennt:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [a,b] }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \{x\mid a \lesssim x \; \wedge \; x \lesssim b \} }
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {[}a,b{)} := \, {[}a,b{[} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \{x\mid a \lesssim x \; \wedge \; x < b \} }
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {(}a,b{]} := \, {]}a,b{]} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \{x\mid a<x \; \wedge \; x \lesssim b \}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a,b) := \, {]}a,b{[} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \{x\mid a<x \; \wedge \; x<b \}}

Die Duplikatsklasse von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar a = [a,a] =: [a] } .

Für uneigentliche Intervalle gibt es die Notationen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {[}a, \; {)} \; := \, {[}a, \; {[} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \, \{x\mid a \lesssim x \}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (a, \; ) \, := \, {]}a, \; {[} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \, \{x\mid a < x \}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {(} \; , a {]} \; := \, {]} \; , a {]} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \, \{x\mid x \lesssim a \}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ( \; , a) \, := \, {]} \; , a {[} }	Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle := \, \{x\mid x < a \}}

Fußnoten

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

Siehe auch

[1] Englischen quasi-lexicographic, radix, length-plus-lexicographic oder shortlex order

[1]

Anonym

Suche

Quasiordnung

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Definitionen

Quasiordnung

Totale Quasiordnung

Partielle Quasiordnung

Eigenschaften

Beispiele und Gegenbeispiele

Induzierte Äquivalenzrelation und Striktordnung

Quotientenmenge

Spiegelung

Komposition (Zusammensetzung, Hintereinanderschaltung)

Komponentenweise Zusammensetzung

Lexikographische Zusammensetzung

Assoziativität

Urbild einer Ordnungsrelation

Erweiterung

Zusammensetzung auf der Grundmenge

Einschränkung einer Quasiordnung

Intervalle

Fußnoten

Siehe auch

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Quasiordnung

Definitionen

Quasiordnung

Totale Quasiordnung

Partielle Quasiordnung

Eigenschaften

Beispiele und Gegenbeispiele

Induzierte Äquivalenzrelation und Striktordnung

Quotientenmenge

Spiegelung

Komposition (Zusammensetzung, Hintereinanderschaltung)

Komponentenweise Zusammensetzung

Lexikographische Zusammensetzung

Assoziativität

Urbild einer Ordnungsrelation

Erweiterung

Zusammensetzung auf der Grundmenge

Einschränkung einer Quasiordnung

Intervalle

Fußnoten

Siehe auch

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien