Ordnungsrelation

Ordnungsrelationen sind in der Mathematik Verallgemeinerungen der „kleiner-gleich“-Beziehung. Sie erlauben es, Elemente einer Menge miteinander zu vergleichen.

Eine Ordnungsrelation ist formal eine zweistellige Relation

auf einer Menge  mit bestimmten unten aufgeführten Eigenschaften, worunter immer die Transitivität ist.

Ist eine Menge  mit einer Ordnungsrelation  gegeben, dann nennt man das Paar  eine geordnete Menge. Meist bevorzugt man an Stelle der Schreibweise  die sogenannte Infix-Notation . Außerdem wird für Ordnungsrelationen nur selten ein Symbol wie  verwendet. Stattdessen verwendet man häufig Symbole wie ,  oder ähnliche. Die Schreibweisen  oder  verwendet man als Abkürzung für „ und “ oder „ und “.

Es folgt eine Auflistung verschiedener Arten von Ordnungsrelationen mit Beispielen. Für Definitionen der Eigenschaften siehe transitiv, reflexiv und irreflexiv, asymmetrisch, antisymmetrisch, oder den Artikel Relation (Mathematik).

Totalordnung 

Eine Relation  auf einer Menge  wird (schwache) Totalordnung oder totale Ordnung oder einfach (schwache) Ordnung genannt, wenn die Forderungen

für alle  erfüllt sind.
Da dies bei der Zahlengeraden, der „Linie“, der Fall ist, wird eine Totalordnung auch lineare Ordnung genannt. Ferner gibt es für totalgeordnete Untermengen von partiell geordneten Mengen die Bezeichnung Kette.

Die durch
 
definierte Umkehrrelation  einer Totalordnung  ist selbst eine Totalordnung. Bei Umkehrrelationen wird gerne das gespiegelte Symbol als Relationszeichen genommen, in diesem Fall  statt , also
.
Im Fall der totalen (Quasi-)Ordnungen hat dies eine besondere Berechtigung, weil bei ihnen die inverse Relation eine Spiegelung ist.

Eine endliche Untermenge einer totalgeordneten Menge lässt sich gemäß dieser Ordnung in eindeutiger Weise sortieren, das heißt in eine („lineare“) Reihenfolge bringen derart, dass jedes Element mit seinem Folgeelement in der Ordnungsbeziehung steht. Solchermaßen geordnet nennt man die Sortierung aufsteigend. Gilt stattdessen zwischen zwei Nachbarelementen die gespiegelte Ordnungsrelation, nennt man die Sortierung absteigend. Der schwächere Begriff der totalen Quasiordnung (siehe unten) erlaubt das Vorhandensein von „Duplikaten“, also eine nicht eindeutige Sortierung.

Beispiel und Gegenbeispiel:

Ein Beispiel ist die Relation  („kleiner-gleich“) auf den ganzen Zahlen .

Ein Gegenbeispiel ist die Teilmengenbeziehung  auf der Potenzmenge von : sie ist nicht total, denn es gilt weder  noch .

Strenge Totalordnung 
Eine Relation  auf  heißt strenge (oder auch starke) Totalordnung, wenn

für alle  gilt.

Da eine strenge Totalordnung nicht reflexiv ist, ist sie keine Totalordnung. Eine Totalordnung im oben erklärten schwachen Sinn ist aber die zu  gehörige Ordnung (mit Reflexivität und Antisymmetrie), die durch

definiert ist. Umgekehrt wird aus jeder (schwachen) Totalordnung  auf  per

eine strenge Totalordnung

Vergleichbarkeit 
Gilt für zwei Elemente  und , dass wenigstens eine der drei Beziehungen (und da sie sich gegenseitig ausschließen: genau eine)
  oder  oder 
erfüllt ist, dann nennt man  und  in  unter der Ordnungsrelation  vergleichbar.
Eine Ordnungsrelation, bei der jedes Element mit jedem vergleichbar ist, nennt man eine totale Ordnungsrelation.

