Ordnungsrelation

Grundidee und Notation

Ordnungsrelationen verallgemeinern in der Mathematik die Beziehung „kleiner-gleich“. Sie dienen dazu, Elemente einer Menge zu vergleichen. Formal ist eine Ordnungsrelation eine zweistellige Relation R⊆M×M auf einer Trägermenge M; Transitivität gehört stets zu ihren Eigenschaften. Das Paar (M,R) heißt geordnete Menge.

Für (a,b)∈R schreibt man meist a R b. Statt R werden häufig ≤ oder ≼ verwendet. Die strengen Schreibweisen sind Abkürzungen: a<b bedeutet „a≤b und a≠b“, a≺b entsprechend „a≼b und a≠b“.

Totale, strenge und Quasiordnungen

Eine (schwache) Totalordnung ≤ auf M ist reflexiv, antisymmetrisch, transitiv und total. Für alle x,y,z∈M gilt also: x≤x; aus x≤y und y≤x folgt x=y; aus x≤y und y≤z folgt x≤z; außerdem gilt immer x≤y oder y≤x. Weil alle Elemente wie auf einer Linie vergleichbar sind, heißt sie auch lineare Ordnung. Eine totalgeordnete Teilmenge einer partiell geordneten Menge heißt Kette.

Die Umkehrrelation ist ebenfalls total geordnet: x≥y genau dann, wenn y≤x. Endliche Teilmengen einer totalgeordneten Menge lassen sich eindeutig aufsteigend sortieren; bei absteigender Sortierung gilt zwischen Nachbarelementen die umgekehrte Relation. Beispiele sind ≤ auf ℤ und die lexikographische Ordnung von Tupeln. Die Teilmengenrelation ⊆ auf der Potenzmenge von ℤ ist dagegen nicht total: Weder {1,2}⊆{2,3} noch {2,3}⊆{1,2} gilt.

Eine strenge Totalordnung < ist transitiv und erfüllt die Trichotomie: Genau eine der Beziehungen x<y, x=y oder y<x gilt. Aus ihr entsteht die schwache Ordnung durch x≤y genau dann, wenn x<y oder x=y; umgekehrt gilt x<y genau dann, wenn x≤y und x≠y. Vergleichbar heißen zwei Elemente genau dann, wenn eine dieser drei Beziehungen gilt.

Eine Quasiordnung ist nur reflexiv und transitiv. Für komplexe Zahlen kann a≤b durch |a|≤|b| definiert werden. Diese Relation ist total, aber nicht antisymmetrisch, weil Zahlen mit gleichem Betrag verschieden sein können.

Halbordnungen und wichtige Elemente

Eine Halbordnung, auch Partial- oder Teilordnung, ist reflexiv, antisymmetrisch und transitiv, aber im Allgemeinen nicht total. Nicht jedes Paar von Elementen muss daher vergleichbar sein. Die Umkehrrelation einer Halbordnung ist wieder eine Halbordnung; Hasse-Diagramme können Halbordnungen darstellen. Eine Oberhalbmenge enthält mit jedem ihrer Elemente auch alle nachfolgenden Elemente.

Die Teilmengenrelation ⊆ ist eine Halbordnung: A⊆A, aus A⊆B⊆C folgt A⊆C, und aus A⊆B sowie B⊆A folgt A=B. Weitere Beispiele sind die komponentenweise Ordnung von n-Tupeln, die Teilt-Relation auf ℕ₀ mit a∣b genau dann, wenn ein k∈ℕ₀ mit a·k=b existiert, sowie stochastische und Pareto-Ordnung. Die Relation „echte Teilmenge“ ist eine strenge Halbordnung; diese ist irreflexiv und transitiv.

Mit dem Auswahlaxiom lässt sich jede Halbordnung in eine Totalordnung einbetten. Für endliche Mengen ist kein Auswahlaxiom nötig; explizite Verfahren dafür sind topologische Sortierungen. Die Zahl möglicher Fortsetzungen zu linearen Ordnungen misst die Vorsortiertheit: Für X={a,b,c} mit a≤b gibt es genau drei Fortsetzungen, nämlich a≤b≤c, a≤c≤b und c≤a≤b; daher e(≤)=3. Natural Mergesort nutzt vorsortierte Teilstücke.

Für x≤z mit x≠z heißt x Vorgänger von z und z Nachfolger von x. Es sind direkte Vorgänger beziehungsweise Nachfolger, wenn kein y mit x<y<z existiert. In einer Teilmenge T einer halbgeordneten Menge ist m minimal, wenn kein x∈T mit x<m existiert. Ein kleinstes Element m erfüllt dagegen m≤x für alle x∈T. Ein kleinstes Element ist eindeutig und minimal; in einer Halbordnung können aber mehrere minimale Elemente existieren, ohne dass es ein kleinstes gibt.

Eine untere Schranke p von T erfüllt p≤t für alle t∈T. Die größte untere Schranke heißt Infimum oder untere Grenze. Analog gibt es maximale und größte Elemente, obere Schranken und das Supremum. Eine Menge ist beschränkt, wenn sie eine obere und eine untere Schranke besitzt. Eine Funktion f:X→P ist beschränkt, wenn p≤f(x)≤q für alle x∈X und geeignete p,q∈P gilt.

Intervalle und besondere Ordnungen

