Für die letzte Proposition habe ich in der Vorlesung keinen Beweis angegeben. Vielleicht war das ganz gut, da ich annehme, dass es für die meisten schon genug Formales in dieser Vorlesung war. Ich werde wahrscheinlich in der nächsten Woche nur kurz etwas dazu sagen und gebe hier einen Beweis für die Interessierten.
Mächtigkeiten von Mengen
Wir definieren eine zweistellige Relation auf Mengen, die wir für zwei Mengen $A$, $B$ als $|A|=|B|$ schreiben wollen, vorerst ohne dem Ausdruck $|A|$ alleine eine Bedeutung zuzuweisen.
Definition. Wir schreiben $|A|=|B|$, wenn eine Bijektion $h\colon A\to B$ existiert.
Proposition. Dies ist eine Äquivalenzrelation.
Cantor gibt in „Ueber eine elementare Frage der Mannigfaltigkeitslehre.“ (1891) den sehr einfachen Beweis der folgenden Aussage. Der Beweis ist als Diagonalargument bekannt.
Satz. Ist $M$ eine Menge, so existiert keine surjektive Funktion $\phi\colon M\to\{0,1\}^M$.
Beweis. Sei $\phi\colon M\to\{0,1\}^M$. Wir definieren $g\colon M\to\{0,1\}$ durch $g(x):=1-\phi(x)(x)$. Dann gilt für beliebiges $x\in M$, dass $g(x)\ne\phi(x)(x)$, also $g\ne\phi(x)$. Damit ist $g\notin\mathrm{Im}\,\phi$.
Bemerkung. $\{0,1\}^M\to\mathcal P(M)$, $f\mapsto \{x\colon f(x)=1\}$ ist eine Bijektion.
Definition. Wir schreiben $|A|\le|B|$, wenn eine injektive Funktion $f\colon A\to B$ existiert.
Proposition. Diese Relation ist transitiv.
Satz. (Cantor-Bernstein-Schröder) Sind $f\colon A\to B$ und $g\colon B\to A$ Injektionen, so existiert eine Bijektion $h\colon A\to B$. (Ist $|A|\le |B|$ und $|B|\le |A|$, so ist $|A|=|B|$.)
Proposition. Es ist $|\mathbb R|$=$|\mathcal P(\mathbb N)|$.
Beweis. Dazu genügt es nun Injektionen $\{0,1\}^{\mathbb N}\to\mathbb R$ und $\mathbb R\to\{0,1\}^{\mathbb N}$ anzugeben. Ersteres geschieht durch $a\mapsto\sum_{k=0}^\infty 3^{-(k+1)}a_k$, letzteres dadurch, dass wir eine reelle Zahl $x$ auf eine Folge $a$ mit $x=\sum_{k=0}^\infty 2^k a_{2k+1}+\sum_{k=0}^\infty 2^{-(k+1)}a_{2k}$ abbilden. Beides wurde in der Vorlesungen mit Darstellungen zur Basis $3$ beziehungsweise $2$ erläutert.
Wir haben damit erneut gesehen, dass $|\mathbb R|>|\mathbb N|$.
Auf die beiden folgenden Fragen werden wir zurückkommen.
Frage. Gilt für Mengen $A$ und $B$ immer $|A|\le |B|$ oder $|B|\le |A|$?
Frage. (Kontinuumshypothese, Cantor 1878) Gilt für Teilmengen $X$ von $\mathbb R$ immer $|X|\le |\mathbb N|$ oder $|X|=|\mathbb R|$?
Das Konzept einer Wohlordnung hängt eng mit dem Prinzip der vollständigen Induktion zusammen. Das vollständige Induktion über natürliche Zahlen funktioniert liegt gerade daran, dass die Menge der natürlichen Zahlen wohlgeordnet ist: Wollen wir zeigen, dass eine Aussage $A(n)$ für alle natürlichen Zahlen $n$ gilt, so genügt es, zu zeigen, dass $A(n)$ gilt, wann immer $A(m)$ für alle $m$ mit $m<n$ gilt. Das zeigt nämlich, dass die Menge aller $n$, für die $A(n)$ nicht gilt, kein kleinstes Element hat, also leer sein muss. Ebenso funktioniert Induktion für wohlgeordnete Mengen. Ein Beispiel ist der Beweis nach der nächsten Definition.
Definition. Eine Teilmenge $A$ einer wohlgeordneten Menge $M$ heißt Anfangsstück von $M$, wenn für alle $y\in A$ und $x\in M$ mit $x<y$ gilt, dass $x\in A$.
Proposition. Es seien $M$, $N$ wohlgeordnete Mengen und $f,g\colon M\to N$ Ordnungsisomorphismen auf Anfangsstücke von $N$ (d.h. ordnungserhaltende injektive Abbildungen, deren Bilder Anfangsstücke von $N$ sind). Dann gilt $f=g$.
Beweis. Für jedes $x\in M$ gilt \[f(x)=\min\left\{y\in N\colon y>f(\tilde x)\text{ für alle }\tilde x<x\right\},\]denn sonst wäre $f$ nicht ordnungserhaltend oder $f[M]$ hätte eine „Lücke“ bei $\min\left\{y\colon y>f(\tilde x)\text{ f. a. }\tilde x<x\right\}$, wäre also kein Anfangsstück. Entsprechendes gilt für $g$. Wir sehen also: Ist $x\in M$ und $f(\tilde x)=g(\tilde x)$ für alle $\tilde x<x$, so ist \begin{multline*}f(x)=\min\left\{y\in N\colon y>f(\tilde x)\text{ für alle }\tilde x<x\right\}=\\=\min\left\{y\in N\colon y>g(\tilde x)\text{ für alle }\tilde x<x\right\}=g(x).\end{multline*} Damit hat $\{x\in M\colon f(x)\ne g(x)\}$ kein Minimum, muss also leer sein.
Diese Proposition ist ein Schritt im Beweis der folgenden. Zusammen sagen sie, dass der Begriff der Wohlordnung starrer ist als man vielleicht zunächst erwartet hätte.
Propostion. Seien $M$ und $N$ wohlgeordnete Mengen, so existiert ein Ordnungsisomorphismus von $M$ auf ein Anfangsstück von $N$ oder ein Ordnungsisomorphismus von $N$ auf ein Anfangsstück von $M$.
Beweis. Für $x\in M$ setzen wir $M_{\le x}:=\{\tilde x\in M\colon \tilde x\le x\}$ und entsprechend $M_{\lt x}$. Zunächst stellen wir fest, dass, wenn für jedes $x\in M$ ein Ordnungsisomorphismus $f_x\colon M_x\to N$ von $M_x$ auf ein Anfangsstück von $N$ existiert, ein Ordnungsisomorphismus von $M$ auf ein Anfangsstück von $N$ existiert. In diesem Falle gilt nämlich für $x_1<x_2$ aufgrund der Eindeutigkeit aus der letzten Proposition, dass $f_{x_2}|_{M_{x_1}}=f_{x_1}$. Daraus schließt man leicht, dass $x\mapsto f_x(x)$ einen Ordnungsisomorphismus von $M$ auf ein Anfangsstück von $N$ definiert.
Sei dies nun also nicht der Fall. Dann gibt es ein kleinstes $x\in M$, für das kein $f_x$ wie oben existiert. Das obige Argument auf $M_{<x}$ angewandt liefert einen Ordnungsisomorphismus $f$ von $M_{<x}$ auf ein Anfangsstück von $N$. Dieses Anfangsstück muss aber ganz $N$ sein. Sonst existierte nämlich $y=\mathrm{min}(N\setminus f[M_{<x}])$ und wir könnten $f$ durch $f(x):=y$ zu einem Ordnungsisomorphismus von $M_{\le x}$ nach $f[M_{<x}]\cup\{y\}$ fortsetzen, im Gegensatz zu der Annahme, dass ein solcher nicht existiert. Damit ist aber $f^{-1}$ ein Ordnungsisomorphismus von $N$ auf das Anfangsstück $M_{<x}$ von $M$.
Folgerung. Sind $A$ und $B$ Mengen, die sich wohlordnen lassen, so gilt $|A|\le |B|$ oder $|B|\le |A|$.
Beweis. Dazu genügt es nun Injektionen $\{0,1\}^{\mathbb N}\to\mathbb R$ und $\mathbb R\to\{0,1\}^{\mathbb N}$ anzugeben. Ersteres geschieht durch $a\mapsto\sum_{k=0}^\infty 3^{-(k+1)}a_k$, letzteres dadurch, dass wir eine reelle Zahl $x$ auf eine Folge $a$ mit $x=\sum_{k=0}^\infty 2^k a_{2k+1}+\sum_{k=0}^\infty 2^{-(k+1)}a_{2k}$ abbilden. Beides wurde in der Vorlesungen mit Darstellungen zur Basis $3$ beziehungsweise $2$ erläutert.
Wir haben damit erneut gesehen, dass $|\mathbb R|>|\mathbb N|$.
Auf die beiden folgenden Fragen werden wir zurückkommen.
Frage. Gilt für Mengen $A$ und $B$ immer $|A|\le |B|$ oder $|B|\le |A|$?
Frage. (Kontinuumshypothese, Cantor 1878) Gilt für Teilmengen $X$ von $\mathbb R$ immer $|X|\le |\mathbb N|$ oder $|X|=|\mathbb R|$?
Wohlordnungen
Cantors ursprüngliches Interesse kam daher, dass er formalisieren wollte, was es heißt, eine Operation unendlich oft zu iterieren. Dies führte ihn zum Begriff der Wohlordnung.
Definition. Eine Wolhlordnung auf einer Menge $M$ ist eine totale Ordnung, bezüglich derer jede nicht-leere Teilmenge von $M$ ein Minimum hat.
Beispiele.
- Die natürliche Ordnung auf der Menge der natürlichen Zahlen ist eine Wohlordnung.
- Die natürliche Ordnung auf der Menge der ganzen Zahlen ist keine Wohlordnung, die Menge selber hat ja kein Minimum.
- Ersetzt man in einer Wohlordnung jedes Element durch eine wohlgeordnete Menge, so erhält man wieder eine Wohlordnung. (Wie ist das zu formalisieren und zu beweisen?)
- Eine Teilmenge einer wohlgeordneten Menge ist durch die Einschränkung der Wohlordnung wohlgeordnet.
Definition. Eine Teilmenge $A$ einer wohlgeordneten Menge $M$ heißt Anfangsstück von $M$, wenn für alle $y\in A$ und $x\in M$ mit $x<y$ gilt, dass $x\in A$.
Proposition. Es seien $M$, $N$ wohlgeordnete Mengen und $f,g\colon M\to N$ Ordnungsisomorphismen auf Anfangsstücke von $N$ (d.h. ordnungserhaltende injektive Abbildungen, deren Bilder Anfangsstücke von $N$ sind). Dann gilt $f=g$.
Beweis. Für jedes $x\in M$ gilt \[f(x)=\min\left\{y\in N\colon y>f(\tilde x)\text{ für alle }\tilde x<x\right\},\]denn sonst wäre $f$ nicht ordnungserhaltend oder $f[M]$ hätte eine „Lücke“ bei $\min\left\{y\colon y>f(\tilde x)\text{ f. a. }\tilde x<x\right\}$, wäre also kein Anfangsstück. Entsprechendes gilt für $g$. Wir sehen also: Ist $x\in M$ und $f(\tilde x)=g(\tilde x)$ für alle $\tilde x<x$, so ist \begin{multline*}f(x)=\min\left\{y\in N\colon y>f(\tilde x)\text{ für alle }\tilde x<x\right\}=\\=\min\left\{y\in N\colon y>g(\tilde x)\text{ für alle }\tilde x<x\right\}=g(x).\end{multline*} Damit hat $\{x\in M\colon f(x)\ne g(x)\}$ kein Minimum, muss also leer sein.
Diese Proposition ist ein Schritt im Beweis der folgenden. Zusammen sagen sie, dass der Begriff der Wohlordnung starrer ist als man vielleicht zunächst erwartet hätte.
Propostion. Seien $M$ und $N$ wohlgeordnete Mengen, so existiert ein Ordnungsisomorphismus von $M$ auf ein Anfangsstück von $N$ oder ein Ordnungsisomorphismus von $N$ auf ein Anfangsstück von $M$.
Beweis. Für $x\in M$ setzen wir $M_{\le x}:=\{\tilde x\in M\colon \tilde x\le x\}$ und entsprechend $M_{\lt x}$. Zunächst stellen wir fest, dass, wenn für jedes $x\in M$ ein Ordnungsisomorphismus $f_x\colon M_x\to N$ von $M_x$ auf ein Anfangsstück von $N$ existiert, ein Ordnungsisomorphismus von $M$ auf ein Anfangsstück von $N$ existiert. In diesem Falle gilt nämlich für $x_1<x_2$ aufgrund der Eindeutigkeit aus der letzten Proposition, dass $f_{x_2}|_{M_{x_1}}=f_{x_1}$. Daraus schließt man leicht, dass $x\mapsto f_x(x)$ einen Ordnungsisomorphismus von $M$ auf ein Anfangsstück von $N$ definiert.
Sei dies nun also nicht der Fall. Dann gibt es ein kleinstes $x\in M$, für das kein $f_x$ wie oben existiert. Das obige Argument auf $M_{<x}$ angewandt liefert einen Ordnungsisomorphismus $f$ von $M_{<x}$ auf ein Anfangsstück von $N$. Dieses Anfangsstück muss aber ganz $N$ sein. Sonst existierte nämlich $y=\mathrm{min}(N\setminus f[M_{<x}])$ und wir könnten $f$ durch $f(x):=y$ zu einem Ordnungsisomorphismus von $M_{\le x}$ nach $f[M_{<x}]\cup\{y\}$ fortsetzen, im Gegensatz zu der Annahme, dass ein solcher nicht existiert. Damit ist aber $f^{-1}$ ein Ordnungsisomorphismus von $N$ auf das Anfangsstück $M_{<x}$ von $M$.
Folgerung. Sind $A$ und $B$ Mengen, die sich wohlordnen lassen, so gilt $|A|\le |B|$ oder $|B|\le |A|$.
