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 Trägermenge mit bestimmten unten aufgeführten Eigenschaften, worunter immer die Transitivität ist. Die Menge wird bei manchen Autoren auch als Trägermenge bezeichnet.

Ist auf einer Trägermenge eine solche Ordnungsrelation gegeben, so ist das Paar eine geordnete Menge. Meist wird für die sogenannte Infix-Notation verwendet. Außerdem wird für Ordnungsrelationen nur selten ein Symbol wie verwendet. Stattdessen werden häufig Symbole wie , oder ähnliche verwendet. Die Schreibweisen und stehen als Abkürzung für „ und “ bzw. „ 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 (Reflexivität) (Antisymmetrie) (Transitivität) (Totalität) für alle erfüllt sind. Da dies bei der Zahlengeraden, der „Linie“, der Fall ist, wird eine Totalordnung auch lineare Ordnung genannt. Eine totalgeordnete Untermenge einer partiell geordneten Menge wird auch als Kette bezeichnet.

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 oder die lexikographische Ordnung über Tupeln.

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 (Transitivität) entweder oder oder (Trichotomie) 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, partielle Ordnung oder Teilordnung genannt – ist eine reflexive, antisymmetrische und transitive Relation. Sie ist im Allgemeinen nicht total, d. h. nicht jedes Element steht notwendigerweise in Relation zu allen anderen Elementen.In der englischsprachigen Fachliteratur bezeichnet man eine halbgeordnete Menge in der Regel als partially ordered set oder kurz als poset.

Eine Halbordnung erfüllt somit für alle : (Reflexivität) (Antisymmetrie) (Transitivität) Eine Menge , auf der eine Halbordnung definiert ist, wird halbgeordnete Menge genannt. 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:

Die Teilmengenbeziehung auf einem Mengensystem ist eine Halbordnung, denn sie ist transitiv, da jede 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, Manchmal auch ohne Exponent , also oder einfach geschrieben. 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. Die Teilt-Relation in der Menge erklärt etwa durch

Stochastische Ordnung Pareto-Ordnung

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.interval. Auf: nLab. Stand: 30. Dezember 2020. Für und sei also abgeschlossenes Intervall:offenes Intervall:halboffenes (genauer rechtsoffenes) Intervall:halboffenes (genauer linksoffenes) Intervall:rechtsseitig unendliches abgeschlossenes Intervall:rechtsseitig unendliches offenes Intervall:linksseitig unendliches abgeschlossenes Intervall:linksseitig unendliches offenes Intervall:beidseitig unendliches offenes (und zugleich abgeschlossenes) Intervall:     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  W. Petersen WS 2001/12 S. 93, WS 2013/14 S. 90. Die Begriffe werden oft auch für andere Relationen anstelle der hier aufgeführten (schwachen bzw. starken ) (Teil-)Ordnungsrelationen verwendet.Achtung: Manche Autoren bezeichnen nur die unmittelbaren (d. h. direkten) Vorgänger (bzw. Nachfolger) als Vorgänger (respektive Nachfolger).Was oben als Vorgänger/Nachfolger definiert ist, wäre dann ein Vorgänger bzw. Nachfolger im weiteren Sinn. Ein solcher muss aber nicht zwangsläufig über eine Sequenz direkter (d. h. unmittelbarer) Vorgänger bzw. Nachfolger (quasi indirekt oder mittelbar) erreichbar sein, z. B. 0 und 1 auf oder 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