Das Zornsche Lemma

Wir besprechen nun noch eine weitere Äquivalenz zum Auswahlaxiom, die in der Mathematik oft als „black box“ verwendet wird. Es handelt sich um ein Maximalprinzip für partielle Ordnungen. Folgende Begriffe der Ordnungstheorie werden verwendet:

Definition (obere Schranke, Kette, maximales Element)

Sei (P, <) eine partielle Ordnung.

(a)	Ein p  ∈  P heißt eine obere Schranke von A ⊆ P, falls A ≤ p, d. h. es gilt a ≤ p für alle a  ∈  A.

(b)	Ein K ⊆ P heißt eine Kette in P oder linear geordnet in P, falls für alle a, b  ∈  K gilt: a ≤ b oder b ≤ a.

(c)	Ein p  ∈  P heißt ein Ziel von P oder maximal in P, falls es kein q  ∈  P gibt mit p < q.

Damit können wir nun formulieren:

Satz (Zornsches Lemma, Satz von Zermelo-Zorn)

Sei (P, <) eine partielle Ordnung. Es gelte:

Jede Kette in P besitzt eine obere Schranke.(Kettenbedingung)

Dann existiert ein Ziel von P.

Bevor wir den Satz beweisen, diskutieren wir seine schematische Anwendung. In vielen Situationen möchten wir die Existenz eines „bestmöglichen Objekts“ beweisen. Wir definieren hierzu eine Menge P von Approximationen an ein solches Objekt und legen fest, wann eine Approximation besser als eine andere sein soll. Dies liefert eine partielle Ordnung (P, <). Wir beweisen, dass jede Kette in P eine obere Schranke in P besitzt. Nun können wir das Zornsche Lemma einsetzen: Es liefert ein Ziel der Ordnung. Ein solches Element ist eine nicht mehr zu verbessernde Approximation und damit ein bestmögliches Objekt wie gewünscht.

Ein Paradebeispiel für diese Technik ist der Beweis, dass das Zornsche Lemma das Auswahlaxiom impliziert: Das gesuchte Objekt ist eine Auswahlmenge für ein gegebenes Mengensystem, die Approximationen sind Auswahlmengen für Teilsysteme. Mit dieser Idee zeigen wir:

Satz (Äquivalenz von Zornschem Lemma und Auswahlaxiom)

In ZF gilt: Das Zornsche Lemma impliziert das Auswahlaxiom.

Beweis

Sei A eine Menge paarweise disjunkter nichtleerer Mengen. Wir setzen

P = { B ⊆ ⋃ A | für alle a  ∈  A existiert höchstens ein b  ∈  B mit b  ∈  a }.

Dann ist P mit der Inklusion ⊂ eine partielle Ordnung, die die Kettenbedingung erfüllt, denn für jede Kette K ⊆ P ist ⋃ K  ∈  P. Nach dem Zornschen Lemma gibt es ein Ziel B  ∈  P. Dann ist B eine Auswahlmenge für A. Denn andernfalls gibt es ein a  ∈  A mit a ∩ B = ∅. Ist nun b  ∈  a beliebig, so ist B ∪ { b }  ∈  P, im Widerspruch zur Maximalität von B.

Auch in vielen weiteren Fällen ist die betrachtete partielle Ordnung die Inklusion auf einer Menge P und darüber hinaus ⋃ K eine obere Schranke einer beliebigen Kette K in P. Wir definieren hierzu:

Definition (Zermelo-System)

Eine partielle Ordnung (Z, ⊂) heißt ein Zermelo-System, falls gilt:

Ist L ⊆ Z eine Kette in Z, so ist ⋃ L  ∈  Z.

Wir nennen auch kurz Z statt (Z, ⊂) ein Zermelo-System. Da ∅ ⊆ Z linear geordnet ist, ist ∅ = ⋃ ∅  ∈  Z. Wir zeigen:

Satz (Zornsches Lemma und Zermelo-Systeme)

Die folgenden Aussagen sind über ZF äquivalent:

(a)	Das Zornsche Lemma.

(b)	Jedes Zermelo-System besitzt ein Ziel.

Beweis

(a) impliziert (b): Ein Zermelo-System Z erfüllt die Kettenbedingung. Nach dem Zornschen Lemma existiert also ein Ziel von Z.

