Beweisarchiv: Mengenlehre: Lemma von Zorn

Aus dem Auswahlaxiom folgt das Lemma von Zorn

Voraussetzung

Die Axiome von ZFC

Behauptung

Jede nichtleere halbgeordnete Menge, in der jede Kette (d.h. jede total geordnete Teilmenge) eine obere Schranke hat, enthält mindestens ein maximales Element.

Beweis

Sei $X$ eine nichtleere durch eine Relation $\le$ halbgeordnete Menge, in der jede Kette eine obere Schranke hat. Sei $𝒯\subseteq \mathrm{Pot}(X)$ die Menge aller Ketten in $X$. Für jedes $T\in 𝒯$ ist dann die Menge $S_T:=\{A\in X\mid A\text{ ist obere Schranke von }T\}$ nicht leer.

Wir nehmen an, dass $S_T\subseteq T$ für kein $T$ gilt. Dann ist die Menge $\{S_T\setminus T\mid T\in 𝒯\}$ eine Menge nichtleerer Mengen und besitzt daher eine Auswahlfunktion $F$. Für $T\in 𝒯$ ist dann $F(S_T\setminus T)$ echt größer als jedes Element von $T$. Dann haben wir eine Abbildung $G:𝒯\to X,T\mapsto F(S_T\setminus T)$, die man sich durch $G(U)=F(S_{\mathrm{\varnothing }})$ für $U\notin 𝒯$ auf ganz $\mathrm{Pot}(X)$ fortgesetzt denken kann.

Durch transfinite Rekursion definiert $I(v):=G(\{I(w)\mid w<v\})$ eine Abbildung von der Klasse $\mathrm{O}\mathrm{n}$ der Ordinalzahlen nach $X$.

Behauptung:

Für zwei Ordinalzahlen $w<v$ gilt $I(w)<I(v)$.

Beweis per Induktion: Sei $u$ Ordinalzahl und die Behauptung wahr für alle $v<u$. Dann ist $T:=\{I(w)\mid w<u\}$ total geordnet, denn aus $w,v<u$ mit $w\ne v$ folgt ja $w<v$ oder $v<w$, nach Induktionsvoraussetzung also $I(w)<I(v)$ oder $I(v)<I(w)$. Dann folgt aber, dass $I(u)=G(T)=F(S_T\setminus T)$ echt größer als jedes Element von $T$ ist, das ist die Induktionsbehauptung.

Insbesondere ist die Abbildung $I$ injektiv. Auf der Menge $Y=\{x\in X\mid \mathrm{\exists }v\in \mathrm{O}\mathrm{n}:x=I(v)\}$ gibt es daher eine (linksseitige) Umkehrabbildung $I^{-1}:Y\to \mathrm{O}\mathrm{n}$, mit der wir die Menge $O=\{I^{-1}(y)\mid y\in Y\}$ erhalten. Es folgt dann jedoch $O=\mathrm{O}\mathrm{n}$ im Widerspruch dazu, dass $\mathrm{O}\mathrm{n}$ eine echte Klasse ist. Daher muss die obige Annahme falsch sein, d.h es gibt ein $T\in 𝒯$ mit $S_T\subseteq T$.

Behauptung:

Für solch ein $T$ ist jedes Element $m$ der Menge $S_T$ ein maximales Element von $X$.

Ist nämlich $x\in X$ mit $x\ge m$, so ist auch $x$ obere Schranke von $T$, wegen $S_T\subseteq T$ also $x\in T$. Aber dann auch $m\ge x$, da $m$ obere Schranke ist. Folglich $m=x$, d.h. $m$ ist maximal.

Da $S_T$ nicht leer ist, sind wir fertig.

Aus dem Lemma von Zorn folgt das Auswahlaxiom

Voraussetzung

Die Axiome von ZF und der Satz:

Jede nichtleere halbgeordnete Menge, in der jede Kette eine obere Schranke hat, enthält mindestens ein maximales Element.

Behauptung

Jede Menge nichtleerer Mengen hat eine Auswahlfunktion

Beweis

Sei $A$ eine Menge nichtleerer Mengen.

Betrachte die Menge $F$ aller partiellen Auswahlfunktionen auf $A$, d.h. die Menge der Funktionen $f:D\to \bigcup A$ mit $D\subseteq A$ und $f(X)\in X$ für alle $X\in D$. Mit anderen Worten ist

$F=\{f\subseteq A\times \bigcup A\mid \mathrm{\forall }a\in A:\mathrm{\forall }b,c\in \bigcup A:(⟨a,b⟩\in f\wedge ⟨a,c⟩\in f)\to (b=c\wedge b\in a)\}$.

Wegen $\mathrm{\varnothing }\in F$ ist $F$ nicht leer. Die Menge $F$ ist durch Inklusion halbgeordnet. Ist $T\subseteq F$ eine Kette, so betrachte die Menge $\bigcup T\subseteq A\times \bigcup A$. Ist $a\in A$, $b,c\in \bigcup A$ und $⟨a,b⟩,⟨a,c⟩\in \bigcup T$, so gibt es ein $f_1\in T$ mit $⟨a,b⟩\in f_1$. Ebenso gibt es ein $f_2\in T$ mit $⟨a,c⟩\in f_2$. Da $T$ Kette ist, gilt $f_1\subseteq f_2$ oder $f_2\subseteq f_1$. Ist $f=\max \{f_1,f_2\}=f_1\cup f_2$, so $f\in T$, $⟨a,b⟩\in f$, $⟨a,c⟩\in f$. Folglich $b=c$ und $b\in a$. Somit ist $\bigcup T\in F$. Da aus $f\in T$ sofort $f\subseteq \bigcup T$ folgt, ist $\bigcup T$ obere Schranke von $T$. Nach dem Lemma von Zorn enthält $F$ also ein maximales Element $m$.

Ist $f\in F$, $x\in A$ und $f\cap (\{x\}\times x)$ leer, so ist für jedes Element $y$ der nicht-leeren Menge $x$ die Menge $g:=f\cup \{(x,y)\}$ ein Element von $F$ und es ist $f<g$, insb. ist solch ein $f$ nicht maximal. Für $m$ gilt daher umgekehrt $m\cap (\{x\}\times x)\ne \mathrm{\varnothing }$ für jedes $x\in A$, d. h. $m$ ist eine Funktion $m:A\to \bigcup A$. Da ferner stets $m(x)\in x$ gilt, ist $m$ eine Auswahlfunktion für $A$.