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

Eine Ordnungsrelation ist formal eine zweistellige Relation

$R\; \backslash subseteq\; M\; \backslash times\; M$

auf einer Menge M mit bestimmten, unten bei "Halbordnung" genannten Eigenschaften.

Ist eine Menge M mit einer Ordnungsrelation R gegeben, dann nennt man das Paar (M, R) eine geordnete Menge. Statt a R b schreibt man meist (je nach Art der Ordnung) a ≤ b oder a < b.

Eine (totale) Ordnung auf einer Menge liefert eine Anordnung der Elemente in einer bestimmten Reihenfolge, z.B. die Anordnung der Buchstaben A bis Z im lateinischen Alphabet. Die Reihenfolge der Buchstaben ist willkürlich festgelegt, und jede andere Reihenfolge wäre ebenfalls eine Ordnung.

Arten von Ordnungsrelationen

---

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

Quasiordnung

Eine Quasiordnung ist reflexiv und transitiv.

Beispiel: Für komplexe Zahlen $a,\; b\backslash in\backslash Bbb\; C$ ist die über den Absolutbetrag durch "a R b falls |a| ≤ |b|" festgelegte Relation eine Quasiordnung: Es gilt die

• Reflexivität, denn |a| ≤ |a| und die
• Transitivität, denn wenn |a| ≤ |b| und |b| ≤ |c| ist, ist auch |a| ≤ |c|.

Diese Quasiordnung ist nicht antisymmetrisch, denn betragsgleiche Zahlen müssen nicht identisch sein.

Halbordnung

Eine partielle Ordnung, Halbordnung, Teilordnung oder Ordnungsrelation im engeren Sinne ist reflexiv, antisymmetrisch und transitiv. Beispielsweise ist die Teilmengenbeziehung eine Halbordnung, denn sie ist

• reflexiv, da jede Menge eine Teilmenge ihrer selbst ist,
• transitiv, da die Teilmenge einer Teilmenge von A auch Teilmenge von A ist,
• und antisymmetrisch, da nur A selbst sowohl Teilmenge als auch Obermenge von A ist.

Weiteres Beispiel ist die Relation "komponentenweise kleinergleich" auf dem Vektorraum $\backslash R^n$ oder die Teilerbeziehung in den natürlichen Zahlen.

= 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 (X, $\backslash leq$) mit $X\; =\; \backslash \{a,\; b,\; c\backslash \}$ und $a\; \backslash leq\; b$ gegeben, so gibt es drei mögliche Fortsetzungen: a $\backslash leq$ b $\backslash leq$ c, a $\backslash leq$ c $\backslash leq$ b und c $\backslash leq$ a $\backslash leq$ b. Der Grad der Vorsortiertheit ist also in diesem Fall e($\backslash leq$) = 3. Nach dem efficient comparison theorem werden für eine vollständige Sortierung der vorsortierten Menge dann nur noch $\backslash Omega(e(\backslash leq))$ Vergleiche benötigt. In der Informatik nutzt zum Beispiel das Sortierverfahren Mergesort diese Eigenschaft.

Striktordnung

Eine Striktordnung ist irreflexiv und transitiv. Sie unterscheidet sich von der Halbordnung dadurch, dass kein Element zu sich selbst in Beziehung steht. Eine Relation ist irreflexiv und transitiv genau dann, wenn sie asymmetrisch und transitiv ist. Damit ist eine Striktordnung auch asymmetrisch.

Beispiel: Die Relation "Echte Teilmenge" in einer Potenzmenge oder die Relation "komponentenweise kleiner, aber nicht gleich" auf dem Vektorraum $\backslash R^n$.

Totalordnung

Eine Totalordnung, lineare Ordnung oder auch Kette ist eine Halbordnung, die zudem eine totale Relation ist, d.h. dass für zwei Elemente a,b der Grundmenge stets aRb oder bRa erfüllt ist. Der Begriff linear orientiert sich an der Vorstellung, die ganze Menge in einer Kette ... R a1 R a2 R a3 R ... aufzuzählen.

Ein Beispiel ist die Relation $\backslash leq$ („kleinergleich“) auf den ganzen Zahlen $\backslash Z$. Gegenbeispiel ist z.B. die Teilmengenbeziehung auf $\backslash Z$: sie ist nicht total, weil für $a\backslash neq\; b$ weder $\backslash \{a\backslash \}\backslash subseteq\backslash \{b\backslash \}$ noch $\backslash \{b\backslash \}\backslash subseteq\backslash \{a\backslash \}$ gilt.

Strenge Totalordnung

Eine strenge Totalordnung ist trichotomisch, irreflexiv und transitiv. In Analogie zur strengen Halbordnung steht ein Element nicht in Beziehung zu sich selbst, beispiel "Kleiner" auf $\backslash Z$.