(b) impliziert (a): Sei (P, <) eine partielle Ordnung, die die Kettenbedingung erfüllt. Wir setzen

Z = { K ⊆ P | K ist eine Kette in P }.

Wir zeigen, dass (Z, ⊂) ein Zermelo-System ist. Sei hierzu L ⊆ Z linear geordnet durch ⊂, und sei K* = ⋃ L. Wir zeigen, dass K*  ∈  Z. Hierzu seien p, q  ∈  K*. Dann gibt es K_p,  K_q  ∈  L mit p  ∈  K_p und q  ∈  K_q. Da L eine Kette in Z ist, sind K_p und K_q vergleichbar durch Inklusion. Wir nehmen ohne Einschränkung an, dass K_p ⊆ K_q. Dann gilt p, q  ∈  K_q. Da K_q eine Kette in P ist, gilt p ≤ q oder q ≤ p. Dies zeigt, dass K* eine Kette in P ist. Folglich ist K*  ∈  Z. Damit ist Z ein Zermelo-System.

Sei nun K ein Ziel von Z. Da K ein Kette in P ist, gibt es ein p  ∈  P mit K ≤ p. Dann gibt es kein q > p in P, da sonst K ⊂ K ∪ { q }  ∈  Z gelten würde, im Widerspruch zu K Ziel von Z. Also ist p ein Ziel von P.

Damit können wir nun das Zornsche Lemma (mit Hilfe von AC) beweisen:

Beweis des Zornschen Lemmas

Sei Z ein Zermelo-System. Wir zeigen, dass Z ein Ziel besitzt. Annahme nicht. Wir definieren f : Z → Z mit Hilfe des Auswahlaxioms durch

f (A) = „ein B  ∈  Z mit A ⊂ B“ für alle A  ∈  Z.

Für den Rest des Beweises wird das Auswahlaxiom nicht mehr verwendet.

Wir nennen ein Y ⊆ Z geschlossen, falls Y abgeschlossen unter f ist und für jede Kette K ⊆ Y gilt, dass ⋃ K  ∈  Y. Speziell ist Z geschlossen. Wir setzen

K* = ⋂ { Y ⊆ Z | Y ist geschlossen }.

Dann ist K* geschlossen. Zudem gilt:

(+) Ist Y ⊆ K* geschlossen, so ist Y = K*.

Wir zeigen über mehrere Zwischenschritte, dass K* eine Kette in Z ist. Hierzu nennen wir ein S  ∈  K* einen Schnitt, falls gilt:

∀A  ∈  K* (f (A) ⊆ S ∨ S ⊆ A).

Ist S  ∈  K* ein Schnitt, so gilt stärker:

(++) ∀A  ∈  K* (f (A) ⊆ S ∨ A = S ∨ f (S) ⊆ A).

Beweis von (++)

Sei S  ∈  K* ein Schnitt, und sei

Y = { A  ∈  K* | A ⊆ S ∨ f (S) ⊆ A }.

Dann ist Y geschlossen (Übung). Nach (+) ist Y = K*. Ist nun A  ∈  K* von S verschieden und f (A) keine Teilmenge von S, so ist auch A keine Teilmenge von S. Wegen A  ∈  Y ist also f (S) ⊆ A. Dies zeigt (++).

Wir setzen nun:

X = { S  ∈  K* | S ist ein Schnitt }.

Dann ist X geschlossen (Beweis als Übung, die Eigenschaft (++) wird zum Beweis der Abgeschlossenheit von X unter f verwendet). Nach (+) ist also X = K* und damit ist jedes Element von K* ein Schnitt. Für alle A, S  ∈  K* gilt also

A ⊂ f (A) ⊆ S ∨ S ⊆ A.

Dies zeigt, dass K* eine Kette in Z ist.

Sei nun A = ⋃ K*. Da K* geschlossen und eine Kette ist, ist A  ∈  K*. Weiter ist dann f (A)  ∈  K*, da K* abgeschossen unter f ist. Dann ist aber

f (A) ⊆ ⋃ K* = A ⊂ f (A),

Widerspruch.

Der technische Beweis wird vielleicht etwas leichter verdaulich, wenn wir der Menge K* eine anschauliche Bedeutung geben. K* ist die kleinste Teilmenge von Z, die abgeschlossen unter der Nachfolgerbildung f (A) und der Kettenvereinigung ⋃ K ist. Was ist in K* enthalten? Zunächst muss ∅ = ⋃ ∅  ∈  K* gelten. Dann sind aber auch

