1.12 Das Zornsche Lemma
Satz (Zornsches Lemma)
Sei ≤ eine partielle Ordnung auf A. Es gelte:
(#) Ist B ⊆ A linear geordnet durch ≤, so existiert eine obere Schranke von B. (Kettenbedingung)
Dann existiert ein maximales Element der Ordnung. Genauer existiert für alle a0 ∈ A ein maximales Element b in A mit a0 ≤ b.
Illustration der Kettenbedingung (#): Die Kette B der partiellen Ordnung hat die obere Schranke s.
Eine Teilmenge B von A wird durch ≤ linear geordnet, falls je zwei Elemente von B vergleichbar sind:
Für alle a, b ∈ B gilt a ≤ b oder b ≤ a.
Man nennt eine solche Menge B eine Kette in A. Das Zornsche Lemma besagt:
Hat jede Kette in A eine obere Schranke, so existiert ein maximales Element in A.
Es wird nicht behauptet, dass max(A) existiert. Behauptet wird lediglich: Es gibt mindestens ein a ∈ A, sodass kein b ∈ A größer als a ist.
Die leere Menge gilt als Kette und hat nach (#) eine obere Schranke a (jedes a ∈ A ist eine solche). Damit ist eine Ordnung, die die Kettenbedingung erfüllt, nichtleer.
Beispiele
(1) | Sei A = ℘({ 1, …, 100 }) geordnet durch ⊆. Dann ist B = { ∅, { 1 }, { 1, 4 }, { 1, 4, 10, 12 }, { 1, 4, 10, 12, 44, 45, 50 } } eine Kette. Dies gilt nicht für C = { { 1 }, { 1, 4 }, { 1, 2, 10 } }. |
(2) | Die durch ⊆ geordnete Menge A = ℘(ℕ) − { ℕ } hat keine maximalen Elemente. Die Ordnung erfüllt die Kettenbedingung nicht. Denn B = { { 0 }, { 0, 1 }, { 0, 1, 2 }, … } = { { 0, …, n } | n ∈ ℕ } ist eine Kette, besitzt aber keine obere Schranke in A. |
(3) | Auf ℕ sei ≼ = { (n, n + 2k) | n, k ∈ ℕ, n ≠ 0 } ∪ { (2k, 0) | k ∈ ℕ }, sodass 1 ≺ 3 ≺ 5 ≺ …, 2 ≺ 4 ≺ 6 ≺ … ≺ 0. Dann ist 0 ein maximales Element von ℕ. Die Kettenbedingung ist verletzt, da die Kette { 1, 3, 5, … } keine obere Schranke besitzt. |
Anschaulicher Beweis des Zornschen Lemmas
Wir setzen uns auf ein beliebiges a0 ∈ A und blicken von dort aus nach oben, d. h., wir betrachten X0 = { a ∈ A | a > a0 }. Sehen wir nichts (X0 = ∅), so ist a0 maximal in A und wir sind fertig. Andernfalls wählen wir ein beliebiges a1 ∈ X0. Es gilt dann
a0 < a1.
Nun klettern wir nach a1 hoch und blicken nach oben. Ist X1 = { a ∈ A | a > a1 } leer, so ist a1 maximal und wir sind fertig. Andernfalls wählen wir ein a2 ∈ X1. Dann gilt
a0 < a1 < a2.
So in der Ordnung hochkletternd finden wir entweder ein maximales Element an wie gewünscht, oder aber wir erhalten eine unendliche Kette
a0 < a1 < … < an < …
Nun hilft uns die Kettenbedingung weiter. Denn B = { an | n ∈ ℕ } ist linear geordnet. Nach (#) existiert also eine obere Schranke von B. Wir wählen eine derartige Schranke, die wir aω nennen (wobei ω an ∞ erinnert). Wir klettern nun nach aω und blicken von dort erneut nach oben. Ist Xω = { a ∈ A | a > aω } leer, so ist aω maximal. Andernfalls wählen wir ein beliebiges aω + 1 ∈ Xω und wiederholen das Verfahren des Hochkletterns, wobei wir an „Limesstellen“ des Hochkletterns die Kettenbedingung (#) zu Hilfe rufen. Irgendwann (das kann sehr, sehr, sehr lange dauern) finden wir schließlich ein maximales Element aα, denn sonst könnten wir wieder weiterklettern und aα + 1 bilden. Das Element aα > a0 ist wie gewünscht.
Zunächst sieht alles wie eine übliche Rekursion aus. Aber wir sind nach unendlich vielen Schritten noch nicht unbedingt fertig. In der ⊆-Ordnung auf ℘(ℕ) können wir über
a0 = { 0 }, a1 = { 0, 2 }, a2 = { 0, 2, 4 }, …
hochklettern, haben dann aber das maximale Element ℕ noch nicht gefunden. Erst
aω = { 0, 2, 4, … }, aω + 1 = { 0, 2, 4, …, 1 }, aω + 2 = { 0, 2, 4, …, 1, 3 }, …
liefert aω + ω = ℕ.
Der anschauliche Beweis kann unter Wahrung der Idee streng geführt werden, wenn man statt ℕ die transfiniten Zahlen
0, 1, 2, …, n, …, ω, ω + 1, ω + 2, …, ω + ω, ω + ω + 1, …, …, …, …, …, …, …, …, …
verwendet, mit denen jede noch so große partielle Ordnung durchwandert werden kann. Da diese Zahlen schwierig sind, wird das Zornsche Lemma oft entweder gar nicht bewiesen, oder es wird ein unanschaulicher Beweis geführt, der die transfiniten Zahlen vermeidet. Ist das Zornsche Lemma als eine Art Axiom aber einmal da, so kann es als Werkzeug verwendet werden, um in ähnlichen Situationen ein transfinites Hochklettern zu vermeiden. Zu diesem Zweck ist es von den Algebraikern ins Leben gerufen worden: Genuss des Transfiniten ohne transfinite Zahlen.
Obiger Beweis verwendet „wir wählen …“ und damit das Auswahlaxiom. Man kann zeigen, dass das Zornsche Lemma äquivalent zum Auswahlaxiom ist.