1.3 Ordnungen
Definition (partielle und lineare Ordnungen)
Partielle und lineare Ordnung
Eine Relation ≤ auf A heißt eine (partielle) Ordnung auf A, falls ≤ reflexiv, antisymmetrisch und transitiv auf A ist. Für alle a, b ∈ A setzen wir a < b, falls a ≤ b und a ≠ b.
Sind a, b ∈ A mit a ≤ b oder b ≤ a, so heißen a und b vergleichbar. Sind je zwei Elemente vergleichbar, so heißt die Ordnung ≤ linear oder total.
Ordnungsbegriffe
Seien ≤ eine partielle Ordnung auf A, a ∈ A und X ⊆ A.
a heißt … | in Zeichen | falls … |
obere Schranke von X | X ≤ a, a ≥ X | für alle x ∈ X gilt x ≤ a |
untere Schranke von X | a ≤ X, X ≥ a | für alle x ∈ X gilt a ≤ x |
Maximum von X | a = max(X) | a ∈ X und X ≤ a |
Minimum von X | a = min(X) | a ∈ X und a ≤ X |
Supremum von X | a = sup(X) | X ≤ a und für alle b ≥ X gilt a ≤ b |
Infimum von X | a = inf (X) | a ≤ X und für alle b ≤ X gilt b ≤ a |
maximal in X | − | a ∈ X und es gibt kein x ∈ X mit a < x |
minimal in X | − | a ∈ X und es gibt kein x ∈ X mit x < a |
Die Inklusion ⊆ ist eine partielle Ordnung auf
A = ℘({ 1, 2, 3 }) =
{ { }, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 }}.
Sie lässt sich durch ein sog. Hasse-Diagramm darstellen: Die Ordnung wird durch Linien angezeigt, wobei größere Elemente über kleineren stehen. In der Ordnung ist { 1 } kleiner als { 1, 2, 3 }, während { 1 } und { 2, 3 } unvergleichbar sind. Auch viele Ordnungen auf unendlichen Mengen kann man in verwandter Weise visualisieren, man denke etwa an Zahlenstrahldarstellungen von ℕ, ℤ, ℚ oder ℝ.
Wir betrachten die durch das Hasse-Diagramm links dargestellte partielle Ordnung ≤ auf
A = { 1, 2, 3, 4, 5, 6 }
und die Teilmenge X = { 2, 3, 4 } von A. Es gilt:
(a) | 5 ist eine obere Schranke von X, 6 ist keine obere Schranke von X, |
(b) | 1 und 2 sind untere Schranken von X, |
(c) | 2 = min(X), max(X) existiert nicht, |
(d) | 3 und 4 sind maximal in X, 2 ist minimal in X. |
Im Gegensatz zu einer Äquivalenzrelation, die eine Menge A in disjunkte Äquivalenzklassen unterteilt, bringt eine partielle Ordnung die Elemente von A in eine netzartige Struktur. Ist die Ordnung linear (total), so wird A in die Form einer „Kette“ oder abstrakten „Linie“ gebracht.
Ist ≤ eine partielle Ordnung auf A, so ist die zugehörige Relation < irreflexiv und transitiv (und damit antisymmetrisch). Eine irreflexive und transitive Relation auf A nennt man auch eine strikte partielle Ordnung auf A. Ist < eine strikte partielle Ordnung auf A, so erhält man eine partielle Ordnung ≤ auf A durch
a ≤ b, falls a < b oder a = b für alle a, b ∈ A.
Es ist also Geschmackssache, ob man ≤ oder < bevorzugt. Man hat immer beides.
Für partielle Ordnungen werden meistens Zeichen wie ≤, ≼, ≤* mit Unterstrich und die zugehörigen strikten Versionen <, ≺, <* verwendet.
Beispiele
(1) | Die üblichen ≤-Relationen auf ℕ, ℤ, ℚ und ℝ sind lineare Ordnungen. |
(2) | Ist ≤ eine lineare Ordnung auf A, so definiert (a, b) ≤lex (c, d), falls a ≤ c oder (a = c und b ≤ d) eine lineare Ordnung auf A2, die sog. lexikographische Ordnung auf A2. Speziell kann die Menge ℝ2 = ℂ in dieser Weise linear geordnet werden. |
(3) | Für jede Menge M ist die Inklusion ⊆ eine partielle Ordnung auf A = ℘(M). Sind a, b ∈ M verschieden, so sind { a } und { b } nicht vergleichbar. Für alle 𝒜 ⊆ ℘(M) gilt sup(𝒜) = ⋃𝒜 und inf (𝒜) = ⋂𝒜. |
(4) | Die Anfangsstückrelation auf der Menge der endlichen 01-Folgen ist eine baumartige partielle Ordnung. Es gilt zum Beispiel 010 ≤ 01011, nicht(010 ≤ 11101). Die Ordnung hat keine maximalen Elemente, da s ≤ s0 (und s ≤ s1) für alle s gilt. |