Das Lemma von Zorn

“Logische Grundlagen der Mathematik”, WS
2014/15
Thomas Timmermann
28. Januar 2015
Wir beweisen zum Abschluss der Vorlesung die Implikationen
(3)
Auswahlaxiom
dl
qy
+3
(1)
Lemma von Zorn
(2)
Wohlordnungsprinzip
Hier die einzelnen Aussagen:
Auswahlaxiom Ist a eine nicht-leere Menge, so existiert eine Auswahlfunktion für
S
a, d.h. eine Abbildung c : a → a mit c(x) ∈ x für alle x ∈ a.
Für endliche Mengen kann man das per Induktion beweisen, für unendliche benötigt
man so etwas wie transfinite Induktion, aber nicht nur für Ordinalzahlen, sondern
für beliebige Mengen. Dass so etwas geht, behauptet das Wohlordnungsprinzip:
Wohlordnungsprinzip Jede Menge besitzt eine Wohlordnung, oder, äquivalent,
jede Menge ist gleichmächtig zu einer Ordinalzahl.
Wieso sind beide Aussagen äquivalent? Nach letzter Vorlesung finden wir für jede wohlgeordnete Menge a eine Ordinalzahl γ und einen Ordnungsisomorphismus
f : γ → a. Ist umgekehrt a noch nicht wohlgeordnet, γ eine Ordinalzahl und
f : γ → a eine Bijektion, so wird a wohlgeordnet durch x ≤ y ⇔ f −1 (x) ≤ f −1 (y ).
Lemma von Zorn Sei a halbgeordnete Menge. Falls jede Kette in a eine obere
Schranke hat, so enthält a ein maximales Element.
Wir fangen mit dem Einfachsten an und hören mit dem Schwierigsten auf:
1
(1) Wohlordnungsprinzip ⇒ Auswahlaxiom Sei a eine nicht-leere Menge. Nach
S
dem Wohlordnungsprinzip können wir die Menge b := a wohlordnen. Eine Auswahlfunktion c : a → b ist dann gegeben durch c(x) := min{z ∈ b : z ∈ x}.
(2) Lemma von Zorn ⇒ Wohlordnungsprinzip Schritt 1: Sei a eine Menge. Wir
wollen zeigen, dass es eine Wohlordnung auf a gibt, und wenden dazu das Lemma
von Zorn auf die Menge aller Wohlordnungen auf Teilmengen von a an.
Bezeichne also A die Menge aller Paare (b, ≤), bestehend aus einer Teilmenge
b ⊆ a und einer Wohlordnung ≤ auf b. Dann wird durch
(b1 , ≤1 ) (b2 , ≤2 )
⇔
b1 ⊆ b2 und x ≤1 y ⇔ x ≤2 y für alle x, y ∈ b1
eine Halbordnung auf A definiert.
Schritt 2: Sei K ⊆ A eine Kette, also eine total geordnete Teilmenge. Setze
[
c := {b : (b, ≤) ∈ K} ⊆ a.
Seien x, y ∈ c. Dann existieren (b1 , ≤1 ) und (b2 , ≤2 ) in K mit x ∈ b1 und y ∈ b2 .
Da K total geordnet ist, gilt (b1 , ≤1 ) (b2 , ≤2 ) oder (b1 , ≤1 ) (b2 , ≤2 ). Gelte
oBdA ersteres. Dann folgt x ∈ b1 ⊆ b2 und wir definieren
x :≤c y
⇔
x ≤2 y .
Man kann nun nachprüfen, dass ≤c eine Wohlordnung auf c definiert und (c, ≤c )
eine obere Schranke für K ist, also (b, ≤) (c, ≤c ) für jedes (b, ≤) in K gilt.
Schritt 3: Nach dem Lemma von Zorn enthält A also ein maximales Element (b, ≤).
Angenommen, b 6= a. Dann existiert ein x ∈ a \ b und auf c := {x} ∪ b erhalten wir
eine Wohlordnung ≤c , indem wir die Wohlordnung auf b nehmen und durch x < y
für alle y ∈ b ergänzen. Dann wäre (b, ≤) ≺ (c, ≤c ), Widerspruch.
Also ist b = a und ≤ eine Wohlordnung auf a.
(3) Das Auswahlaxiom ⇒ das Lemma von Zorn Sei (a, ≤) eine halbgeordnete
Menge ohne maximale Elemente, in der jede Kette eine obere Schranke besitzt,
und sei c : P(a) \ {∅} → a eine Auswahlfunktion für P(a) \ {∅}.
Wir werden zeigen: Zu jeder Ordinalzahl γ > 0 gibt es eine Abbildung hγ : γ → a
mit folgenden Eigenschaften:
(i) hγ (0) = c(a) ∈ a;
2
(ii) hγ (ξ + 1) = c({z ∈ a : z > hγ (ξ)}) falls ξ, ξ + 1 < γ;
(iii) hγ (λ) = c({z ∈ a : z > hγ (ξ) für alle ξ < λ}), falls λ < γ eine Limeszahl
ist.
Aus den Bedingungen (ii) und (iii) folgt dann sofort für alle Ordinalzahlen η, ξ:
η<ξ<γ
⇒
hγ (η) < hγ (ξ),
insbesondere ist hγ injektiv für jede Ordinalzahl. Nach letzter Vorlesung bilden aber
die Ordinalzahlen, die eine injektive Abbildung nach a erlauben, eine Menge. Das
ist ein Widerspruch.
Die Existenz von hγ für jede Ordinalzahl γ beweisen wir mit transfiniter Induktion.
1. Induktionsanfang γ = {∅}: Setze z.B. hγ := c(a).
2. Induktionsschritt für eine Nachfolgezahl γ = s(β):
Angenommen, hβ existiert. Dann ist hβ (β) ⊆ a eine Kette. Wir wählen eine obere
Schranke
{z ∈ a : z > hβ (ξ) für alle ξ < β} )
|
{z
}
Menge der oberen Schranken von hβ (β)
x = c(
Nun können wir hγ definieren durch
(
hβ (ξ),
hγ (ξ) :=
x,
ξ < β, d.h. ξ ∈ β,
ξ = β.
S
3. Induktionsschritt für eine Limeszahl γ = γ:
Angenommen, hβ existiert für jedes β < γ. Ist α < β, so stimmen hα und hβ auf
α überein. Wir definieren dann hγ durch hγ (ξ) := hξ+1 (ξ) für alle ξ ∈ γ (beachte
ξ + 1 < γ.)
Typische Anwendungen des Lemmas von Zorn
Satz. Jeder Vektorraum besitzt eine Basis.
Beweis. Schritt 1: Sei V ein Vektorraum und A ⊆ P(V ) die Menge aller linear
unabhängigen Teilmengen, halbgeordnet durch Inklusion.
S
Schritt 2: Sei K ⊆ A eine Kette. Dann ist c := K auch linear unabhängig.
Pn
Denn andernfalls gäbe es eine nicht-triviale Linearkombination 0 = i=1 λi vi mit
3
v1 , . . . , vn ∈ c, und nach Def. von c gäbe es ein d ∈ K mit v1 , . . . , vn ∈ d, im
Widerspruch zur linearen Unabhängigkeit von d.
Schritt 3: Sei b ⊆ A ein maximales Element. Dann ist b linear unabhängig, aber
auch ein Erzeugendensystem, denn sonst gäbe es ein v ∈ V so, dass auch b ∪ {v }
linear unabhängig wäre, im Widerspruch zur Maximalität von b.
Satz. Seien a und b Mengen. Dann gibt es eine injektive Abbildung a → b oder
eine injektive Abbildung b → a, d.h. es gilt |a| ≤ |b| oder |b| ≤ |a|.
Beweis. Schritt 1: Sei A die Menge aller Teilmengen f ⊆ a × b, die der Graph einer
Bijektion zwischen Teilmengen von a und b sind (äquivalent: A ist die Menge aller
Tripel (c, d, f ), wobei c ⊆ a, d ⊆ b und f : c → d bijektiv ist). Diese Menge wird
halbgeordnet durch Inklusion.
S
Schritt 2: Ist K ⊆ A eine Kette, so ist K ebenfalls der Graph einer Bijektion
zwischen Teilmengen von a und b und eine obere Schranke von K.
Schritt 3: Somit besitzt A ein maximales Element f ⊆ a×b. Falls c := {x : (x, y ) ∈
f} =
6 a und d := {y : (x, y ) ∈ f } =
6 b, so finden wir x ∈ a \ c und y ∈ b \ d, und
dann ist f ≺ f ∪ {(x, y )} ∈ A im Widerspruch zur Maximalität.
Also ist c = a und f Graph einer Injektion a → b, oder d = b und f beschreibt
eine Injektion b → a.
Nicolas Bourbaki und die Neuschreibung der Grundlagen
1939 erschien Bourbakis erster Band, dem viele weitere folgten:
4
I Théorie des ensembles
II Algèbre
III Topologie générale
IV Fonctions d’une variable réelle
V Espaces vectoriels topologiques
Später erschienen Überblicks-
VI Intégration
VII Algèbre commutative
Charles Denis Bourbaki
VIII Groupes et algèbres de Lie
(1816–1897)
IX Théories spectrales
Werke:
• Eléments d’histoire de mathématique
• Panorama of pure mathematics as seen by Bourbaki
Die Mitglieder von Bourbaki
• Gründungskongress 1935 durch Henri Cartan, Claude Chevalley, Jean Delsarte, René de Possel, Jean Dieudonné und André Weil
• spätere Mitglieder: Laurent Schwartz, Jean-Pierre Serre, Alexander Grothendieck, Serge Lang, Pierre Cartier, . . .
• Regeln: Ausschluss aus Altersgründen mit 50, Frauen zugelassen
5
Zitate
“Structures are the weapons of the mathematician.”
Nicolas Bourbaki
“A whole generation of graduate students were trained to think like Bourbaki.”
Mac Lane
Saunders
“The misunderstanding was that many people thought that it should be taught the way it
was written in the books. You can think of the first books of Bourbaki as an encyclopedia
of mathematics, containing all the necessary information. That is a good description. If
you consider it as a textbook, it’s a disaster. ”
Pierre Cartier
“Most books nowadays tend to be too formal most of the time. They give too much in
the way of formal proofs, and not nearly enough in the way of motivations and ideas. Of
course it is difficult to do that—to give motivations and ideas... French mathematics has
been dominant and has led to a very formal school. I think it is very unfortunate that
most books tend to be written in this overly abstract way and don’t try to communicate
understanding.”
Michael Francis Atiyah
6