Strenge schwache Ordnung

Eine strenge schwache Ordnung ist eine Ordnung, die verschiedene gleichartige Objekte erlaubt, amsonsten eine eindeutige Reihenfolge definiert.

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

Mathematische Definition

Eine strenge schwache Ordnung R ist eine Teilordnung, bei der zusätzlich die Bedingung gilt:

$\neg aRb\land \neg bRc\Rightarrow \neg aRc$

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:=\neg aRb\land \neg bRa$

eine Äquivalenzrelation ist.

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:A->B$, und ist auf der Menge $B$ die strenge schwache Ordnung $R_{B}$ definiert, so ist auch die Ordnung $R_{A}:=\{(a,b)\in A\times A:f(a)R_{B}f(b)\}$ eine strenge schwache Ordnung.

Beispiele:

• Geldbeträge unterliegen einer strengen Totalordnung $R_{B}$ (kleiner als). 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 $R_{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 $R_{1}$ und $R_{2}$ strenge schwache Ordnungen auf $A$, so ist auch $R:=\{(a,b)\in A\times A:aR_{1}b\lor (\neg bR_{1}a\land aR_{2}b)\}$ eine strenge schwache Ordnung.

Beispiel:

Ist $R_{1}$ die alphabetische Ordnung auf dem Nachnamen und $R_{2}$ die alphabetische Ordnung auf dem Vornamen, so ist $R$ 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 Sortieralgorithmen funktionieren nicht nur für Totalordnungen, sondern auch für strenge schwache Ordnungen. Hierbei unterscheidet man zwischen stabilen und instabilen Sortieralgorithmen: Stabile Sortieralgorithmen ändern die Reihenfolge äquivalenter Elemente beim sortieren nicht, instabile können diese verändern.

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.