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:

$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

$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 $\sim$ die Gleichheit.

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

Die zugehörige nichtstrikte Relation $x\leq y\Leftrightarrow x<y\vee x=y$ nennt man Präferenzrelation. Eine Präferenzrelation ist also eine partielle Ordnung $\leq$ , 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 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 $<_{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 $<_{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 $<_{1}$ und $<_{2}$ strenge schwache Ordnungen auf , so ist auch ${<}:=\{(a,b)\in A\times A:a<_{1}b\lor (b\sim _{1}a\land a<_{2}b)\}$ eine strenge schwache Ordnung.

Beispiel:

Ist $<_{1}$ die alphabetische Ordnung auf dem Nachnamen und $<_{2}$ die alphabetische Ordnung auf dem Vornamen, so ist 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.

Basierend auf einem Artikel in:

Wikipedia.de