Beweisarchiv: Mengenlehre: Wohlordnungssatz

Aus dem Auswahlaxiom folgt der Wohlordnungssatz

Voraussetzung

Die Axiome von ZFC

Behauptung

Jede Menge hat eine Wohlordnung

Beweis

Sei $A$ eine beliebige Menge. Dann ist $\mathrm{Pot}(A)\setminus \{\mathrm{\varnothing }\}$ eine Menge nichtleerer Mengen und folglich gibt es eine Auswahlfunktion

$C:\mathrm{Pot}(A)\setminus \{\mathrm{\varnothing }\}\to \bigcup (\mathrm{Pot}(A)\setminus \{\mathrm{\varnothing }\})=A$

mit $C(U)\in U$ für alle $\mathrm{\varnothing }\ne U\subseteq A$. Zu jeder Relation $R\subseteq A\times A$ definiere

$D(R):=\{x\in A\mid \mathrm{\exists }y\in A:⟨x,y⟩\in R\vee ⟨y,x⟩\in R\}.$

Für Relationen $R,R^{\prime }\subseteq A\times A$ definiere

$R\le R^{\prime }:⟺R=R^{\prime }\cap (D(R)\times D(R))\wedge D(R)\times (D(R^{\prime })\setminus D(R))\subseteq R^{\prime }.$

Die so definierte zweistellige Relation $\le$ auf $\mathrm{Pot}(A\times A)$ ist reflexiv, transitiv und antisymmetrisch, d. h. eine Halbordnung. Sei schließlich

$W:=\{R\subseteq A\times A\mid R\text{ ist Wohlordnung auf }D(R)\}.$

Angenommen, die Menge $A$ lässt sich nicht wohlordnen. Dann gilt für $R\in W$ stets $D(R)\ne A$, folglich ist $s_R:=C(A\setminus D(R))$ definiert. Wenn $R$ Wohlordnung auf $D(R)$ ist, dann ist $S(R):=R\cup (D(R)\times \{s_R\})$ Wohlordnung auf $D(S(R))=S(R)\cup \{s_R\}$. (Anschaulich: Das neu hinzugenomme Element $s_R$ von $A$, das nicht von $R$ abgedeckt wurde, wird als größer als alle bisherigen Elemente deklariert). Somit ist $S$ eine Abbildung $W\to W$. Für $R\in W$ gilt nach Konstruktion stets $R<S(R)$. Der Form halber setzen wir $S$ zu einer Abbildung $\overline{S}:\mathrm{Pot}(A\times A)\to \mathrm{Pot}(A\times A)$ fort, indem wir $\overline{S}(R)=\mathrm{\varnothing }$ für alle $R\notin W$ setzen. Wir definieren eine Abbildung $I$ von der Klasse $\mathrm{On}$ der Ordinalzahlen nach $\mathrm{Pot}(A\times A)$ durch transfinite Rekursion vermöge

$I(v)=\overline{S}(\bigcup _{w<v}I(w)).$

Durch transfinite Induktion zeigt man jetzt die Aussage:

$\mathrm{\Phi }(v)$: Für $v\in \mathrm{On}$ ist $I(v)\in W$ und für $w<v$ ist $I(w)<I(v)$.

Zum Beweis der Aussage sei vorausgesetzt, dass für alle $v^{\prime }<v$ bereits $\mathrm{\Phi }(v^{\prime })$ gilt.

Betrachte die Relation $I:=\bigcup _{w<v}I(w)$ auf der Menge $D:=D\left(I\right)$. Für jedes Element $x\in D$ gibt es dann ein $w<v$ mit $x\in D(I(w))$. Für je zwei Elemente $x,y\in D$ kann man sogar ein gemeinsames $w<v$ mit $x,y\in D(I(w))$ finden (wähle zu $x,y$ zunächst einzeln und bilde das Maximum). Für jedes solche $w$ gilt $⟨x,y⟩\in I(w)⟺⟨x,y⟩\in I$. Da jedes $I(w)$, $w<v$ Totalordnung auf $D(I(w))$ ist, folgt dann, dass $I$ Totalordnung auf $D$ ist.

