Strenge schwache Ordnung

Eine strenge schwache Ordnung ist eine Ordnungsrelation, die mehrere gleichartige Objekte erlaubt, sonst aber eine eindeutige Reihenfolge definiert.

Beispiel: Die Relation A kostet weniger als B ist eine strenge schwache Ordnung: Zwei oder mehrere verschiedene Objekte können gleich viel kosten, aber sonst ist stets eindeutig, welches Objekt weniger kostet.

Mathematische Definition

Eine strenge schwache Ordnung < ist eine Striktordnung, bei der zusätzlich negative Transitivität 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\not< b \land b\not < c \Rightarrow a\not< c}

Beispiel: Wenn Milch nicht weniger kostet als Brot, und Brot nicht weniger als Kuchen, dann kostet Milch auch nicht weniger als Kuchen.

Daraus folgt insbesondere, dass die Relation

$a\sim b:=a\not <b\land b\not <a$

eine Äquivalenzrelation ist, denn in einer Striktordnung gilt:

(Reflexivität)

$a\not <a$, also $a\sim a.$

Direkt aus der Definition folgt:

(Symmetrie)

$a\sim b\Rightarrow b\sim a$,

und für:

(Transitivität)

$a\sim b\land b\sim c$,

also

$a\not <b\land b\not <a\land b\not <c\land c\not <b$

gilt wegen der negativen Transitivität

$a\not <c\land c\not <a$,

oder

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 c}

Die strenge schwache Ordnung induziert dabei eine strenge Totalordnung auf den Äquivalenzklassen dieser Relation.

Im Beispiel: „A kostet nicht weniger als B, und B kostet nicht weniger als A“ ist eine Äquivalenzrelation: „A und B kosten gleich viel“. Die Äquivalenzklassen enthalten alle Produkte mit gleichem Preis, und die darauf induzierte strenge Totalordnung ist einfach die Ordnung der Preise.

Ist < darüber hinaus eine strenge Totalordnung, so ist die Ä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} die Gleichheit.

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

Die zugehörige nichtstrikte Relation 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 \Leftrightarrow x < y \vee x=y} nennt man Präferenzrelation (siehe Präferenz). Eine Präferenzrelation ist also eine partielle 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} , für die gilt, dass die Relation „x=y oder x,y sind unvergleichbar“ eine Äquivalenzrelation ist. Jede strenge schwache Ordnung induziert (wie eben beschrieben) eine Präferenzrelation, und jede Präferenzrelation induziert umgekehrt eine strenge schwache Ordnung.

Konstruktion strenger schwacher Ordnungen

Jede strenge Totalordnung ist eine strenge schwache Ordnung. Zudem kann man aus strengen schwachen Ordnungen nach folgenden Regeln weitere strenge schwache Ordnungen konstruieren:

• Hat man eine Abbildung $f\colon A\rightarrow B$, und ist auf der Menge $B$ die strenge schwache Ordnung $<_{B}$ definiert, so ist auch die Ordnung ${<_{A}}:=\{(a,b)\in A\times A:f(a)<_{B}f(b)\}$ eine strenge schwache Ordnung.

Beispiele:

• Geldbeträge unterliegen einer strengen 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 <_B} . Der Preis ist eine Funktion, die von der Menge der Waren auf die Menge der Geldbeträge abbildet (jeder Ware wird ein Geldbetrag, der Preis der Ware, zugeordnet). Damit ist die zugehörige Relation 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} (kostet weniger als) eine strenge schwache Ordnung.
• Auch das Auswählen eines Elements aus einem Tupel ist eine Funktion. Eine strenge schwache Ordnung auf diesem Element liefert somit auch eine strenge schwache Ordnung auf den Tupeln. So kommt man z. B. von der alphabetischen Ordnung der Namen auf eine Ordnung von Adressen nach dem Namen.

• Sind 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 $<_{2}$ strenge schwache Ordnungen 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 A} , so 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 {<}:=\{(a,b) \in A\times A: a <_1 b \lor (b \sim_1 a \land a <_2 b)\}} eine strenge schwache Ordnung.

Beispiel:

Ist Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle <_{1}} die alphabetische Ordnung auf dem Nachnamen 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 <_2} die alphabetische Ordnung auf dem Vornamen, 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 < } die übliche Ordnung auf dem Namen: Zunächst wird der Nachname verglichen, bei gleichem Nachnamen der Vorname.

Eine Erweiterung dieser Regel auf beliebig lange Listen ergibt die lexikographische Ordnung. Diese liefert beispielsweise aus der Ordnung der Buchstaben die alphabetische Ordnung der Wörter.

Anwendung

Die üblichen Sortierverfahren funktionieren nicht nur für Totalordnungen, sondern auch für strenge schwache Ordnungen. Hierbei unterscheidet man zwischen stabilen und instabilen Sortierverfahren: Stabile Sortierverfahren ändern die Reihenfolge äquivalenter Elemente beim Sortieren nicht, instabile können diese verändern.

Beispiel: Auf der Menge aller Wörter ist die Relation A hat weniger Buchstaben als B eine strenge schwache Ordnung. Liegt nun die unsortierte Liste

Hund Katze Maus Elefant Nashorn Vogel

vor, so liefert ein stabiler Sortieralgorithmus für diese Relation stets

Hund Maus Katze Vogel Elefant Nashorn

während ein instabiler Sortieralgorithmus auch z. B.

Maus Hund Vogel Katze Nashorn Elefant

liefern kann.

Weitere Beispiele

In der Newtonschen Physik bildet die Kausalordnung (Zeitordnung) von Ereignissen eine strenge schwache Ordnung. Bezüglich der Zeitordnung äquivalente Ereignisse werden gleichzeitig genannt. In der Relativitätstheorie gilt dies nicht mehr.