Eine Ordnung definiert Intervalle. Für a,b∈M gilt [a,b]={x∈M | a≤x≤b}, (a,b)={x∈M | a<x<b}, [a,b)={x∈M | a≤x<b} und (a,b]={x∈M | a<x≤b}. Unbeschränkte Varianten sind etwa [a,∞)={x∈M | a≤x} und (-∞,b]={x∈M | x≤b}. Die Wörter offen, abgeschlossen, rechts und links stammen vom Fall M=ℝ. Bei Halbordnungen entstehen wegen fehlender Totalität oft leere Intervalle; bei Quasiordnungen können sie größer sein, etwa ganze Kreisscheiben oder Kugelschalen.

Eine lokal endliche Halbordnung oder Kausalmenge ist eine Halbordnung, in der jedes Intervall [x,y]={z∈M:x≤z≤y} endlich ist. Kausalmengentheorie untersucht ihre Einbettung in Lorentzsche Mannigfaltigkeiten ohne geschlossene Weltlinien und ist ein Modell für eine Quantengravitationstheorie.

Induktiv geordnet heißt eine halbgeordnete Menge, wenn jede linear geordnete Teilmenge eine obere Schranke besitzt; streng induktiv geordnet heißt sie, wenn jede solche Teilmenge eine kleinste obere Schranke hat. Nach dem Lemma von Zorn besitzt jede induktiv geordnete Menge ein maximales Element. Fundierte Ordnungen sind Halbordnungen ohne unendliche echt absteigende Ketten; gleichwertig besitzt jede nichtleere Teilmenge ein minimales Element. Die Teilbarkeitsbeziehung zwischen natürlichen Zahlen ist ein Beispiel.

Eine Wohlquasiordnung verlangt für jede Folge (p₁,p₂,p₃,…) natürliche Zahlen k<n mit pₖ≤pₙ. Eine Wohlordnung ist eine Totalordnung, in der jede nichtleere Teilmenge ein kleinstes Element hat. Beispiele sind ≤ auf ℕ sowie die Ordnungen 0<1<-1<2<-2<3<-3<… und 0<1<2<3<…<-1<-2<-3<… auf ℤ. Der Wohlordnungssatz garantiert für jede Menge, auch ℝ, eine Wohlordnung und ist zum Auswahlaxiom äquivalent. Ein Baum ist eine Halbordnung (T,<), bei der die Vorgängermenge {y | y<x} jedes x∈T wohlgeordnet ist.

In einer Verbandsordnung besitzen je zwei Elemente v,w sowohl sup(v,w) als auch inf(v,w). Mit v∨w:=sup(v,w) und v∧w:=inf(v,w) entsteht ein Verband. Umgekehrt wird in jedem Verband durch v≤w genau dann, wenn v∨w=w, eine solche Ordnung bestimmt. Eine vollständige Halbordnung besitzt ein kleinstes Element und für jede aufsteigende Kette (x₀≤x₁≤x₂≤…) ein Supremum. Bei einer gerichteten vollständigen Halbordnung (DCPO) muss die leere Menge kein Supremum haben; ein kleinstes Element ist dann nicht erforderlich.

Zusammensetzen und Abbilden von Ordnungen

Eine strenge schwache Ordnung ist eine Striktordnung mit negativer Transitivität: ¬aRb und ¬bRc ⇒ ¬aRc. Sie ist genau dann komplementär zu einer totalen Quasiordnung, wenn umgekehrt diese totale Quasiordnung vorliegt.

Bei der Verkettung zweier geordneter Mengen (A,<A) und (B,<B) bildet die disjunkte Vereinigung A⊔B eine neue geordnete Menge. Die bisherigen Ordnungen bleiben erhalten, und zusätzlich gilt für jedes a∈A und b∈B: a<∪b. Die neue Ordnung ist total, wenn beide Ausgangsordnungen total sind; das Konzept lässt sich auf beliebige geordnete Indexmengen erweitern.

Auf A×B ist die lexikographische Ordnung durch (a₁,b₁)<(a₂,b₂) genau dann definiert, wenn a₁<a₂ oder a₁=a₂ und b₁<b₂. Sie ist bei total geordneten Ausgangsmengen total. Die Produktordnung lautet (a₁,b₁)≤(a₂,b₂) genau dann, wenn a₁≤a₂ und b₁≤b₂; sie ist im Allgemeinen nicht total. Ebenso verliert die komponentenweise Ordnung ≤ⁿ auf Mⁿ im Allgemeinen die Totalität, auch wenn ≤ total ist. Mehrdimensionale Intervalle werden entsprechend mit a≤ⁿx≤ⁿb definiert; an verschiedenen Komponenten können Ränder unterschiedlich einbezogen sein.

Ordnungstheoretische Stetigkeit für vollständige Halbordnungen A,B bedeutet für jede gerichtete Teilmenge X⊆A: f(⨆X)=⨆f(X). Stetigkeit impliziert Monotonie; viele Autoren verlangen Monotonie bereits in der Definition. Eine Abbildung φ:X→X′ zwischen geordneten Mengen heißt isoton, ordnungserhaltend oder Ordnungshomomorphismus, wenn aus xRy stets φ(x)R′φ(y) folgt.

Der Begriff „Ordnung“ wird nicht einheitlich verwendet: Je nach Autor bezeichnet er eine Halbordnung oder eine totale Ordnung.