Die Irreflexivität folgt schon aus der Trichotomie. Damit sind die oben angegebenen Axiome zwar nicht mehr unabhängig, andererseits kann man so leichter erkennen, dass eine strenge Totalordnung eine trichotomische, strenge Halbordnung ist. Übrigens: Auch wenn der Begriff an sich einen anderen Schluss nahelegt - eine strenge Totalordnung ist wegen der Irreflexivität i.A. nicht total.

Mit Hilfe des Auswahlaxioms kann man beweisen, dass jede Halbordnung in eine Totalordnung eingebettet werden kann. Für endliche Mengen gibt es zur Konstruktion so einer Totalordnung auch explizite Algorithmen (AC wird hier natürlich nicht verwendet), siehe Topologische Sortierung.

Wohlordnung

Eine Wohlordnung ist eine totale Ordnung, bei der jede nichtleere Teilmenge ein kleinstes Element besitzt.

• Beispiel: "Kleinergleich" auf den natürlichen Zahlen $\backslash Bbb\; N$.
• Beispiel: Die ganzen Zahlen $\backslash Z$ mit der Ordnung 0 < 1 < -1 < 2 < -2 < 3 < -3 < ... .
• Beispiel: Die ganzen Zahlen $\backslash Z$ mit der Ordnung 0 < 1 < 2 < 3 < ... < -1 < -2 < -3 < ... .

Das so genannte Wohlordnungsprinzip garantiert die Existenz einer Wohlordnung für jede Menge, z.B. auch für die reellen Zahlen $\backslash R$. Das Wohlordnungsprinzip folgt aus dem Auswahlaxiom, ist ohne dieses aber nicht beweisbar.

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 (p₁, p₂, p₃, ...) zwei natürliche Zahlen k<n gibt, sodass p_k ≤ p_n gilt.

Verband

Ein Verband ist eine Halbordnung, in der es zu je zwei Elementen immer eine kleinste obere Schranke und eine größte untere Schranke gibt.

Man benutzt diese Schranken, um die Verknüpfungen des Verbandes zu definieren. Kleinste obere Schranke heißt auch Supremum, abgekürzt sup(v,w). Größte untere Schranke heißt auch Infimum, abgekürzt inf(v,w).
Verknüpfungen für zwei Elemente v und w werden dann definiert:

• v $\backslash cap$ w : = inf(v,w)
• v $\backslash cup$ w : = sup(v,w)

Vollständige Halbordnung

Eine vollständige Halbordnung (engl. complete partial order, CPO) ist eine partielle Ordnung mit einem kleinsten Element und der Eigenschaft, dass jede Teilmenge, die eine aufsteigende Kette (x₀ ≤ x₁ ≤ x₂ ≤ ...) bildet, ein Supremum besitzt. Das Supremum muss dabei nicht unbedingt in der Teilmenge selber liegen.

Eine gerichtete vollständige Halbordnung (engl. directed complete partial order, DCPO) besitzt im Gegensatz zur vollständigen Halbordnung kein kleinstes Element und die leere Menge wird als Teilmenge nicht beachtet.

Beachte: Verschiedene Autoren benutzen den Begriff "Ordnung" unterschiedlich. Er kann eine Halbordnung oder eine totale Ordnung bezeichnen. Man findet also oft entweder die Bezeichnungen

"Ordnung" (= Halbordnung) und "totale Ordnung"

oder die Bezeichnungen

"Halbordnung" und "Ordnung" (= totale Ordnung).

Minimale, maximale und andere Elemente

---

Sei T eine Teilmenge einer partiell geordneten Menge P. Falls es ein Element m in T gibt, das ≤ allen anderen Elementen von T ist, dann heißt m das kleinste Element von T.

Wenn m in T die Eigenschaft hat, dass es kein x in T mit x<m gibt, dann heißt m minimales Element von T. Ein kleinstes Element von T (wenn es das gibt; zB hat die Menge der ganzen Zahlen kein kleinstes Element) ist immer eindeutig bestimmt, und natürlich auch minimal. In einer Totalordnung bedeutet "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 T zwar ein einziges minimales Element hat, dieses aber nicht das kleinste Element der Menge ist. Siehe auch Minimum (Mathematik).

Wenn T eine Teilmenge von P ist, und p in P die Eigenschaft hat, dass für alle t in T die Beziehung p≤t gilt, dann heißt p eine untere Schranke von T. (p kann, muss aber nicht, Element von T sein.)

Wenn es eine größte untere Schranke der Menge T gibt, dann nennt man diese auch das Infimum von T. Jede untere Schranke ist also kleiner als oder gleich dem Infimum.

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

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

Man nennt eine Funktion f, die eine beliebige Menge X in eine partiell oder total geordnete Menge P abbildet, beschränkt, wenn die Menge der Funktionswerte beschränkt ist, also wenn es ein p und ein q in P gibt, sodass für alle x in X gilt: p ≤ f(x) ≤ q.

Ordnungstheorie

Partially ordered set | Conjunto parcialmente ordenado | Relation d'ordre | Relazione d'ordine | Relacija urejenosti | 偏序关系