Nun mit einigen Fehlern weniger: Mehr beweisbar Unbeweisbares.
Posts mit dem Label Mengenlehre werden angezeigt. Alle Posts anzeigen
Posts mit dem Label Mengenlehre werden angezeigt. Alle Posts anzeigen
Montag, 3. Juni 2013
Montag, 13. Mai 2013
Montag, 6. Mai 2013
Panorama 6. 5. 2013
Nach etwas Wiederholung und Zusammenfassung heute wenig Neues.
Folgerungen aus dem Auswahlaxiom
- Existiert eine Surjektion $f\colon B\to A$, so ist $|A|\le|B|$.
- Der Wohlordnungssatz.
- Der Basisexistenzsatz (in der linearen Algebra meist mit dem Zornschen Lemma bewiesen).
- Daraus die Existenz unstetiger Funktionen $f\colon\mathbb R\to\mathbb R$ mit $f(x+y)=f(x)+f(y)$ für alle $x,y\in\mathbb R$.
Den dazu in der Vorlesung erwähnten Aufsatz habe ich nun doch noch gefunden, es ist Hamel, G.: Eine Basis aller Zahlen und die unstetigen Lösungen der Funktionalgleichung: $f(x+y)=f(x)+f(y)$. Ich konnte feststellen, dass der Beweis der Existenz einer Basis dort der auch in dieser Vorlesung gegebene ist. Übrigens heißt in der Funktionalanalysis eine Vektorraumbasis im Sinne der linearen Algebra in Abgrenzung zu den dort betrachteten Basen eine Hamel-Basis. - Folgenstetigkeit impliziert Stetigkeit (z.B. für Abbildungen zwischen metrischen Räumen, wir hatten Abbildungen von $\mathbb R$ nach $\mathbb R$). Beim Beweis benötigt man nur eine abzählbare Auswahl.
- Die Existenz einer nicht Lebesgue-messbaren Menge reeller Zahlen. (Vitali, 1905)
Freitag, 3. Mai 2013
Zur Dimension des Vektorraums $K^{\mathbb N}$.
Wir wollen ein Diagonalargument finden, das beweist, dass der Vektorraum $K^{\mathbb N}$ der Folgen in einem beliebigen Körper $K$ keine abzählbare Basis besitzt. Ich skizziere hier knapp ein solches.
Für $n\in\mathbb N$ definieren wir die Projektionsabbildung\begin{align*}p_n\colon K^\mathbb N&\to K^n,\\u&\mapsto(u(0),\dots,u(n-1)).\end{align*}
Es sei $(v_i)_{i\in\mathbb N}$ ein linear unabhängiges System von Elementen von $K^\mathbb N$.
Wir definieren rekursiv eine streng monoton steigende Funktion Folge natürlicher Zahlen $(m_k)$, so dass $p_{m_k}(v_0),\dots,p_{m_k}(v_k)$ für alle $k\in\mathbb N$ linear unabhängig ist. Dazu sei $m_0:= 1+\min\left\{j\colon v_0(j)\ne0 \right\}$. Sei für ein $k\in\mathbb N$ bereits $m_k$ mit der geforderten Eigenschaft definiert. Sind $p_{m_k}(v_0),\dots,p_{m_k}(v_{k+1})$ bereits linear unabhängig setzen wir $m_{k+1}:=m_k+1$. Ansonsten existieren eindeutige $\lambda_j$ mit \[p_{m_k}(v_{k+1})=\lambda_0 p_{m_k}(v_0)+\dots+\lambda_k p_{m_k}(v_k).\]Wir setzen $m_{k+1}:=1+\mathrm{min}\left\{j\colon v_{k+1}(j)\ne \lambda_0 v_0(j)+\dots+\lambda_k v_k(j)\right\}$. Es ist $m_{k+1}>m_k$, und aufgrund der Eindeutigkeit der $\lambda_j$ ist \[p_{m_{k+1}}(v_{v_{k+1}})\notin\mathrm{span}\left\{p_{m_{k+1}}(v_0),\dots,p_{m_{k+1}}(v_k)\right\}.\] Daher hat die so definierte Folge $(m_k)$ die geforderten Eigenschaften.
Wir definieren nun ein $u\in K^{\mathbb N}$, so dass\[p_{m_{k+1}}(v_0),\dots,p_{m_{k+1}}(v_k),p_{m_{k+1}}(u)\]für alle $k\in{\mathbb N}$ linear unabhängig ist. Wir definieren rekursiv die Einträge $u(j)$ von $u$. Dies ist sinnvoll, da $p_{m_k}(u)$ nur von $u(j)$ mit $j<m_k$ abhängt.
Den Wert $u(j)$ für $j<m_0$ setzen wir beliebig (z.B. gleich $0$).
Es sei nun $k\in{\mathbb N}$ und $u(0),\dots,u(m_k-1)$ seien bereits definiert. Sind\[p_{m_k}(v_0),\dots,p_{m_k}(v_k),p_{m_k}(u)\]bereits linear unabhängig, so definieren wir $u(m_k),\dots,u(m_{k+1}-1)$ beliebig. Ansonsten existieren wie oben eindeutige $\lambda_j$, so dass\[p_{m_k}(u)=\lambda_0 p_{m_k}(v_0)+\dots+\lambda_k p_{m_k}(v_k).\]Wir definieren nun $u(m_k)$ so, dass \[u(m_k)\ne\lambda_0 v_0(m_k)+\dots+\lambda_k v_k(m_k)\]und $u(j)$ für $m_k<j<m_{k+1}$ beliebig. Dann ist\[p_{m_{k+1}}(u)\notin\mathrm{span} \{p_{m_{k+1}}(v_0),\dots,p_{m_{k+1}}(v_k)\},\]wobei wieder die Eindeutigkeit der $\lambda_j$ eingeht.
Es folgt, dass für alle $k$ die Vektoren $u,v_0,\dots,v_k$ linear unabhängig sind. Also sind die Vektoren\[u,v_0,v_1,v_2,\dots\]linear unabhängig. Damit ist $(v_j)_j$ keine Basis. Da das linear unabhängige System $(v_j)_j$ beliebig war, kann $K^{\mathbb N}$ keine abzählbar unendliche Basis besitzen. (Dass $K^{\mathbb N}$ nicht endlich-dimensional ist, folgt aus der Existenz des unendlichen linear unabhängigen System von Vektoren $(e_n)_{n\in{\mathbb N}}$ mit $e_n(j)=\delta_{j\, n}$.)
Wir definieren nun ein $u\in K^{\mathbb N}$, so dass\[p_{m_{k+1}}(v_0),\dots,p_{m_{k+1}}(v_k),p_{m_{k+1}}(u)\]für alle $k\in{\mathbb N}$ linear unabhängig ist. Wir definieren rekursiv die Einträge $u(j)$ von $u$. Dies ist sinnvoll, da $p_{m_k}(u)$ nur von $u(j)$ mit $j<m_k$ abhängt.
Den Wert $u(j)$ für $j<m_0$ setzen wir beliebig (z.B. gleich $0$).
Es sei nun $k\in{\mathbb N}$ und $u(0),\dots,u(m_k-1)$ seien bereits definiert. Sind\[p_{m_k}(v_0),\dots,p_{m_k}(v_k),p_{m_k}(u)\]bereits linear unabhängig, so definieren wir $u(m_k),\dots,u(m_{k+1}-1)$ beliebig. Ansonsten existieren wie oben eindeutige $\lambda_j$, so dass\[p_{m_k}(u)=\lambda_0 p_{m_k}(v_0)+\dots+\lambda_k p_{m_k}(v_k).\]Wir definieren nun $u(m_k)$ so, dass \[u(m_k)\ne\lambda_0 v_0(m_k)+\dots+\lambda_k v_k(m_k)\]und $u(j)$ für $m_k<j<m_{k+1}$ beliebig. Dann ist\[p_{m_{k+1}}(u)\notin\mathrm{span} \{p_{m_{k+1}}(v_0),\dots,p_{m_{k+1}}(v_k)\},\]wobei wieder die Eindeutigkeit der $\lambda_j$ eingeht.
Es folgt, dass für alle $k$ die Vektoren $u,v_0,\dots,v_k$ linear unabhängig sind. Also sind die Vektoren\[u,v_0,v_1,v_2,\dots\]linear unabhängig. Damit ist $(v_j)_j$ keine Basis. Da das linear unabhängige System $(v_j)_j$ beliebig war, kann $K^{\mathbb N}$ keine abzählbar unendliche Basis besitzen. (Dass $K^{\mathbb N}$ nicht endlich-dimensional ist, folgt aus der Existenz des unendlichen linear unabhängigen System von Vektoren $(e_n)_{n\in{\mathbb N}}$ mit $e_n(j)=\delta_{j\, n}$.)
Panorama 3. 5. 2013
Zwischenspiel zu Vektorräumen und Basen
Existiert eigentlich zu jedem Vektorraum eine Basis? Und was heißt dabei „existiert“? Im ersten Semester wurde vielleicht berichtet (oder gar mit Hilfe des Zornschen Lemmas bewiesen?), dass das so sei, vielleicht aber mit einer Warnung. Auf jeden Fall wissen wir, dass das für endlich erzeugte gilt, und ein mögliches Argument dafür lässt sich auf unendliche Indexmengen verallgemeinern, sofern diese wohlgeordnet sind.
Proposition. Es sei $V$ ein Vektorraum, $I$ eine wohlgeordnete Indexmenge und $(v_i)_{i\in I}$ ein Erzeugendensystem von $V$. Dann ist mit $J:=\left\{j\in I\colon v_j\notin\mathrm{span}\{v_i\colon i<j\}\right\}$ das Teilsystem $(v_j)_{j\in J}$ eine Basis von $V$.
Beweis. Die lineare Unabhängigkeit von $(v_j)_{j\in J}$ ist leicht zu sehen. Um zu sehen, dass $(v_j)_{j\in J}$ immer noch Erzeugendensystem ist, zeigen wir für alle $i\in I$ per Induktion (über die Wohlordnung $I$, vergleichen Sie die ausführlichere Formulierung aus der Vorlesung!), dass $v_i\in\mathrm{span}\{v_j\colon j\in J,\ j\le i\}$. Für $i\in J$ ist das klar. Ist $i\notin J$, so ist $v_i\in\mathrm{span}\{v_k\colon k<i\}$. Per Induktion gilt für $k<i$, dass $v_k\in\mathrm{span}\{v_j\colon j\in J,\ j\le k\}$. Es folgt die Behauptung.
Übung. Zeigen Sie an einem Beispiel, dass die Aussage scheitern kann, wenn $I$ eine totale Ordnung trägt, die keine Wohlordnung ist.
Ein interessantes Beispiel ist die Frage, ob $\mathbb R$ als $\mathbb Q$-Vektorraum aufgefasst eine Basis hat, und wie eine solche aussehen würde.
Da für jeden Vektorraum die Menge aller Vektoren (mit sich selbst indiziert) ein Erzeugendensystem ist, können wir festhalten:
Proposition. Existiert eine Wohlordnung auf $\mathbb R$, so hat $\mathbb R$ eine $\mathbb Q$-Basis.
Und wir wissen auch, dass eine solche Basis überabzählbar sein muss.
Proposition. $\mathbb R$ hat keine abzählbare $\mathbb Q$-Basis.
In der Tat gilt:
Proposition. Ist $V$ ein Vektorraum über einem abzählbaren Körper $K$, und sind $v_n\in V$, $n\in\mathbb N$ Vektoren, so ist die Menge $\mathrm{span}\{v_n\colon n\in\mathbb N\}$ abzählbar.
Was für Konsequenzen hat aber die Existenz einer $\mathbb Q$-Basis von $\mathbb R$? Zum Beispiel die folgende.
Proposition. Hat $\mathbb R$ eine $\mathbb Q$-Basis, so existiert eine unstetige Abbildung $f\colon\mathbb R\to\mathbb R$ mit $f(x+y)=f(x)+f(y)$ für alle $x,y\in\mathbb R$.
Konstruktion. Man definiert zu einer gegebenen Basis eine $\mathbb Q$-lineare Abbildung $f\colon\mathbb R\to\mathbb R$, indem man jedes Basiselement auf $1$ abbildet. Das Bild dieser Abbildung ist $\mathbb Q$, sie kann also nicht stetig sein, da sonst der Zwischenwertsatz verletzt würde.
Ein weiterer scheinbar einfacher Vektorraum ist für einen beliebigen Körper $K$ der Raum $K^{\mathbb N}$ aller $K$-Folgen. Da dieser nie abzählbar ist (es ist ja schon $\left|\{0,1\}^{\mathbb N}\right|>|\mathbb N|$), folgt aus obigem, dass er für abzählbares $K$ keine abzählbare Basis hat. Dies ist in der Tat auch für einen beliebigen Körper $K$ richtig. Ein Diagonalargument, das das zeigt, haben wir vorbereitet und als Übungsaufgabe gelassen. Einige Hinweise dazu gebe ich hier noch einmal in einem gesonderten Eintrag.
Der Wohlordnungssatz und das Auswahlaxiom
Wir sehen, dass die Existenz von Wohlordnungen interessante Auswirkungen hat. Cantor hat als Prinzip angenommen, dass jede Menge wohlgeordnet werden kann. Klarer wurde die Situation mit Ernst Zermelos Arbeit „Beweis, daß jede Menge wohlgeordnet werden kann.“ aus dem Jahr 1904. Darin beweist er folgendes.
Satz. Es sei $M$ eine Menge und $\gamma\colon\mathcal P(M)\setminus\{Ø\}\to M$ eine Funktion mit $\gamma(S)\in S$ für alle $S$. Dann existiert genau eine Wohlordnung auf $M$, für die $a=\gamma\left(M\setminus M_{<a}\right)$ für alle $a\in M$ gilt.
Dabei ist wie zuvor $M_{<a}=\{x\in M\colon x\lt a\}$.
Übung. Angenommen $M=\mathbb N$ und $\gamma(\{0\})=0$, $\gamma(S)=\mathrm{min}(S\setminus\{0\})$ sonst. Wie sieht dann die zugehörige Wohlordnung aus?
Insbesondere existiert also überhaupt eine Wohlordnung auf $M$, sofern eine solche Auswahlfunktion existiert, die jeder nicht-leeren Teilmenge von $M$ eines ihrer Elemente zuordnet. Zermelo schreibt, diese Aussage ließe sich nicht auf einfachere zurückführen, werde aber auch anderswo in der Mathematik frei angewandt. Wir nennen Sie heute das Auswahlaxiom (Axiom of Choice):
AC. Ist $\mathfrak S$ eine Menge von nicht-leeren Mengen, so existiert eine Funktion $f\colon \mathfrak S\to\bigcup\mathfrak S$ mit $f(S)\in S$ für alle $S\in\mathfrak S$.
Eine Konsequenz des Auswahlaxioms ist also der Wohlordnungssatz, der besagt, dass auf jeder Menge eine Wohlordnung existiert. Damit ist mit obigem der Basisexistenzsatz, der besagt, dass jeder Vektorraum eine Basis hat, eine weitere. Mit weiteren Konsequenzen dieses Axioms werden wir uns in der Folge beschäftigen.
Übung. Andererseits folgt in der Situation des Auswahlaxioms aus der Existenz einer Wohlordnung auf $\bigcup\mathfrak S$ leicht die Existenz der Auswahlfunktion $f$. Wie?
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|$?
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|$.
Freitag, 26. April 2013
Panorama 26. 4. 2013
Noch einmal Fundamentalsatz der Algebra
Wir haben uns noch den Beweis von Argand in «Essai sur une manière de représenter les quantités imaginaires dans les constructions géométriques» (1874), Abschnitt 31 (S. 58-59), angesehen. Wir kannten ihn schon aus einer modernen Darstellung im Königsberger, Analysis I. Im Vergleich fiel auf:
- Argand zeigt, dass ein nicht konstantes Polynom in keiner komplexen Zahl, bei der es nicht verschwindet, ein Betragsminimum haben kann. Das aber überhaupt das Betragsminimum angenommen wird, wird nicht problematisiert.
- Argand setzt noch Variablen auf unendlich kleine Werte.
- Argand betrachtet explizit nur den Fall, dass der lineare Term der Entwicklung des Polynoms in dem betrachteten Punkt nicht verschwindet, und schreibt, ansonsten gehe es durch Betrachten des nächsten nicht verschwindenden Terms ebenso, obwohl man argumentieren kann, dass letzter Fall gerade der Interessante ist.
Zwischenspiel zum Unendlichen
Als Beispiel für das Unendliche in der Mathematik haben wir uns den Satz von Euklid, dass es unendlich viele Primzahlen gibt, mit dem üblichen Beweis angesehen. Es ist zu beachten, dass man dabei gar nicht von unendlichen Mengen reden muss, es wird gezeigt, dass es zu endlichen vielen Primzahlen immer noch eine weitere gibt.
Mengenlehre
Während wir gewohnt sind, beispielsweise Kurven in der Ebene als Punktmengen aufzufassen, scheint diese Vorstellung bei Gauß noch nicht vorhanden gewesen zu sein. Die Mengenlehre wie wir sie kennen wurde von Georg Cantor (1845-1918) ab 1872 begründet. Ich habe seine Arbeit „Ueber eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen“ mit nur leicht modifiziertem Beweis präsentiert. Er gibt dort einen neuen Beweis für den Satz, dass es in jedem Intervall reeller Zahlen eine transzendente Zahl gibt. Dazu zeigt er:
- Es gibt eine Folge $(a_n)_n$ algebraischer Zahlen, in der jede algebraische Zahl vorkommt.
- Ist $(a_n)_n$ eine Folge reeller Zahlen und $(l,r)$ ein Intervall in $\mathbb R$, $l<r$, so existiert ein $x\in(l,r)$, so dass $x\ne a_j$ für alle $j$.
Er zeigt also, in heutigen Begriffen, die Cantor eben dort zu entwickeln begann, dass die Menge der algebraischen Zahlen abzählbar ist, ein Intervall reeller Zahlen aber nicht. Der Beweis des zweiten Aussage benutzt wesentlich die Vollständigkeit der reellen Zahlen. (Es ist nicht das bekannte Diagonalargument, an das wir in der nächsten Sitzung noch einmal erinnern werden.)
Abonnieren
Posts (Atom)