Hauptmenü öffnen

Quasiordnung

abgeschwächte Variante einer Halbordnung

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.

DefinitionenBearbeiten

QuasiordnungBearbeiten

 
4 Typen von Ordnungsrelationen in Beziehung:   A   B: A ist B; A   B: aus A wird B bei Quotientenbildung; A   B: aus A wird B bei Erweiterung; A   B: aus A wird B bei komponentenweiser Komposition

Eine zweistellige Relation   auf einer Menge   heißt eine Quasiordnung (englisch preorder), wenn sie reflexiv und transitiv ist. Für alle   muss also gelten

  (Reflexivität)
  (Transitivität)

Man nennt dann   eine quasigeordnete Menge oder kurz eine Quasiordnung.

Totale QuasiordnungBearbeiten

Eine Quasiordnung heißt total, auch Präferenzordnung, (englisch total preorder), wenn je zwei Elemente immer vergleichbar sind. Für alle   muss also gelten:

  (Totalität)

Man nennt dann   eine total quasigeordnete Menge oder kurz eine totale Quasiordnung.

Partielle QuasiordnungBearbeiten

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   auf einer Menge   heißt partielle Quasiordnung (englisch partial preorder), wenn sie reflexiv und transitiv ist, wo sie definiert ist. Für alle   muss also gelten

  (partielle Reflexivität)
  (Transitivität)

Man nennt dann   eine partiell quasigeordnete Menge oder kurz eine partielle Quasiordnung.

EigenschaftenBearbeiten

  • Eine Halbordnung (englisch partial order) ist eine Quasiordnung.
  • Eine Totalordnung (englisch total order) ist eine totale Quasiordnung (und auch eine Halbordnung).
  • Ist   eine Quasiordnung, dann gilt für alle  
           .
    Diese Eigenschaft ist sogar charakterisierend für Quasiordnungen: jede Relation   mit dieser Eigenschaft ist eine Quasiordnung.
  • Ist   eine Quasiordnung, dann gilt   genau dann, wenn für alle  
           
    gilt.
  • Beim Vergleich zweier quasigeordneter Elemente   und   gibt es maximal vier Möglichkeiten:
    ist (echt) kleiner als  .
    ist äquivalent zu (bei den antisymmetrischen Quasiordnungen: gleich)  .
    ist (echt) größer als  .
    und   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   ist bei einer partiellen Quasiordnung eine partielle Äquivalenzrelation, also symmetrisch und transitiv.

Beispiele und GegenbeispieleBearbeiten

  • Vergleicht man komplexe Zahlen anhand ihres Betrags, erhält man eine totale Quasiordnung. Deren Definition lautet also:  . Dies ist keine Halbordnung, da zum Beispiel die Zahlen   und   gegenseitig vergleichbar sind, also   und   gilt.
  • Auf der Knotenmenge eines gerichteten Graphen erhält man eine Quasiordnung durch die Festlegung
      es gibt einen gerichteten Weg von   nach   (  ist also von   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 (Ungenauigkeit) behaftet, dann handelt es sich nicht um eine Quasiordnung, da die zugehörige Duplikatrelation 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-Fließkommazahlen 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 StriktordnungBearbeiten

Eine Quasiordnung   auf einer Menge   erzeugt eine Äquivalenzrelation – die „kanonische“, das heißt die zu   gehörige, ausgezeichnete Äquivalenzrelation –     auf   durch die Festlegung

  .

Zwei Elemente sind also äquivalent, wenn sie gegenseitig vergleichbar sind. Diese Äquivalenzrelation sei der Kürze halber als Duplikatrelation der Quasiordnung bezeichnet. Ist   bereits eine Äquivalenzrelation, entsteht durch diese Konstruktion wieder   .

Die Nebenklasse von   ist die Menge

  .

Weiterhin erhält man die kanonische Striktordnung   auf   vermöge

  .

Ist   total, dann ist   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:

 ,

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  , wenn es zwar einen gerichteten Weg von   nach  , aber keinen gerichteten Weg von   nach   gibt. Die drei Äquivalenzklassen beim nebenstehenden Graphen sind also   Außerdem gilt für die induzierte strenge Halbordnung:  
  • 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.

QuotientenmengeBearbeiten

Auf der Quotientenmenge oder Faktormenge     (also der Menge der Äquivalenzklassen) erhält man die kanonische Halbordnung durch die wohldefinierte Festlegung

 

(wobei die Klasse von   mit   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   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).

SpiegelungBearbeiten

Eine Quasiordnung   kann gespiegelt werden:

  (siehe auch Umkehrrelation).

Normalerweise nimmt man dann die Schreibweise:

  .

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)Bearbeiten

