Beweisarchiv: Mengenlehre: Wohlordnungssatz

Beweisarchiv: Mengenlehre

Charakteristikum unendlicher Mengen

Injektivität Surjektivität Bijektivität: Faktoren · Komposition · Linksinverse · Linkskürzbarkeit · Rechtsinverse · Rechtskürzbarkeit

Verkettungen: Assoziativgesetz der Hintereinanderausführung

Mächtigkeiten (Kardinalzahlen): lineare Ordnung · Kardinalität und Bijektionen · Potenzmenge

Deskriptive Mengenlehre: Satz von Young

Rechenregeln für Mengenoperationen: Assoziativgesetze · Distributivgesetze · Differenzgesetze · Grundeigenschaften der Inklusion · De Morgansche Regeln für Mengen · Bild und Urbild

Ordinalzahlen: Ordinalzahlen enthalten sich nicht selbst als Element · Elemente von Ordinalzahlen sind Ordinalzahlen · Durchschnitte von Ordinalzahlen sind Ordinalzahlen · Wohlordnung der Klasse aller Ordinalzahlen · Ordinalzahlen bilden eine echte Klasse · Der Nachfolger einer Ordinalzahl ist Ordinalzahl · Vereinigungen von Ordinalzahlen sind Ordinalzahlen · Limes- und Nachfolgerzahlen · Äquivalenz verschiedener Definitionen

Sätze die in ZF Äquivalent zum Auswahlaxiom sind: Alternative Darstellung des Auswahlaxioms · Wohlordnungssatz · Lemma von Zorn

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 $\operatorname {Pot} (A)\setminus \{\emptyset \}$ eine Menge nichtleerer Mengen und folglich gibt es eine Auswahlfunktion

$C\colon \operatorname {Pot} (A)\setminus \{\emptyset \}\to \bigcup {\bigl (}\operatorname {Pot} (A)\setminus \{\emptyset \}{\bigr )}=A$

mit $C(U)\in U$ für alle $\emptyset \neq U\subseteq A$. Zu jeder Relation $R\subseteq A\times A$ definiere

$D(R):=\{x\in A\mid \exists y\in A\colon \langle x,y\rangle \in R\lor \langle y,x\rangle \in R\}.$

Für Relationen $R,R'\subseteq A\times A$ definiere

$R\leq R':\iff R=R'\cap \left(D(R)\times D(R)\right)\ \land \ D(R)\times \left(D(R')\setminus D(R)\right)\subseteq R'.$

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

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

Angenommen, die Menge $A$ lässt sich nicht wohlordnen. Dann gilt für $R\in W$ stets $D(R)\neq 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 ${\bar {S}}\colon \operatorname {Pot} (A\times A)\to \operatorname {Pot} (A\times A)$ fort, indem wir ${\bar {S}}(R)=\emptyset$ für alle $R\notin W$ setzen. Wir definieren eine Abbildung $I$ von der Klasse $\operatorname {On}$ der Ordinalzahlen nach $\operatorname {Pot} (A\times A)$ durch transfinite Rekursion vermöge

$I(v)={\bar {S}}\left(\bigcup _{w<v}I(w)\right).$

Durch transfinite Induktion zeigt man jetzt die Aussage:

$\Phi (v)$: Für $v\in \operatorname {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'<v$ bereits $\Phi (v')$ 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 $\langle x,y\rangle \in I(w)\iff \langle x,y\rangle \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\neq m$ gilt dann entweder $y\in D(I(w))$ und folglich $\langle m,y\rangle \in I(w)\subseteq I$, oder $y\in D(I(w'))\setminus D(I(w))$ für ein $w'$ mit $w<w'<v$. Aus $\Phi (w')$ folgt dann wiederum $\langle m,y\rangle \in I(w')\subseteq I$ wegen $I(w)<I(w')$. Somit ist $\langle m,y\rangle \in I$ für alle $y\in X$, $y\neq m$, mithin $I$ sogar Wohlordnung auf $D$.

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

Sei jetzt $w<v$. Falls $\langle x,y\rangle \in I(w)$, so auch $\langle x,y\rangle \in I$, und falls $\langle x,y\rangle \in I\cap D(I(w)\times D(I(w))$, so $x,y\in D(I(w))$, also $\langle x,y\rangle \in I(w)\iff \langle x,y\rangle \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'))$ für ein $w'$ mit $w'<v$. Es muss sogar $w<w'$ gelten, denn sonst $y\in D(I(w'))\subseteq D(I(w))$. Aus $\Phi (w')$ folgt dann $\langle x,y\rangle \in I(w')\subseteq I$, mithin ist $I(w)\leq I<S(I)=I(v)$.

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

Mittels der so definierten Abbildung $I$ setze

$W':=\{R\in W\mid \exists v\in \operatorname {On} \colon R=I(v)\}.$

Wegen $\Phi$ ist $I$ injektiv, d. h. es gibt eine Umkehrabbildung $J\colon W'\to \operatorname {On}$, so dass $I\circ J$ auf $W'$ die Identität ist. Dann enthält aber die Menge $\{J(R)\mid R\in W'\}$ sämtliche Ordinalzahlen. Dies widerspricht der Tatsache, dass $\operatorname {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\colon \,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 $\operatorname {dom} (R)=\{a\mid \langle a,b\rangle \in R\}$ und $\operatorname {rg} (R)=\{b\mid \langle a,b\rangle \in R\}$. Auf $\operatorname {Pot} (A\times A)$ sei die folgende Relation definiert:

$R\leq R'\iff R\subseteq R'\land \operatorname {dom} (R)\times (\operatorname {dom} (R')\setminus \operatorname {dom} (R))\subseteq R'$.

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

$W:=\{R\subseteq A\times A\mid \operatorname {dom} (R)=\operatorname {rg} (R)\,\land \,R{\mbox{ ist Wohlordnung von }}\operatorname {dom} (R)\}$

aller Wohlordnungen auf Teilmengen von $A$ ist auf diese Weise halbgeordnet. Wegen $\emptyset \in W$ ist $W$ nicht leer.

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

Sei $X\subseteq \operatorname {dom} (S)$ nicht leer. Für beliebiges $x\in X$ gibt es dann ein $U\in T$ mit $x\in \operatorname {dom} (U)$. Insbesondere ist dann $X\cap \operatorname {dom} (U)$ nichtleere Teilmenge von $\operatorname {dom} (U)$ und enthält ein kleinstes Element $m$. Da für jedes $y\in X\setminus \operatorname {dom} (U)$ wegen $U\leq S$ erst recht $m\leq y$ folgt, ist $m$ auch kleinstes Element von $X$. Somit ist $S$ Wohlordnung auf $\operatorname {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 \operatorname {dom} (M)$ existiert, ist $M':=M\cup (\operatorname {dom} (M)\times \{a\})\cup \{\langle a,a\rangle \}$ eine Wohlordnung von $\operatorname {dom} (M)\cup \{a\}$ mit $M'\geq M$ im Widerspruch zur Maximalität von $M$. Daher muss $\operatorname {dom} (M)=A$ gelten, d. h. $M$ ist eine Wohlordnung auf $A$.