Quasiordnung 

Eine Quasiordnung ist eine transitive und reflexive Relation.

Beispiel:

Für komplexe Zahlen  ist die über den Absolutbetrag durch „“ festgelegte Relation eine Quasiordnung.

Diese Quasiordnung ist nicht antisymmetrisch – also keine Halbordnung, denn betragsgleiche Zahlen müssen nicht identisch sein.

Jedoch handelt es sich um eine totale Quasiordnung, da je zwei Elemente vergleichbar sind.

Halbordnung 
Eine Halbordnung – auch Partialordnung, Teilordnung oder partielle Ordnung genannt – zeichnet sich gegenüber einer totalen Ordnung dadurch aus, dass die Totalität dahingehend abgeschwächt wird, dass jedes Element mindestens zu sich selbst in Relation steht (Reflexivität). Es ist also eine reflexive, antisymmetrische und transitive Relation, bei der also

für alle  erfüllt sind. Die Umkehrrelation einer Halbordnung
 
ist wiederum eine Halbordnung.

Halbordnungen können in Hasse-Diagrammen visualisiert werden. Eine Teilmenge einer halbgeordneten Menge heißt Oberhalbmenge, wenn sie zu jedem ihrer Elemente auch alle nachfolgenden Elemente (also alle, die rechts vom Relationssymbol stehen könnten) enthält.

Mit Hilfe des Auswahlaxioms kann man beweisen, dass jede Halbordnung in eine Totalordnung eingebettet werden kann. Für endliche Mengen muss man das Auswahlaxiom nicht voraussetzen, und in diesem Fall gibt es zur Konstruktion einer solchen Totalordnung auch explizite Algorithmen (siehe Topologische Sortierung).

Beispiele:

Jede Teilmengenbeziehung  auf einem System  von Mengen ist eine Halbordnung, denn sie ist
 transitiv, da die Teilmenge einer Teilmenge von  auch Teilmenge von  ist:
 für alle 
 reflexiv, da jede Menge eine Teilmenge ihrer selbst ist:
 für alle 
 und antisymmetrisch, da nur  selbst sowohl Teilmenge als auch Obermenge von  ist:
 für alle 

Weitere Beispiele:
 komponentenweise-kleiner-oder-gleich,  Für eine fest gewählte natürliche Zahl  und zwei Tupel aus einer Menge von  gilt:
 für jedes 
 Dies ist ein Spezialfall einer von einem Kegel induzierten Halbordnung, die zu dem Begriff der sogenannten verallgemeinerten Ungleichungen führt, die eine wichtige Rolle in der Optimierung spielen.
 Teilerbeziehung,  Für zwei natürliche Zahlen gilt:

Strenge Halbordnung 
So wie sich die strenge Totalordnung von der Totalordnung dadurch unterscheidet, dass Reflexivität und Antisymmetrie durch Irreflexivität ersetzt werden, so wird eine strenge Halbordnung durch Irreflexivität und Transitivität bestimmt. Wie bei der strengen Totalordnung fällt bei der strengen Halbordnung der Gleichheitsstrich in der Notation weg oder wird gar durch ein Ungleichzeichen ersetzt. Ein Beispiel ist die Relation „echte Teilmenge“ bei den Mengen.

Intervalle 
Mit einem Ordnungsbegriff  lässt sich der Begriff des Intervalls bilden.
Für  und  sei also

Die Begriffe „abgeschlossen“, „offen“, „rechts“ und „links“ stammen vom Fall  ab.

Man beachte, dass man im Fall einer Halbordnung wegen fehlender Totalität „oft“ leere Intervalle erhält (im Fall einer Quasiordnung „oft mehr“, etwa ganze Kreisscheiben oder Kugelschalen).