Komponentenweise ZusammensetzungBearbeiten

Auf zwei quasigeordneten Mengen   und   kann die Zusammensetzung komponentenweise-kleiner-oder-gleich   auf der Menge   der Paare wie folgt definiert werden:

 

Die Zusammensetzung   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 Kommunitativität ist vorhanden, denn   ist isomorph zu   .

Lexikographische ZusammensetzungBearbeiten

Auf zwei quasigeordneten Mengen   und   kann die lexikographische Zusammensetzung   auf der Menge   der Paare wie folgt definiert werden:

 

Die Zusammensetzung   ist wieder eine Quasiordnung. (Für die Ordnung der gleich langen Wörter unten sei der Einfachheit halber wieder   gesetzt.)

Nach dem lexikographischen Prinzip lassen sich folgende Quasiordnungen für variabel lange Symbolsequenzen ableiten:

Sei   quasigeordnet und seien   und   die Längen zweier Wörter   (Kleenesche Hülle) und  , dann kann   sowohl durch:

 [1]

als auch durch:

 

quasigeordnet werden. Letztere Zusammensetzung nennt man wieder lexikographisch.

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 sogar Totalordnungen, entsteht wieder eine Totalordnung.

AssoziativitätBearbeiten

Die genannten Zusammensetzungen verhalten sich assoziativ, das heißt   und   .

Bemerkung:

  • Bei den Tabellenkalkulationsprogrammen entspricht eine „Spalte“ einer Komponentmenge  . 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 meist eine totale Quasiordnung, seltener eine echte Totalordnung (und dann höchstens auf der entsprechenden Spalte) ist. Es kann die „aufsteigende“ oder „absteigende“ Sortierreihenfolge gewählt werden.

Urbild einer OrdnungsrelationBearbeiten

Sei   eine nicht-leere Menge,   eine quasigeordnete Menge und   eine beliebige Abbildung. Dann kann vermöge

 

die Menge   quasigeordnet werden.

Ist   total quasigeordnet, so ist es auch   .

Ist   eine Halbordnung, so ist   eine Halbordnung genau dann, wenn   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.

ErweiterungBearbeiten

Ist   eine Quasiordnung und   eine beliebige nicht-leere Menge, so kann   wie folgt auf die Menge   erweitert werden:

  .

Wie   ist auch   eine Quasiordnung.

Ist   total, so ist das Ergebnis wieder eine totale Quasiordnung.

Antisymmetrie geht im Allgemeinen verloren, das heißt, wenn die gegebene Quasiordnung   eine Halbordnung (bzw. Totalordnung) ist, ist das Ergebnis nur dann wieder eine Halbordnung (bzw. Totalordnung), wenn   aus genau einem Element besteht. Besteht   aus mehreren Elementen, so ist das Ergebnis nur noch eine Quasiordnung (bzw. totale Quasiordnung).

  ist die Quasiordnung       (mit der trivialen Ordnung   auf  ). Man kann sich   als eine Vergleichsfunktion vorstellen, die auf ihren Schlüsselfeldern in   operiert. Die Ergebnisordnung kann also ohne Verlust an Genauigkeit wieder mit       bezeichnet werden.

Zusammensetzung auf der GrundmengeBearbeiten

Hat man auf einer Menge   mehrere Quasiordnungen  , so kann man ähnlich wie oben die lexikographischen Zusammensetzungen   bilden gemäß

  .

Sie bilden eine (nicht-kommutative) Halbgruppe mit dem (beidseitig) neutralen Element   .

  ist eine Verfeinerung von  . Das heißt auch, dass eine einer (auf ganz   totalen) Totalordnung nachgeschaltete Quasiordnung nichts mehr ändert.

Beispiel:

  • Sei   die Menge der natürlichen Zahlen,   mit der (nicht-injektiven) Eulerschen  -Funktion und   die übliche Kleinerrelation, dann ordnet die Totalordnung    
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  -Werte.

Einschränkung einer QuasiordnungBearbeiten

In naheliegender Weise wird von einer Quasiordnung   die Einschränkung   auf eine Teilmenge   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.

IntervalleBearbeiten

Ä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:

   
   
   
   

Die Duplikatsklasse von   ist dann   .

Für uneigentliche Intervalle gibt es die Notationen:

   
   
   
   

FußnotenBearbeiten

  1. auch als quasi-lexikographische Ordnung bezeichnet (im Englischen quasi-lexicographic, radix, length-plus-lexicographic oder shortlex order)

Siehe auchBearbeiten