Ist $X\subseteq D$ nicht leer und etwa $x\in X$ ein Element, so gibt es ein $w<v$ mit $x\in D(I(w))$. Da $I(w)\in W$ und somit Wohlordnung auf $D(I(w))$ ist, sei $m:=\min (X\cap D(I(w))$. Für $y\in X$ mit $y\ne m$ gilt dann entweder $y\in D(I(w))$ und folglich $⟨m,y⟩\in I(w)\subseteq I$, oder $y\in D(I(w^{\prime }))\setminus D(I(w))$ für ein $w^{\prime }$ mit $w<w^{\prime }<v$. Aus $\mathrm{\Phi }(w^{\prime })$ folgt dann wiederum $⟨m,y⟩\in I(w^{\prime })\subseteq I$ wegen $I(w)<I(w^{\prime })$. Somit ist $⟨m,y⟩\in I$ für alle $y\in X$, $y\ne m$, mithin $I$ sogar Wohlordnung auf $D$.

Insbesondere gilt dann $I(v)=S(I)\in W$.

Sei jetzt $w<v$. Falls $⟨x,y⟩\in I(w)$, so auch $⟨x,y⟩\in I$, und falls $⟨x,y⟩\in I\cap D(I(w)\times D(I(w))$, so $x,y\in D(I(w))$, also $⟨x,y⟩\in I(w)⟺⟨x,y⟩\in I$, mithin $I(w)=I\cap D(I(w)\times D(I(w))$. Falls $x\in D(I(w))$ und $y\in D\setminus D(I(w))$, so $y\in D(I(w^{\prime }))$ für ein $w^{\prime }$ mit $w^{\prime }<v$. Es muss sogar $w<w^{\prime }$ gelten, denn sonst $y\in D(I(w^{\prime }))\subseteq D(I(w))$. Aus $\mathrm{\Phi }(w^{\prime })$ folgt dann $⟨x,y⟩\in I(w^{\prime })\subseteq I$, mithin ist $I(w)\le I<S(I)=I(v)$.

Somit gilt $\mathrm{\Phi }(v)$ für alle Ordinalzahlen $v\in \mathrm{On}$.

Mittels der so definierten Abbildung $I$ setze

$W^{\prime }:=\{R\in W\mid \mathrm{\exists }v\in \mathrm{On}:R=I(v)\}.$

Wegen $\mathrm{\Phi }$ ist $I$ injektiv, d. h. es gibt eine Umkehrabbildung $J:W^{\prime }\to \mathrm{On}$, so dass $I\circ J$ auf $W^{\prime }$ die Identität ist. Dann enthält aber die Menge $\{J(R)\mid R\in W^{\prime }\}$ sämtliche Ordinalzahlen. Dies widerspricht der Tatsache, dass $\mathrm{On}$ eine echte Klasse ist.

Die Annahme, dass die Menge $A$ sich nicht wohlordnen lässt, muss also falsch sein. Damit ist der Wohlordnungssatz bewiesen.

Aus dem Wohlordnungssatz folgt das Auswahlaxiom

Voraussetzung

Die Axiome von ZF und der Satz:

Jede Menge hat eine Wohlordnung

Behauptung

Jede Menge nichtleerer Mengen hat eine Auswahlfunktion

Beweis

Sei $A$ eine Menge nichtleerer Mengen. Wegen des Wohlordnungssatzes gibt es eine Wohlordung von $\bigcup A$. Da jedes Element $B$ von $A$ eine nichtleere Teilmenge von $\bigcup A$ ist, hat $B$ ein kleinstes Element $\min (B)$ bzgl. der Wohlordnung. Folgende Funktion ist dann eine Auswahlfunktion von A:

$f:A\to \bigcup A,B\mapsto \min (B).$

Aus dem Lemma von Zorn folgt der Wohlordnungssatz

Voraussetzung

Die Axiome von ZF und der Satz:

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

Behauptung

Jede Menge hat eine Wohlordnung

Beweis

Sei $A$ eine Menge. Zu einer Relation $R\subseteq A\times A$ sei $\mathrm{dom}(R)=\{a\mid ⟨a,b⟩\in R\}$ und $\mathrm{rg}(R)=\{b\mid ⟨a,b⟩\in R\}$. Auf $\mathrm{Pot}(A\times A)$ sei die folgende Relation definiert:

$R\le R^{\prime }⟺R\subseteq R^{\prime }\wedge \mathrm{dom}(R)\times (\mathrm{dom}(R^{\prime })\setminus \mathrm{dom}(R))\subseteq R^{\prime }$.

Diese Relation ist reflexiv, da für $R\in W$ stets $\mathrm{dom}(R)\times (\mathrm{dom}(R)\setminus \mathrm{dom}(R))=\mathrm{dom}(R)\times \mathrm{\varnothing }=\mathrm{\varnothing }\subseteq R$ gilt. Da aus $B\subseteq B^{\prime }\subseteq B^{″}$ auch $B\times (B^{″}\setminus B)=B\times (B^{\prime }\setminus B)\cup B\times (B^{″}\setminus B^{\prime })\subseteq B\times (B^{\prime }\setminus B)\cup B^{\prime }\times (B^{″}\setminus B^{\prime })$ folgt, ergibt sich auch, dass $\le$ transitiv ist. Insgesamt handelt es sich also um eine Halbordnung. Auch die Menge

$W:=\{R\subseteq A\times A\mid \mathrm{dom}(R)=\mathrm{rg}(R)\wedge R\text{ ist Wohlordnung von }\mathrm{dom}(R)\}$

aller Wohlordnungen auf Teilmengen von $A$ ist auf diese Weise halbgeordnet. Wegen $\mathrm{\varnothing }\in W$ ist $W$ nicht leer.

Sei $T\subseteq W$ eine Kette. Setze $S=\bigcup T\subseteq A\times A$. Man sieht leicht $\mathrm{dom}(S)=\bigcup \{\mathrm{dom}(U)\mid U\in T\}$ und $\mathrm{rg}(S)=\bigcup \{\mathrm{rg}(U)\mid U\in T\}$. Es folgt $\mathrm{dom}(S)=\mathrm{rg}(S)$. Sei $U\in T$, $a\in \mathrm{dom}(U)$, $b\in \mathrm{dom}(S)\setminus \mathrm{dom}(U)$. Dann ist $b\in \mathrm{dom}(V)\setminus \mathrm{dom}(U)$ für ein $V\in T$. Da gewiss nicht $V<U$ gelten kann, ist $U\le V$, also $⟨a,b⟩\in \mathrm{dom}(U)\times (\mathrm{dom}(V)\setminus \mathrm{dom}(U))\subseteq V\subseteq S$, mithin $\mathrm{dom}(U)\times (\mathrm{dom}(S)\setminus \mathrm{dom}(U))\subseteq S$. Es folgt $U\le S$ für alle $U\in T$.

Sei $X\subseteq \mathrm{dom}(S)$ nicht leer. Für beliebiges $x\in X$ gibt es dann ein $U\in T$ mit $x\in \mathrm{dom}(U)$. Insbesondere ist dann $X\cap \mathrm{dom}(U)$ nichtleere Teilmenge von $\mathrm{dom}(U)$ und enthält ein kleinstes Element $m$. Da für jedes $y\in X\setminus \mathrm{dom}(U)$ wegen $U\le S$ erst recht $m\le y$ folgt, ist $m$ auch kleinstes Element von $X$. Somit ist $S$ Wohlordnung auf $\mathrm{dom}(S)$ und daher obere Schranke von $T$ in $W$.

Also erfüllt $W$ die Voraussetzung des Lemmas von Zorn. Sei demnach $M\in W$ ein maximales Element. Falls $a\in A\setminus \mathrm{dom}(M)$ existiert, ist $M^{\prime }:=M\cup (\mathrm{dom}(M)\times \{a\})\cup \{⟨a,a⟩\}$ eine Wohlordnung von $\mathrm{dom}(M)\cup \{a\}$ mit $M^{\prime }\ge M$ im Widerspruch zur Maximalität von $M$. Daher muss $\mathrm{dom}(M)=A$ gelten, d. h. $M$ ist eine Wohlordnung auf $A$.