Strenge schwache Ordnung - LinkFang.de





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:

[math] a\not\lt b \and b\not \lt c \Rightarrow a\not\lt c[/math]

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

[math]a\sim b := a\not\lt b \and b\not\lt a[/math]

eine Äquivalenzrelation ist. 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 [math]\sim[/math] die Gleichheit.

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

Die zugehörige nichtstrikte Relation [math] x\le y \Leftrightarrow x \lt y \vee x=y[/math] nennt man Präferenzrelation (siehe Präferenz). Eine Präferenzrelation ist also eine partielle Ordnung [math]\le[/math], 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 [math]f:A \rightarrow B[/math], und ist auf der Menge [math]B[/math] die strenge schwache Ordnung [math]\lt_B[/math] definiert, so ist auch die Ordnung [math]{\lt_A} := \{(a,b)\in A \times A: f(a) \lt_B f(b)\}[/math] eine strenge schwache Ordnung.
Beispiele:
  • Geldbeträge unterliegen einer strengen Totalordnung [math]\lt_B[/math]. 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 [math]\lt_A[/math] (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 [math]\lt_1[/math] und [math]\lt_2[/math] strenge schwache Ordnungen auf [math]A[/math], so ist auch [math]{\lt}:=\{(a,b) \in A\times A: a \lt_1 b \or (b \sim_1 a \and a \lt_2 b)\}[/math] eine strenge schwache Ordnung.
Beispiel:
Ist [math]\lt_1[/math] die alphabetische Ordnung auf dem Nachnamen und [math]\lt_2[/math] die alphabetische Ordnung auf dem Vornamen, so ist [math]\lt [/math] 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.


Kategorien: Ordnungstheorie | Ordnungsstruktur

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Strenge schwache Ordnung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.