Ordnungen

 Neben den Äquivalenzrelationen gehören die Ordnungen zu den wichtigsten Relationen. Auch diese sind uns durch den Alltag sehr vertraut: Wir sprechen in den verschiedensten Situationen von „besser“ und „schlechter“, von „schneller“ und „langsamer“, von „größer“ und „kleiner“. Wir unterliegen dabei leider oft einem Bedürfnis, je zwei Objekte miteinander vergleichen zu wollen. Natürlicher ist in vielen Fällen ein „partieller“ Ansatz, der zwei vorliegende Dinge nur manchmal miteinander vergleicht und andernfalls gar keine Aussage trifft. Diese Ordnungsidee können wir mathematisch wieder durch eine Kombination von Eigenschaften einer Relation einfangen:

Ausformuliert gilt also für alle a, b, c  ∈  A:

a ≤ a,  a ≤ b ∧ b ≤ a  impliziert  a = b,  a ≤ b ≤ c  impliziert  a ≤ c.

 Das bevorzugte Zeichen für partielle Ordnungen ist ≤, zusammen mit verwandten Symbolen wie ≼, ≤*, usw.

 Stillschweigend wird für eine partielle Ordnung ≤ immer definiert:

a  <  b,  falls  a  ≤  b  und  a ≠ b   für alle a, b  ∈  A.

Die Relation < ist irreflexiv und transitiv auf A. Eine irreflexive und transitive Relation heißt eine partielle Ordnung (vom strikten Typ). Ist < eine strikte partielle Ordnung auf A, so definieren wir

a  ≤  b,  falls  a  <  b  oder  a = b   für alle a, b  ∈  A.

Dann ist die Relation ≤ eine partielle Ordnung auf A vom nicht strikten Typus.

 Wir haben also immer partielle Ordnungen beider Typen vorliegen. Die Zeichen ≤, ≼, ≤*, … stehen immer für nichtstrikte Typen, die zugehörigen Zeichen <, ≺, <*, … für die strikten Versionen.

 Nichtstrikte partielle Ordnungen unterscheiden sich von den Äquivalenzrelationen „nur“ durch den Austausch der Bedingungen „symmetrisch“ und „antisymmetrisch“. Dieser Austausch führt zu einer vollkommen anderen Welt. Partielle Ordnungen zerlegen eine Menge nicht in Teilgebiete, sondern sie ordnen die Elemente der Menge in einer netzartigen Struktur an. Diese Struktur kann man für endliche Mengen A mit Hilfe von Diagrammen sehr anschaulich machen: Wir zeichnen die Elemente von A als benannte Punkte und verbinden zwei Punkte a < b genau dann mit einem Pfeil, wenn es kein c gibt mit a < c < b. Dieser Zusatz führt zu übersichtlichen Diagrammen, die nicht mit Transitivitätspfeilen überladen sind. Weiter kann man statt der Pfeile auch einfache Verbindungslinien einzeichnen, wenn man vereinbart, dass Punkte, die weiter oben stehen, größer sind als Elemente, die weiter unten stehen.

 So gilt im Diagramm rechts:

a  <  c  <  f,  a  <  d  <  g, 

a  <  e  <  f,  a  <  e  <  g, 

b  <  e  <  f,  b  <  e  <  g. 

Darüber hinaus gelten keine weiteren Relationen, so gilt z. B. weder a < b noch d < f.

 Zur Beschreibung der Struktur einer partiellen Ordnung führen wir die folgenden Begriffe ein:

 In der partiellen Ordnung des obigen Diagramms sind zum Beispiel a und g vergleichbar, a und b sind dagegen unvergleichbar. Die Menge { a, d, g } ist eine maximale Kette und die Menge { c, d, e } eine maximale Antikette der Ordnung.

 Weiter zeichnen wir noch gewisse Elemente von partiellen Ordnungen aus:

 Im obigen Diagramm sind a und b die minimalen Elemente und f und g die maximalen Elemente der Ordnung. Die Ordnung hat weder ein größtes noch ein kleinstes Element.

 Die Inklusion liefert die wichtigsten Beispiele für partielle Ordnungen. Für jedes Mengensystem 𝒜 auf einer Menge A ist die Teilmengenrelation ⊆ eine partielle Ordnung auf 𝒜, und die echte Inklusion ⊂ ist die zugehörige strikte Version.

 Einen schärferen Begriff als die partiellen Ordnungen bilden die so genannten linearen Ordnungen.

Für eine lineare Ordnung ≤ (oder <) auf A gilt also:

∀a, b  ∈  A (a ≤ b  ∨  b ≤ a). (Vergleichbarkeitsbedingung)

 Die Elemente von A werden in einer linearen Ordnung nicht mehr netzartig, sondern in einer abstrakten „Reihe“ oder „Linie“ angeordnet. In waagrechten Diagrammen vereinbaren wir dann, dass die Elemente von links nach rechts „wachsen“. So gilt a < b < c < d in der wie folgt visualisierten Ordnung: