Montag, 29. April 2013

Panorama 29. 4. 2013

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|$?

Wohlordnungen


Etwas ausführlicher habe ich das Folgende im Kapitel 7 dieses Skriptes beschrieben.

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.
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|$.

6 Kommentare:

  1. Was ist denn x im Beweis der vorletzten Proposition, wo f=g zu zeigen ist? Sind damit alle x aus M gemeint, wie am Anfang des Satzes? Das scheint mir so keinen Sinn zu ergeben.

    AntwortenLöschen
    Antworten
    1. Hallo, ich habe jetzt das Argument an einer Stelle etwas mehr ausgeführt und ein paar „$\in M$“ und „$\in N$“ eingefügt. Hilft das, oder ist es immer noch genau so unklar? Danke für die Rückmeldung!

      Löschen
    2. Hallo, ja, vielen Dank, das hat (mir) sehr geholfen.

      Jetzt irritiert mich nur noch, dass ein Ordnungs/ISO/morphismus f: M -> N per Definition nur injektiv sein muss, aber bei Isomorphismen erwartet man doch üblicherweise Bijektivität?

      Den Beweis der dritten Proposition verstehe ich prinzipiell, mir ist nur der Grund entfallen, warum wir einmal die Basis 3 verwenden. Dass wir in der zweiten Richtung die Basis 2 verwenden, ist klar, da wir ja 0-1-Folgen konstruieren wollen.

      Löschen
    3. Ein guter Punkt, dass das mit dem Ordningsiso missverständlich sein kann. Ich nehme an, dass „Ordnungsisomorphismus von M auf ein Anfangsstück von N“ eigentlich klar ist, dass aber das „$f\colon M\to N$“ dabei verwirren kann. Gemeint ist, dass der Isomorphismus zwischen $M$ und $f[M]$ besteht und letzteres ein Anfangsstück von $N$ ist.

      Wir hätten die Proposition auch formulieren können:
      Sind $N'$ und $N''$ Anfangsstücke von $N$, sowie $f\colon M\to N'$ und $g\colon M\to N''$ Ordnungsisomorphismen, so ist $N'=N''$ und $f=g$.

      Oder: Ist $M$ zu einem Anfangsstück von $N$ isomorph, so nur zu einem und nur auf eine Art.

      Löschen
    4. Zur Basis $3$: Die Abbildung $a\mapsto\sum_{k=0}^\infty 2^{-(k+1)}a_k$ wäre nicht injektiv, da beispielsweise $1, 0, 0, 0, \ldots$ und $0, 1, 1, 1, \ldots$ beide auf $\frac12$ abgebildet würden. Zur Basis $2$ ist ja $0.0\overline1=0.1$.

      Löschen
  2. Ah ja, das mit den Ordnungsisos verstehe ich jetzt und jetzt erinnere ich mich auch wieder an das Problem der Einserperioden aus der Vorlesung - erneut vielen Dank für die raschen und hilfreichen Antworten!

    AntwortenLöschen