f (∅), f (f (∅)), …, f ⁿ(∅), …

Elemente von Z. Diese Elemente bilden eine Kette, sodass

A = ⋃_{n  ∈  ℕ} f ⁿ(∅)

ein Element von K* ist.

Die Kette f (∅) ⊂ f (f (∅) ⊂ … ⊂ f ⁿ(∅) ⊂ … ⊂ A

Dann sind aber auch

f (A), f (f (A)), …, f ⁿ(A), …

in K*, sodass wir eine weitere Kette erhalten, die zum Element

B = ⋃_{n  ∈  ℕ} f ⁿ(A)

von K* führt. So fortfahrend erhalten wir C, D, E, … in K* und

A* = A ∪ B ∪ C ∪ …

in K* usw. Die Menge K* besteht aus genau den Elementen von Z*, die bei diesem Prozess angetroffen werden. Damit ist auch klar, das K* eine Kette ist.

In der Mengenlehre können Prozesse dieser Art mit Hilfe der transfiniten Zahlen ebenso anschaulich wie formal untadelig durchgezählt werden. Damit ergibt sich ein viel klarerer (fast trivialer) Beweis des Zornschen Lemmas:

Steige solange in der partiellen Ordnung hoch, bis du ein maximales Element findest und nicht mehr weiter hochsteigen kannst.

Das Problem ist, dass die natürlichen Zahlen im Allgemeinen nicht ausreichen, die Stufen dieses Hochsteigens zu indizieren. Gebraucht werden die transfiniten Zahlen und damit die Theorie der Wohlordnungen. Das Zornsche Lemma ist gerade dafür gemacht worden, die Theorie der Wohlordnungen zu eliminieren (damit man sie nicht lernen muss). Ob zum Guten, sei dahingestellt. Unabhängig von solchen letztendlich didaktischen Fragen zeigt unser Beweis, dass die Theorie der Wohlordnungen für einen Beweis des Zornschen Lemmas nicht eingesetzt werden muss. Das Zornsche Lemma ist, egal auf welchem Wege es bewiesen wird, ein zweifelsohne nützliches und flexibles Hilfsmittel. Es lässt sich auch noch durch andere Maximalprinzipien der Ordnungstheorie ergänzen. Wir besprechen dies in den Übungen.

Insgesamt haben wir bewiesen:

Satz (Äquivalenz von Zornschem Lemma und Auswahlaxiom)

Die folgenden Aussagen sind über ZF äquivalent:

(a)

AC.

(b)	Das Zornsche Lemma.

Nach den begrifflichen und beweistechnischen Mühen ist die Ernte der Früchte angesagt. Das Zornsche Lemma erlaubt einen einfachen Beweis des Vergleichbarkeitssatzes der Mengenlehre:

Satz (Vergleichbarkeitssatz)

Für alle Mengen A, B gilt |A| ≤ |B| oder |B| ≤ |A|.

Beweis

Sei Z = { f | f : C → B injektiv, C ⊆ A }. Dann ist Z ein Zermelo-System. Sei also g ein Ziel von Z. Dann ist g : A → B injektiv oder g : C → B bijektiv mit C ⊂ A, da wir andernfalls die Funktion g in Z fortsetzen könnten. Im ersten Fall ist |A| ≤ |B|. Im zweiten Fall ist g^{− 1} : B → A injektiv, sodass |B| ≤ |A|.

Für Leser mit Grundkenntnissen der Linearen Algebra zeigen wir noch:

Satz (Basisexistenzsatz)

Sei V ein K-Vektorraum. Dann existiert eine Basis B von V.

Beweis

Eine Menge von Vektoren ist genau dann eine Basis von V, wenn sie linear unabhängig und erzeugend ist. Wir setzen

Z = { A ⊆ V | A ist linear unabhängig }.

Dann ist Z ein Zermelo-System, da die Vereinigung einer Kette linear unabhängiger Mengen linear unabhängig ist. (Die leere Menge gilt als linear unabhängig, sodass ∅  ∈  Z.) Sei also B ein Ziel von Z. Dann ist die Menge B erzeugend, da wir andernfalls B zu einer linear unabhängigen Menge B ∪ { v } in Z vergrößern könnten. Also ist B eine Basis von V.