Im Zusammenhang mit gewissen Anwendungen eindimensionaler Intervalle können Konkretisierungen entsprechender Halbordnungen untersucht werden, die insbesondere in der englischsprachigen Literatur als Semiordnungen (Semiorder) und Intervallordnungen (Interval order) bezeichnet werden. Hierbei stehen die Aspekte überlappender Intervalle und gegebenenfalls vorliegender Intransitivität der Indifferenz im Mittelpunkt.

Weitere Anwendung der Halbordnung 
Um den Grad der Vorsortiertheit einer Menge zu messen, kann man die Anzahl der möglichen Fortsetzungen einer Halbordnung zu einer linearen Ordnung angeben. Ist beispielsweise die geordnete Menge  mit  und  gegeben, so gibt es drei mögliche Fortsetzungen: ,  und . Der Grad der Vorsortiertheit ist also in diesem Fall . Das Sortierverfahren Natural Mergesort nutzt vorsortierte Teilstücke für eine vollständige Sortierung der Menge.

Vorgänger und Nachfolger 

Sei  eine (schwache) totale (oder partielle) Ordnung auf der Menge . Für  mit

heißt  ein Vorgänger von , und  ein Nachfolger von . Wenn es kein  gibt, mit

dann heißt  der direkte (auch unmittelbare) Vorgänger von , und  der direkte (bzw. unmittelbare) Nachfolger von  

Für eine starke (gleichbedeutend: strikte) totale (oder partielle) Ordnung  auf  gilt formal ebenfalls die obige Definition (mit Notation  anstelle von   Die Kriterien können in diesem Fall jedoch wie folgt vereinfacht werden:

Sei  auf der Menge . Für  mit

heißt  ein Vorgänger von , und  ein Nachfolger von . Wenn es kein  gibt, mit
 (d. h. 

dann heißt  der direkte (auch unmittelbare) Vorgänger von  und  der direkte (bzw. unmittelbare) Nachfolger von .

Minimale, maximale und andere Elemente 
Sei  eine Teilmenge einer halbgeordneten Menge .

Wenn  die Eigenschaft hat, dass es kein  mit  gibt, dann heißt  minimales Element von . Falls es ein Element  gibt, das  für alle Elemente  erfüllt, dann heißt  das kleinste Element von . Ein kleinstes Element von  (wenn es das gibt; z. B. hat die Menge der ganzen Zahlen kein kleinstes Element) ist immer eindeutig bestimmt (wegen der Antisymmetrie) und natürlich auch minimal. In einer Totalordnung bedeuten „kleinstes Element“ und „minimales Element“ dasselbe, aber in allgemeinen Halbordnungen kann eine Menge mehrere minimale Elemente haben, von denen dann keines das kleinste ist.

Es kann sogar vorkommen, dass eine (unendliche) Menge  zwar ein einziges minimales Element hat, dieses aber nicht das kleinste Element der Menge ist (dann hat  kein kleinstes Element). Beispiel:
 In , versehen mit  als Halbordnung, ist  ein minimales Element, sogar das einzige, aber nicht das kleinste, da  nicht für alle  gilt.

Wenn  eine Teilmenge von  ist und  die Eigenschaft hat, dass für alle  die Beziehung  gilt, dann heißt  eine untere Schranke von . ( kann, muss aber nicht Element von  sein.) Wenn es eine größte untere Schranke der Menge  gibt, dann nennt man diese auch die untere Grenze oder das Infimum von . Eine untere Schranke ist also kleiner als das oder gleich dem Infimum.

Analog sind die Begriffe maximales Element, größtes Element, obere Schranke und obere Grenze bzw. Supremum definiert.

Eine Menge, die sowohl eine obere als auch eine untere Schranke hat, heißt beschränkt. (Analog sind „nach oben beschränkt“ und „nach unten beschränkt“ definiert.)

Man nennt eine Funktion , die eine beliebige Menge  in eine halb- oder total geordnete Menge (siehe unten)  abbildet, beschränkt, wenn die Menge der Funktionswerte beschränkt ist, also wenn es ein  und ein  gibt, sodass für alle 

gilt.

Lokal endliche Halbordnung 
Eine Halbordnung  heißt lokal endlich oder Kausalmenge (, kurz ), wenn jedes Intervall  eine endliche Menge ist. Die Kausalmengentheorie untersucht die Einbettung von Kausalmengen in Lorentzsche Mannigfaltigkeiten (ohne geschlossene Weltlinien) und ist ein Modell für eine Quanten­gravitations­theorie.

Striktordnung 
Eine strenge Ordnung oder Striktordnung ist transitiv und asymmetrisch. Der Begriff Asymmetrie fasst die Begriffe Irreflexivität und Antisymmetrie zusammen. Irreflexivität unterscheidet die Striktordnung von der Halbordnung und bedeutet, dass kein Element zu sich selbst in Beziehung steht. Eine Striktordnung ist also transitiv, irreflexiv und antisymmetrisch.

Beispiele:
 Die Relation „(echt) kleiner“ auf 
 die Relation „Echte Teilmenge“ in einer Potenzmenge
 die Relation „komponentenweise kleiner, aber nicht gleich“ auf dem Vektorraum .

Strenge schwache Ordnung 
Eine strenge schwache Ordnung R ist eine Striktordnung, bei der zusätzlich negative Transitivität gilt:

Eine strenge schwache Ordnung ist einer totalen Quasiordnung komplementär und umgekehrt.

Zusammensetzung von Ordnungen

Kreuzprodukt 
Sind  und  streng geordnete Mengen, dann lässt sich auf  die (ebenfalls strenge) Ordnungsrelation

definieren.

Ist  und , dann ist
 .    Aber die Paare
 
 und     sind unter der Ordnungsrelation  nicht vergleichbar.    Jedoch ist
     gleichwertig zu  und vergleichbar.

Das bedeutet insgesamt, dass eine evtl. Totalität von  und  beim Kreuzprodukt verloren geht.

Mehrdimensionale Intervalle 
Hat man eine geordnete Menge , dann lässt sich die Ordnungsrelation nach dem oben definierten Schema für „komponentenweise-kleiner-oder-gleich“ immer auf die mehrdimensionale Menge  erweitern, da die Transitivität der Relation  durch das Hinzufügen weiterer Komponenten von  nicht verloren geht.

Allerdings geht Totalität verloren.
Und ist  nicht antisymmetrisch, dann ist es  auch nicht.

Mit dem mehrdimensionalen Ordnungsbegriff  lässt sich der Begriff des Intervalls für Halbordnungen (wie auch für Quasiordnungen) vom Eindimensionalen auf  Dimensionen erweitern.
Für  und  sei also

Es gibt jedoch auch mehrdimensionale Intervalle, deren Verhalten an den Rändern sich nicht bei den genannten einordnen lassen, z. B.
,
wo bei der ersten Komponente  der Rand dabei ist, bei der zweiten  aber nicht.

Induktive Ordnung 
Eine halbgeordnete Menge  heißt induktiv geordnet, wenn jede linear geordnete Teilmenge von  eine obere Schranke besitzt. Sie heißt streng induktiv geordnet, wenn jede linear geordnete Teilmenge eine kleinste obere Schranke besitzt.

Nach dem Lemma von Zorn besitzt jede induktiv geordnete Menge ein maximales Element.

Fundierte Ordnung 
Eine fundierte Ordnung ist eine Halbordnung, in der es keine unendlichen, echt absteigenden Ketten gibt (oder, äquivalent formuliert: bei der jede nichtleere Teilmenge ein minimales Element besitzt). Beispiel: Die Teilbarkeitsbeziehung | zwischen natürlichen Zahlen.

Wohlquasiordnung 
Eine Wohlquasiordnung ist eine Quasiordnung mit der Eigenschaft, dass es zu jeder Folge  zwei natürliche Zahlen  gibt, so dass  gilt.

Wohlordnung 
Eine Wohlordnung ist eine totale Ordnung, bei der jede nichtleere Teilmenge ein kleinstes Element besitzt. Einige Beispiele:
 „Kleinergleich“ auf den natürlichen Zahlen .
 Die ganzen Zahlen  mit der Ordnung 
 Die ganzen Zahlen  mit der Ordnung 
Der Wohlordnungssatz garantiert die Existenz einer Wohlordnung für jede Menge, zum Beispiel auch für die reellen Zahlen . Er ist zum Auswahlaxiom äquivalent.

Baum 

Ein Baum ist eine Halbordnung , bei der für jedes  die Menge  der Vorgänger von  wohlgeordnet ist.

Verbandsordnung 
Eine Verbandsordnung ist eine Halbordnung, in der es zu je zwei Elementen  und  immer ein Supremum  und ein Infimum  gibt.

Durch jede Verbandsordnung ist die algebraische Struktur eines Verbandes gegeben, indem man für je zwei Elemente  und  definiert:
 
 

Umgekehrt lässt sich in jedem Verband durch
 
für je zwei Elemente  und  eine Verbandsordnung definieren, so dass
 
 

Eine verbandsgeordnete Menge wird daher oft „Verband“ genannt, sie selbst ist jedoch im Gegensatz zum Verband keine algebraische Struktur.

Vollständige Halbordnung 
Eine vollständige Halbordnung (engl. pointed complete partial order, dcpo, cppo, auch cpo) ist eine Halbordnung mit einem kleinsten Element und der Eigenschaft, dass jede Teilmenge, die eine aufsteigende Kette  bildet, ein Supremum besitzt. Das Supremum muss dabei nicht in der Teilmenge selbst liegen.

Bei einer gerichteten vollständigen Halbordnung (engl. directed complete partial order, DCPO) muss im Gegensatz zur vollständigen Halbordnung die leere Menge kein Supremum besitzen. Es muss damit kein kleinstes Element geben.

Diese beiden Vollständigkeitsbegriffe spielen eine Rolle bei Beweisen mit Hilfe des Lemmas von Zorn. → Davon zu unterscheiden ist der an die Topologie angelehnte Begriff Ordnungsvollständigkeit.

Konstruktion neuer Ordnungen 
Aus vorhandenen Ordnungen lassen sich auf sehr unterschiedliche Weise neue Ordnungen konstruieren.

Verkettung 
Ähnlich den Zeichenketten lassen sich zwei geordnete Mengen zu einer dritten geordneten Menge verketten (englisch: ordinal sum).
Dabei ist für zwei geordnete Mengen  und 
 die Menge 
die geordnete Menge, die die disjunkte Vereinigungsmenge  zur Grundmenge hat und mit der („vereinigten“) Ordnungsrelation  ausgestattet ist, die für  und  deren Ordnung in  resp.  als  resp.  fortsetzt und zusätzlich für  die durch die Reihenfolge der Operanden (zuerst  dann  in ) spezifizierte Ordnung  festlegt.Die so definierte Relation  ist wieder eine Ordnung, die total ist, wenn die Ausgangsordnungen total sind.Es existieren auch die abgekürzten Schreibweisen  oder  – oder (bei ausreichendem anderweitigem Kontext) gar nur .

Das Konzept lässt sich auf beliebige geordnete Indexmengen und damit gebildete disjunkte Vereinigungsmengen erweitern.

Ordnungen auf dem kartesischen Produkt 

Im kartesischen Produkt  zweier geordneter Mengen  und  lassen sich bilden:
 die Lexikographische Ordnung:    ist total, wenn die Ausgangsmengen total geordnet sind;
 die Produktordnung (englisch: product order):    ist nicht total.

Die so konstruierten Ordnungen können auf kartesische Produkte von mehr als 2 Mengen erweitert werden. Die Erweiterungsoperation erweist sich dabei als assoziativ.

Ordnungstheoretischer Stetigkeitsbegriff 
Ordnungstheoretisch lässt sich die Stetigkeit als Verträglichkeit einer Funktion mit dem Supremum vollständiger Halbordnungen  fassen.
Eine Funktion  heißt stetig, wenn  für alle gerichteten Teilmengen  gilt. Dieser Begriff spielt in der Bereichstheorie eine zentrale Rolle. Ähnlich der Folgenstetigkeit oben werden auch hier Grenzwerte wieder auf Grenzwerte abgebildet.

In diesem Zusammenhang folgt aus der Stetigkeit einer Funktion deren Monotonie. Umgekehrt bildet jede monotone Funktion eine gerichtete Menge wieder auf eine solche ab, wodurch die Existenz des Supremums des Abbilds dann von vornherein gewiss ist und nicht mehr gezeigt werden muss. Viele Autoren nehmen die Monotonie als Voraussetzung in die Definition der Stetigkeit auf.

Homomorphismen 
Seien  und  geordnete Mengen. Eine Abbildung  heißt isoton, ordnungserhaltend, ordnungstreu oder Ordnungshomomorphismus, wenn  für alle  gilt.

Verwendung der Begriffe 
Die Autoren benutzen den Begriff „Ordnung“ unterschiedlich. Er kann eine Halbordnung oder eine totale Ordnung bezeichnen. Vermutlich induziert von den Polaritäten „halb“ und „total“, findet man somit häufig die Abgrenzung
 Ordnung (im Sinn von Halbordnung)  totale Ordnung
oder auch
 Halbordnung  Ordnung (im Sinn von totale Ordnung).

Siehe auch 
 Eine Ordnungsrelation auf einer Menge von Güterbündeln heißt in der Mikroökonomie Präferenzrelation.
 In der Algebra werden (meist totale) Ordnungsrelationen auf einer Menge betrachtet, die mit der Verknüpfung bzw. den Verknüpfungen auf dieser Menge verträglich sind. Siehe als Beispiel Geordneter Körper.
 In der Geometrie lassen sich unter bestimmten Bedingungen Anordnungen der Punkte auf jeder Geraden einführen. Man spricht hier zunächst von Zwischenrelationen (dies sind dreistellige Relationen), aus denen sich in wichtigen Spezialfällen totale, miteinander und mit der geometrischen Struktur verträgliche Ordnungen auf diesen Punktreihen ergeben.
 Jede totalgeordnete Menge lässt sich mit einer durch die Ordnung bestimmten topologischen Struktur, der Ordnungstopologie ausstatten.
 Lexikographische Ordnung

Literatur 
 Rudolf Berghammer: Ordnungen, Verbände und Relationen mit Anwendungen. 2., durchgesehene und korrigierte Auflage. Springer Vieweg, Wiesbaden 2012, ISBN 978-3-658-00618-1.
 Marcel Erné: Einführung in die Ordnungstheorie. Bibliographisches Institut, Mannheim u. a. 1982, ISBN 3-411-01638-8.
 Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen. Springer Spektrum, Berlin/ Heidelberg 2013, ISBN 978-3-642-37499-9.
 Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Bd. 7). Springer, New York NY 2005, ISBN 0-387-24219-8.
 Ingmar Lehmann, Wolfgang Schulz: Mengen – Relationen – Funktionen. Eine anschauliche Einführung. 3., überarbeitete und erweiterte Auflage. Teubner, Wiesbaden 2007, ISBN 978-3-8351-0162-3.
 Wiebke Petersen: Mathematische Grundlagen der Computerlinguistik – Ordnungsrelationen, 4. Foliensatz, Heinrich-Heine-Universität Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 WS 2013/14, abgerufen am 21. April 2018.

Weblinks 

 Ordnungsrelation im Lexikon der Mathematik auf Spektrum.de

Einzelnachweise 

!
Ordnungstheorie
Mathematischer Grundbegriff