Algebraische Topologie: Dritte Woche

Dieses war eine kurze Woche, und da es momentan doch ein Skript gibt, gibt es hier auch wenig zu sagen. Den zweiten Abschnitt habe ich auf das tatsächlich behandelt zusammengekürzt, was auch thematisch ganz gut passt. Passend zu der halben Woche habe ich auch einen ungefähr halben Aufgabenzettel erstellt.

Ein komischer Kegel

Da wir leider nicht mehr dazu gekommen sind, die letzte Aufgabe zu besprechen, aber anscheinend einige an ihr herumgeknobelt hatten, möchte ich hier kurz eine Lösung angeben.

In der Aufgabe ging es darum zu sehen, dass für $M\subset\mathbb R^n$ der abstrakt definierte Kegel $CM$ nicht immer homöomorph zu \[\left\{((1-t)x,t)\in\mathbb R^{n+1}\colon x\in M,\,t\in I\right\}\] ist, wie man vermuten könnte. Für kompaktes $M$ zeigen wir leicht, dass die Räume homöomorph sind, aber schon für $M=\mathbb N\subset\mathbb R$ sind sie es nicht, das zu zeigen war Teil der Aufgabe. In der Tat ist $C\mathbb N$ zu keiner Teilmenge eines euklidischen Raumes homöomorph.

Ist $x$ ein Punkt eines metrischen Raumes $X$, so enthält jede Umgebung von $x$ einen $\frac1n$-Ball um $x$. Für die Spitze des Kegels $C\mathbb N$ werden wir aber zeigen, dass es kein abzählbares System von Umgebungen gibt, so dass jede Umgebung der Spitze eine Umgebung aus diesem System enthält. $C\mathbb N$ kann damit zu keinem metrischen Raum homöomorph sein. Wir sagen, $X$ sei nicht metrisierbar.

Nun zum Beweis. Es sei $p\colon \mathbb N\times I\to C\mathbb N$ die Quotientenabbildung. Die Kegelspitze bezeichnen wir mit $\ast$, es ist also $p[\mathbb N\times\{1\}]=\{\ast\}$. Es sei $(U_n)_{n\in\mathbb   N}$ eine abzählbare Familie von Umgebungen von $\ast$. Wir wollen eine Umgebung $V$ von $\ast$ finden, so dass $U_n\setminus V\ne\emptyset$ für alle $n$. Dies leistet eine einfache Diagonalkonstruktion.  Für $n\in\mathbb N$ ist $p^{-1}[U_n]$ Umgebung von $(n,1)\in\mathbb N\times I$, also existiert $\varepsilon_n>0$, so dass $\{n\}\times (1-2\varepsilon_n,1]\subset p^{-1}[U_n]$. Ein solches wählen wir für jedes $n$ und setzen $\tilde V:=\bigcup_{n\in\mathbb    N}\{n\}\times(1-\varepsilon,1]$ und $V:=p[\tilde V]$. Es ist $p^{-1}[V]=\tilde V$ offen, also $V$ Umgebung von $\ast$. Für jedes $n$ ist aber $(n,1-\varepsilon)\in p^{-1}[U_n\setminus V]$. Das zeigt die Behauptung.

Algebraische Topologie: Zweite Woche

Wir haben uns am Dienstag der zweiten Woche weiter mit Quotiententopologien beschäftigt.  Das Ziel war, zu sehen, wie man mit diesen in einfachen Argumenten umgeht. So haben wir gezeigt, dass der Kegel über einer $n$-Sphäre ein $(n+1)$-Ball ist. Das ist geometrisch keine große Erkenntnis, man sollte es eher so sehen, dass der Begriff des Kegels, den wir eingeführt haben, und der vielleicht etwas abstrakt schien, wenn man wenig Erfahrung mit Topologien hat, der richtige ist. Außerdem haben wir projektive Räume Sphären, auf denen antipodale Punkte identifiziert werden, eingeführt und gesehen, dass man sie auch erhalten kann, indem man antipodale Punkte auf dem Rand eines Balles identifiziert.

Zum Schluss habe ich noch auf ein technisches Lemma hingearbeitet, zu dem ich aber nicht mehr gekommen bin. Das hat uns aber eine Gelegenheit gegeben, ein wenig über Produkte und Kompaktheit zu reden.

Wie angekündigt habe ich den bisherigen Stoff aufgeschrieben, beziehungsweise zusammenkopiert. Hier ist er: Abschnitt 1, Quotienten.

Dazu habe ich auch einige Grundlagen zur mengentheoretischen Topologie aus einem alten Skript zusammengetragen: Abschnitt 0, Präliminarien. 

Durch das Zusammenkopieren kann es zu Inkonsistenten gekommen sein. Diese Präliminarien sind nicht als Voraussetzungen an die Hörer zu verstehen, sondern als gemeinsame Quelle, um Grundlagen nachzuschlagen.

Das oben erwähnte am Dienstag noch nicht vorgekommene technische Lemma hat es dennoch bereits in den ersten Abschnitt geschafft (1.27) und wir nächsten Dienstag behandelt werden. Die auf dem Weg dorthin gezeigte Aussage über Projektionen mit kompakter Faser hat aber ihren Platz in Abschnitt 0 gefunden (0.63),

Algebraische Topologie: Erste Woche

Nach einem Ausblick auf die Themen dieses Semesters haben wir uns einigen topologischen Grundbegriffen zugewandt.

Von Grundlagen über topologische Räume, Unterräume, Produkte, Kompaktheit und Zusammenhang nehme ich an, dass sie im wesentlichen bekannt sind, ich bemühe mich aber, an einige zu erinnern, wenn sich die Gelegenheit anbietet. Zum Nachlesen kann ich die ersten beiden Kapitel meines Skripts zu einer Topologievorlesung an der TU Berlin anbieten. Außerdem kann ich Kapitel 6 von Bröckers „Analysis I“ empfehlen. Falls dies nicht genügt und ich zu schnell bin, bitte ich um freundlichen Protest.

Angefangen habe ich mit dem Begriff des Quotientenraums. Was ich darüber erzähle wird eine verkürzte Fassung des siebenten Kaptitels des genannten Skripts sein.

Ebenfalls hatten wir bereits den Begriff der Homotopie. Das entspräche in dem alten Skript 8.1, 8.2, 8.3, 8.6, 8.7.

Algebraische Topologie im Wintersemester 2013/14

Hier werde ich mindestens wöchentlich kurz etwas zur Vorlesung „Algebraische Topologie“ schreiben. Kommentare und Fragen zu dem Stoff sind willkommen, rein organisatorische Fragen zur Vorlesung werden aber besser direkt an mich gerichtet.

Anonyme Kommentare sind nicht möglich, gegen pseudonyme habe ich aber nichts einzuwenden.

Ich werde die Blogposts zur Vorlesung mit AlgTop1314 kennzeichnen.

Panorama 17. 6. 2013

Noch einmal eine Zusammenfassung des Teils dieser Sitzung, der der Wiederholung und Diskussion der Gödelschen Unvollständigkeitssätze gewidmet war. Dies enthält nun wieder ein paar Feinheiten, die das ganze vielleicht schwieriger erscheinen lassen als es ist. Außer allen Sätzen sind vor allem die Teile in Fettdruck wichtig.

Wir haben uns noch einmal mit den Gödelschen Unvollständigkeitssätzen beschäftigt. Die einfachste Form, die wir formuliert hatten, war:

Satz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und $\mathcal N\models X$, so ist $X$ unvollständig.

Dabei ist $X$ eine Menge von Aussagen in der Sprache der Arithmetik. Nun ist eine solche Aussage zunächst ein rein syntaktisches Gebilde, es ist erst nach Interpretation der Aussage sinnvoll, davon zu reden, ob sie wahr oder falsch ist. Aussagen in der Sprache der Arithmetik können wir aber immer als Aussagen über natürliche Zahlen interpretieren und damit wahr oder falsch nennen. Wenn wir $\mathcal N\models X$ schreiben, so heißt dies gerade, dass alle Aussagen aus $X$ so interpretiert wahr sind. Wenn wir das so verstehen, können wir auch schreiben:

Satz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und enthält $X$ nur wahre Aussagen, so existiert eine wahre Aussage, die sich nicht aus $X$ ableiten lässt.

Der Beweis hiervon lässt sich einfacher skizzieren als ich das in einer früheren Sitzung getan hatte: Es ist möglich, eine Aussage $\gamma$ zu konstruieren, die gerade sagt, dass $\gamma$ nicht aus $X$ ableitbar ist. Wäre $\gamma$ falsch, so ließe sich $\gamma$ also ableiten, es ließe sich aus $X$ also eine falsche Aussage ableiten, was im Widerspruch dazu steht, dass $X$ nur wahre Aussagen enthält. Damit ist $\gamma$ also wahr und nicht aus $X$ ableitbar.

Eigentlich möchte man aber nicht nur über Mengen wahrer Aussagen sprechen. Redet man vom ersten Gödelschen Unvollständigkeitssatz meint man meist eine Form des folgenden, auch wenn dies eigentlich eine Verstärkung des Satzes durch Rosser ist.

Satz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und konsistent, so ist $X$ unvollständig.

Es gibt also eine Aussage, so dass weder diese Aussage noch ihre Negation aus $X$ ableitbar sind. Aber Achtung: Dies muss nicht auf unsere oben konstruierte Aussage $\gamma$ zutreffen, Rossers Konstruktion ist eine andere. Wer in einer populären Darstellung also diese starke Fassung formuliert, dann aber zum Beweis einen Satz der Art „ich bin nicht beweisbar“ vorbringt, der schummelt.

Durchaus aber folgt für die Aussage $\gamma$ von oben, dass $X$ inkonsistent ist, wenn $\gamma$ aus $X$ ableitbar ist. (Wenn $\gamma$ aus $X$ ableitbar ist, so ist diese Tatsache auch in $X$ beweisbar, das heißt $\neg\gamma$ ist aus $X$ ableitbar.)  Das heißt aber, dass $X$ genau dann konsistent ist, wenn $\gamma$ nicht aus $X$ ableitbar ist, was wiederum die Aussage von $\gamma$ ist. Die Grundlage des Beweises des zweiten Gödelschen Unvollständigkeitssatzes ist nun, dass sich die Äquivalenz von $\gamma$ und $Con_X$ (der Konsistenz von $X$) auch in $X$ beweisen lässt. Dies liefert:

Zweiter Gödelscher Unvollständigkeitssatz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und konsistent, so ist $Con_X$ nicht aus $X$ ableitbar.

Betrachten wir ein Beispiel: PA selbst ist konsistent. Dies liegt daran, dass PA ein Modell hat, nämlich das Standardmodell $\mathcal N$. Kurz: PA enthält nur wahre Aussagen. (Dies ist ein Beweis der Konsistenz von PA, den wir in „unserer Mathematik“ geführt haben, in der es ja die Menge der natürlichen Zahlen gibt. Dies ist also ein Beweis der Konsistenz von PA in ZF. Keine Unvollstänidgkeitssätze wurden verletzt.) Also ist $Con_{\mathrm{PA}}$ nicht in PA beweisbar. Das heißt aber, dass $X:=\mathrm{PA} + \neg Con_{\mathrm{PA}}$ konsistent ist. (Wäre $X$ inkonsistent, so ließe sich aus $\mathrm{PA} + \neg Con_{\mathrm{PA}}$ ein Widerspruch herleiten, die Aussage $Con_{\mathrm{PA}}$ wäre also in PA per Widerspruch beweisbar.) $X$ ist also eine konsistente Theorie, die eine falsche Aussage enthält (wobei falsch wie gesagt nur bedeutet, dass sie im Standardmodell $\mathcal N$ nicht gilt). Wir wissen insbesondere, dass auch $X$ unvollständig ist. Aber: Ist $\gamma$ die Aussage, die behauptet, dass $\gamma$ in $X$ nicht beweisbar ist, so ist $\gamma$ wie gehabt äquivalent zu $Con_X$. Da $Con_X$ aber $Con_{\mathrm PA}$ impliziert, ist $\neg\gamma$ aus $X$ ableitbar. $X$ ist also konsistent, behauptet aber seine eigene Inkonsistenz.

All das gilt wie schon früher bemerkt nicht nur für die Sprache der Arithmetik und PA, sondern wo immer man genug Mathematik nachbilden kann, um sinnvoll über Beweisbarkeit zu reden. Insbesondere gilt das für die Sprache der Mengenlehre und ZF, also:

Satz.  Ist $X\supset\mathrm{ZF}$ rekursiv aufzählbar und konsistent, so ist $X$ unvollständig und $Con_X$ nicht aus $X$ ableitbar.

Wir müssen hier nur aufpassen: Im Gegensatz zu der Situation bei PA dürfen wir hier nicht einfach „in ZF lässt sich die Konsistenz von ZF nicht beweisen“ behaupten. Dass es überhaupt eine Aussage gibt, die sich in ZF nicht beweisen lässt, heißt ja, dass ZF konsistent ist. Hätten wir tatsächlich einen Beweis dieser Tatsache, den wir in unserer üblichen Mathematik, also in ZFC, geführt hätten, so würde also ZFC die Konsistenz von ZF beweisen. Von Gödel wissen wir aber (das wurde in einer früheren Sitzung berichtet), dass wenn ZF konsistent ist, auch ZFC konsistent ist. ZFC würde also seine eigene Konsistenz beweisen, was nach dem zweiten Gödelschen Unvollständigkeitssatz nur möglich ist, wenn ZFC inkonsistent ist, was wir doch nicht hoffen wollen. Wir müssen also genau sein und sagen: „Wenn ZF konsistent ist, lässst sich in ZF die Konsistenz von ZF nicht beweisen.“

Panorama 10. und 14. 6. 2013

Neben einigen Eiederholungen und sonstigem haben wir mit Hilfe der Eulerschen Polyederformel den Satz von Sylvester-Gallai und den Satz von Pick bewiesen. Da ich in beidem weiterhin eng dem Buch von Aigner und Ziegler gefolgt bin, verzichte ich hier darauf, die Beweise aufzuschreiben.

Panorama 7. 6. 2013

Wir haben über die Eulersche Polyederformel geredet. Wir sind dabei fast vollständig dem entsprechenden Kapitel in Aigners und Zieglers „Das Buch der Beweise“ gefolgt.
Formuliert haben wir sie wie folgt.

Satz. Es sei $G$ ein zusammenhängender ebener Graph mit $n$ Ecken, $e$ Kanten und $f$ Flächen (oder Ländern) inklusive der äußeren. Dann ist \[n-e+f=2.\]
Der angegebene Beweis ist der erste dieser 20.

Als Beispiel haben wir gesehen, dass ein Polyeder aus $k$ Dreiecken und $l$ Vierecken, bei dem an jeder Ecke drei Flächen zusammenstoßen. $3k+2l=12$ erfüllen muss. Dies folgte aus der Eulerformel sowie $f=k+l$, $2e=3n$ (doppeltes Abzählen der Ecken-Kanten-Inzidenzen) und $2e=3k+4l$ (doppeltes Abzählen der Kanten-Flächen-Inzidenzen).

Ebenfalls haben wir gesehen, dass der Graph $K_{3,3}$ nicht planar ist. Dies folgte daraus, dass $n=6$, $e=9$ und $2e\ge4f$ (doppeltes Abzählen der Kanten-Flächen-Inzidenzen zusammen damit, der jeder Kreis in $K_{3,3}$ mindestens Länge $4$ hat) im Widerspruch zur Euler-Formel steht.

Panorama 3. 6. 2013

Nun mit einigen Fehlern weniger: Mehr beweisbar Unbeweisbares.

Panorama 31. 5. 2013

Abschluss Unabhängigkeitssätze
Den zweiten Unvollständigkeitssatz habe ich noch einmal umformuliert.

Panorama 24. und 27. 5. 2013

Der erste Gödelsche Unvollständigkeitssatz

Alles technische habe ich dem bereits erwähnten Lehrbuch von Rautenberg entnommen.
Eine nicht-technische Darstellung des Beweises findet sich in dem Buch von Franzén, das sich auch mit der Rezeption des Satzes außerhalb der Mathematik beschäftigt.

Wir haben zunächst die Peano-Axiome im Rahmen der Mengenlehre formuliert. Diese beschreiben die natürlichen Zahlen mit der Nachfolgeroperation bis auf Isomorphie eindeutig, was in Aufgabe 21 gezeigt wurde.

Wir haben dann die Peano-Arithmetik als Theorie erster Ordnung (also in der Prädikatenlogik erster Stufe) eingeführt. Diese ist in der Sprache der Arithmetik $\mathcal L_{\mathrm{ar}}$ formuliert, die ein Konstantenymbol $0$ sowie Funktionssymbole $S$ (Nachfolger), $+$ und $\cdot$ enthält. Aus dem Rautenberg:

Peano-Arithmetik PA

Dabei ist zu beachten, dass das Induktionsschema für jede Formel $\varphi$ ein Axiom liefert, das Axiomensystem $\mathrm{PA}$ ist also unendlich. Dennoch lässt sich von einer gegeben Formel „mechanisch“ feststellen, ob sie eines der Axiome von $\mathrm{PA}$ ist, das wird noch wichtig sein.

Das Standardmodell $\mathcal N$ von $\mathrm{PA}$, also in gewisser Hinsicht das beabsichtige Modell, besteht aus der Menge der hatürlichen Zahlen $\mathbb N$ zusammen mit der Null, sowie der üblichen Nachfolgeroperation, Addition und Multiplikation. Da $\mathrm{PA}$ ein Modell hat, haben wir also sofort (mit dem Korrektheitssatz) den

Satz. $PA$ ist konsistent.

Man muss ein wenig arbeiten, um das einzusehen, aber in $\mathrm{PA}$ lassen sich tatsächlich alle elementaren Zahlentheoretischen Beweise durchführen, sowie ein guter Teil der diskreten Mathematk. $\mathrm{PA}$ taugt damit als Repräsentant für finitistische Mathematik.

Für jede natürliche Zahl $n\in\mathbb N$ definieren den die entsprechende Zahl bezeichnenden Term $\underline n:=\underbrace{SS\cdots S}_{n}0$. Als Warnung und im Gegensatz zu Aufgabe 21 weisen wir auf die Existenz von Nichtstandardmodellen hin.

Satz. Es gibt ein Modell $\mathcal M$ von $\mathrm{PA}$, das außer $\left(\underline n\right)^{\mathcal M}$, $n\in\mathbb N$, noch weitere Elemente hat.

Auf den Beweis, der eine leichte Anwendung des Vollständigkeitssatzes ist, haben wir verzichtet. Der Interessierte findet dies als Satz 3.2 bei Rautenberg.

Das Induktionsschema leistet also nicht, was wir vielleicht erwartet hätten. Das mag zunächst verwundern, deutet aber bereits in Richtung des Unvollständigkeitssatzes.

Daraus, dass aber das Standardmodell nur die von $\underline n$ bezeichneten Elemente enthält, erhält man aber folgendes.

Satz/Definition. Es sei $\varphi=\varphi(x)\in\mathcal L_{\mathrm{ar}}$. Gilt $\mathrm{PA}\vdash\exists x\varphi(x)$, so existiert ein $n\in\mathbb N$ mit $\mathrm{PA}\not\vdash\neg\varphi(\underline n)$. Wir sagen, $\mathrm{PA}$ sei $\omega$-konsistent.

Beweis. Sonst gölte $\mathcal N\models\exists x\varphi(x)$, aber $\mathcal N\models\neg\varphi(\underline n)$ für alle $n\in\mathbb N$.

Wir wollen nun als eine Instanz des Gödelschen Unvollständigkeitssatzes skizzieren, dass $\mathrm{PA}$ unvollständig ist, dass also eine Aussage $\gamma\in\mathcal L_{\mathrm{ar}}$ mit $\mathrm{PA}\not\vdash\gamma$ und $\mathrm{PA}\not\vdash\neg\gamma$ existiert. Der Beweis basiert nun darauf, dass der Begriff der Ableitbarkeit in $\mathrm{PA}$ sich arithmetisch (also als Aussage über das Rechnen mit natürlichen Zahlen) formulieren lässt, und dass sich genug Tatsachen darüber in $\mathrm{PA}$ beweisen lassen.

Zunächst führt man ein Schema ein, nachdem man jeder Formel $\gamma$ injektiv eine Gödelnummer $n\in\mathbb N$ zuordnet. Wir schreiben dafür dann $\dot\gamma=n$ und $\lceil\gamma\rceil=\underline n$. Ebenso ordnen wir jeder potentiellen Herleitung einer Formel (man denke an etwas, das aussieht wie die lange Folge von Zeilen in Aufgabe 22. Dieses soll so sein, dass sich auch Formel $bew(n,m)$ angeben lässt, die „sagt“, dass $n$ Gödelnummer eines Beweises einer Formel mit Gödelnummer $m$ ist. Und in der Tat soll sich, wenn das der Fall ist, das auch in $PA$ herleiten lassen. Dies ist zu erreichen, da das Testen, ob etwas eine Herleitung ist, ja tatsächlich rein mechanisch möglich ist (man denke wieder an Aufgabe 22), und wie oben bereits behauptet sich solche Argumente in $\mathrm{PA}$ durchführen lassen. Natürlich wäre hier einiges zu zeigen. Wir können aber genau sagen, was wir erreichen wollen, nämlich, dass für jede jede Formel $\varphi$ die folgenden Implikationen gelten, wobei wir noch $bwb(m):=\exists n\,bew(n,m)$ setzen:\begin{align*}\mathrm{PA}\ \vdash\ \varphi\quad&\Rightarrow\quad\text{Ex. $n\in\mathbb N$ mit $\mathrm{PA}\vdash bew(\underline n,\lceil\varphi\rceil)$}\\&\Rightarrow\quad\mathrm{PA}\vdash bwb(\lceil\varphi\rceil),\\\mathrm{PA}\not\vdash\varphi\quad&\Rightarrow\quad\mathrm{PA}\vdash\neg bew(\underline n,\lceil\varphi\rceil)\text{ f.a. $n\in\mathbb N$}.\end{align*}Nächstes Ziel ist nun, eine Aussage $\gamma$ zu finden, die von sich selber behauptet, nicht in PA beweisbar zu sein. Genauer wollen wir\[\mathrm{PA}\vdash\,\gamma\leftrightarrow\neg bwb(\lceil\gamma\rceil).\]Für eine solche Aussage gilt in der Tat weder $\mathrm{PA}\vdash\gamma$ noch $\mathrm{PA}\vdash\neg\gamma$. Aus ersterem folgte nämlich einerseits aufgrund der Eigenschaft von $\gamma$, dass $\mathrm{PA}\vdash\neg bwb(\lceil\gamma\rceil)$ und andererseits aufgrund einer Eigenschaft von $bwb$, dass $\mathrm{PA}\vdash bwb(\lceil\gamma\rceil)$. Dies widerspräche der Konsistenz von $\mathrm{PA}$. Aus $\mathrm{PA}\not\vdash\gamma$ folgt nun aber nach obigem $\mathrm{PA}\vdash\neg bew(\underline n,\lceil\gamma\rceil)$ für alle $n\in\mathbb N$, was aufgrund der $\omega$-Konsistenz von $\mathrm{PA}$ impliziert, dass $\mathrm{PA}\not\vdash \exists n\,bew(n,\lceil\gamma\rceil)$, also nach Definition von $bwb$ und der Eigenschaft von $\gamma$ auch $\mathrm{PA}\not\vdash\neg\gamma$.

Die Frage ist nun also, wie man an eine solche Aussage $\gamma$ kommt, die etwas über sich selbst behauptet. Gödels Trick benutzt nun textuelle Ersetzung. Später hat Quine folgendes natürlichsprachliche Analogon angegeben:

„ergibt einen unbeweisbaren Satz, wenn man ihm sein Zitat voranstellt.“ ergibt einen unbeweisbaren Satz, wenn man ihm sein Zitat voranstellt.

Dieser Satz sagt von einem anderen, dass er unbeweisbar sei, und dieser andere ist aber gleich ihm selbst. Dabei entspricht das Zitieren mit Anführungszeichen dem Zitieren via Gödelnummer. Auf der technischen Seite zeigt man, dass es man eine Formel $sb(m,n,y)$ konstruieren kann, die sagt, dass $y$ die Gödelnummer der Formel ist, die man erhält, wenn man in der Formel mit Gödelnummer $m$ die Variable $x$ durch $\underline n$ ersetzt, genauer wollen wir für alle Formeln $\varphi=\varphi(x)$ und $n\in\mathbb N$\[PA\,\vdash\,sb(\lceil\varphi\rceil,\underline n,y)\leftrightarrow y=\lceil\gamma(\underline n)\rceil.\]Weiterhin setzt man nun $\beta(z):=\forall y(sb(z,z,y)\rightarrow\neg bwb(y))$ („Die Aussage, die man erhält, wenn man in die Formel mit Gödelnummer z für die Variable x gerade z einsetzt, ist nicht beweisbar“) und $\gamma:=\beta(\lceil\beta\rceil)$. So erhält man in der Tat\begin{align*}\mathrm{PA}\quad&\vdash\quad\gamma\leftrightarrow\forall y(y=\lceil\beta(\lceil\beta\rceil)\rceil\rightarrow\neg bwb(y)),\\\mathrm{PA}\quad&\vdash\quad\gamma\leftrightarrow\neg bwb(\lceil\beta(\lceil\beta\rceil)\rceil),\\\mathrm{PA}\quad&\vdash\quad\gamma\leftrightarrow\neg bwb(\lceil\gamma\rceil).\end{align*}Damit sind wir am Ziel angelangt.

Satz (Gödel). Für obige Aussage $\gamma\in\mathcal L_{\mathrm{ar}}$ gilt $\mathrm{PA}\not\vdash\gamma$ und $\mathrm{PA}\not\vdash\neg\gamma$. PA ist also unvollständig.

Wenn $\gamma$ in PA weder beweisbar noch widerlegbar ist, ist es dann trotzdem sinnvoll zu fragen, ob $\gamma$ wahr ist? In der Tat ist im allgemeinen in der Prädikatenlogik nur sinnvoll von Beweisbarkeit aus einer Formelmenge (wie hier PA) oder Wahrheit in einem Modell zu reden. Nun hat aber PA das Standardmodell $\mathcal N$, und wir können fragen, ob $\gamma$ in diesem erfüllt ist. Der Beweis zeigt, dass das tatsächlich dann der Fall ist, wenn $\gamma$ in PA nicht beweisbar ist.

Bemerkung. Für dieses $\gamma$ gilt $\mathcal N\models\gamma$. In diesem Sinne ist $\gamma$ also wahr.

Damit ist $\mathcal N$ auch Modell von $\mathrm{PA}\cup\{\gamma\}$. Ist diese Formelmenge nun vielleicht vollständig? Immerhin ist $\gamma$ aus ihr ja trivial ableitbar. Sicher ist sie es auch nicht, denn wir können obigen Beweis für sie wiederholen, nur muss $bew$ dann durch eine neue Formel, die die Beweisbarkeit in $\mathrm{PA}\cup\{\gamma\}$ beschreibt, ersetzt werden, und wir erhalten eine neue Aussage $\gamma'$, die in $\mathrm{PA}\cup\{\gamma\}$ weder beweis- noch widerlegbar ist. Allgemeiner könnten wir eine Formelmenge $X\supset\mathrm{PA}$ betrachten und für diese den Beweis durchführen. Es ist dabei lediglich wichtig, dass sich Beweisbarkeit in $X$ auch wieder durch eine Formel ausdrücken lässt. Dies ist gegeben, wenn sich wieder „mechanisch“ überprüfen lässt, ob eine gegebene Formel zu $X$ gehört oder nicht. Wir brauchen zur Formulierung des Ergebnisses daher einen Berechenbarkeitsbegriff, ein ausreichender ist der der rekursiven Aufzählbarkeit. Es gilt dann der folgende

Satz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und $\mathcal N\models X$, so ist $X$ unvollständig.

Man beachte, dass andererseits $X=\{\varphi\in\mathcal L_{\mathrm{ar}}\colon \text{$\varphi$ Aussage, $\mathcal N\models\varphi$}\}$ natürlich vollständig ist. Damit ist diese Menge nicht rekursiv aufzählbar.

Panorama 17. 5. 2013

Den ersten Teil der Vorlesung werde ich im vorherigen Eintrag mit einarbeiten, da er dort inhaltlich hingehört. Hier aber die „Folien“ zur Einführung logischer Grundbegriffe.


Und damit Sie mal eine solche gesehen haben und weil ich offenbar zu viel Zeit habe, hier mit\begin{align*}
AG:=\{&\forall x\forall y (x+y=y+x),
\\&\forall x\forall y\forall z((x+y)+z=x+(y+z)),
\\&\forall x(0+x=x),
\\&\forall x\neg\forall y\neg (x+y=0)
\}\end{align*}eine Herleitung von $AG\vdash\neg(c+a=c+b\land\neg a=b)$. Dabei muss man sich noch für jede Zeile überlegen, mit welcher Regel sie aus welchen vorhergehenden folgt.
\begin{align*}
&&AG&\ \vdash\ \forall x\forall y (x+y=y+x)&&\\
&&AG&\ \vdash\ \forall y (c+y=y+c)&&\\
&&AG&\ \vdash\ c+d=d+c&&\\
&&AG,c+d=0&\ \vdash\ c+d=d+c&&\\
&&AG,c+d=0&\ \vdash\ c+d=0&&\\
&&AG,c+d=0&\ \vdash\ d+c=0&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+a)=d+(c+a)&&\\
&&AG,c+a=c+b&\ \vdash\ c+a=c+b&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+a)=d+(c+b)&&\\
&&AG&\ \vdash\ \forall x\forall y\forall z((x+y)+z=x+(y+z))&&\\
&&AG&\ \vdash\ \forall y\forall z((d+y)+z=d+(y+z))&&\\
&&AG&\ \vdash\ \forall z((d+c)+z=d+(c+z))&&\\
&&AG&\ \vdash\ (d+c)+a=d+(c+a)&&\\
&&AG&\ \vdash\ (d+c)+a=(d+c)+a&&\\
&&AG&\ \vdash\ d+(c+a)=(d+c)+a&&\\
&&AG&\ \vdash\ (d+c)+b=d+(c+b)&&\\
&&AG&\ \vdash\ (d+c)+b=(d+c)+b&&\\
&&AG&\ \vdash\ d+(c+b)=(d+c)+b&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+a)=(d+c)+a&&\\
&&AG,c+a=c+b&\ \vdash\ (d+c)+a=d+(c+b)&&\\
&&AG,c+a=c+b&\ \vdash\ d+(c+b)=(d+c)+b&&\\
&&AG,c+a=c+b&\ \vdash\ (d+c)+a=(d+c)+b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ (d+c)+a=(d+c)+b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ d+c=0&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+a=0+b&&\\
&&AG&\ \vdash\ \forall x(0+x=x)&&\\
&&AG&\ \vdash\ 0+a=a&&\\
&&AG&\ \vdash\ 0+b=b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+a=a&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+b=b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ a=b&&\\
&&AG,c+d=0,c+a=c+b,\neg a=b&\ \vdash\ a=b&&\\
&&AG,c+d=0,c+a=c+b,\neg a=b&\ \vdash\ \neg a=b&&\\
&&AG,c+d=0,c+a=c+b,\neg a=b&\ \vdash\ \neg c+d=0&&\\
&&AG,\neg c+d=0,c+a=c+b,\neg a=b&\ \vdash\ \neg c+d=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ \neg c+d=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ \forall y\neg c+y=0&&\\
&&AG&\ \vdash\ \forall x\neg\forall y\neg x+y=0&&\\
&&AG&\ \vdash\ \neg\forall y\neg c+y=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ \neg\forall y\neg c+y=0&&\\
&&AG,c+a=c+b,\neg a=b&\ \vdash\ a=b\\
&&AG,c+a=c+b,a=b&\ \vdash\ a=b\\
&&AG,c+a=c+b&\ \vdash\ a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ c+a=c+b\land\neg a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg a=b\\
&&AG,c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg(c+a=c+b\land\neg a=b)\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg c+a=c+b\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ c+a=c+b\land\neg a=b&&\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ c+a=c+b&&\\
&&AG,\neg c+a=c+b,c+a=c+b\land\neg a=b&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
&&AG,c+a=c+b\land\neg a=b&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
&&AG,\neg(c+a=c+b\land\neg a=b)&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
&&AG&\ \vdash\ \neg(c+a=c+b\land\neg a=b)&&\\
\end{align*}
Durch Weglassen vieler Zeilen und Benutzung von Abkürzungen wird das fast lesbar.
\begin{align*}
&&AG&\ \vdash\ c+d=d+c&&\\
&&AG,c+d=0&\ \vdash\ d+c=0&&\\
&&c+a=c+b&\ \vdash\ d+(c+a)=d+(c+b)&&\\
&&AG&\ \vdash\ (d+c)+a=d+(c+a)&&\\
&&AG&\ \vdash\ (d+c)+b=d+(c+b)&&\\
&&AG,c+a=c+b&\ \vdash\ (d+c)+a=(d+c)+b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ 0+a=0+b&&\\
&&AG&\ \vdash\ 0+a=a&&\\
&&AG&\ \vdash\ 0+b=b&&\\
&&AG,c+d=0,c+a=c+b&\ \vdash\ a=b&&\\
&&AG&\ \vdash\ \exists y(c+y=0)&&\\
&&AG,c+a=c+b&\ \vdash\ a=b\\
&&AG&\ \vdash\ c+a=c+b\rightarrow a=b&&\\
\end{align*}

Panorama 13. 5. 2013

Vorerst nur ein paar Links

• Russellsche Antinomie
• mathematischer Platonismus
• Finitismus
• Konstruktive Mathematik – Wikipedia 
• Intuitionismus (Logik und Mathematik) – Wikipedia
• Luitzen Egbertus Jan Brouwer – Wikipedia
• Errett Bishop - Wikipedia, the free encyclopedia

Panorama 10. 5. 2013

Diese Vorlesung war „paradoxen“ Zerlegungen der Sphäre und der Kugel gewidmet. Die bekanntere und spektakulärere ist die folgende.

Satz (Banach-Tarski, 1924, mit AC). Wir schreiben $A\approx B$ für Teilmengen $A$, $B$ des $\mathbb R^3$, wenn endliche Zerlegungen\begin{align*}A&=A_1\mathop{\dot\cup}\cdots\mathop{\dot\cup} A_k,&B&=B_1\mathop{\dot\cup}\cdots\mathop{\dot\cup} B_k\end{align*}und Bewegungen $\phi_r\colon\mathbb R^3\to\mathbb R^3$ mit $\phi_r[A_r]=B_r$ für $1\le r\le k$ existieren.

Es sei $D:=\{x\in\mathbb R^3\colon \|x\|\le 1\}$ die Vollkugel. Dann existiert eine Zerlegung $D=X\dot\cup Y$ mit $X\approx Y\approx D$.

Wir zerlegen also die Kugel in endlich viele Teile und setzen diese zu zwei Kugeln zusammen. Offenbar können diese Zerlegungen nicht messbar sein, sonst erhielte man durch Vergleich der Volumina der beiden Kugeln den Widerspruch $1=2$.

Wir sehen daran auch, dass „Teilmenge des $\mathbb R^3$“ ohne weitere Qualifizierung wie zumindest Messbarkeit keine sinnvolle Modellierung des Konzepts eines dreidimensionalen Objekts in einem physikalischen Sinne ist.

Auch kann dieses Ergebnis eventuell unsere Skepsis gegenüber dem Auswahlaxiom erhöhen.

Die Zerlegung lässt sich aus der folgenden erhalten. (Die Jahreszahl hatte ich in der Vorlesung falsch angegeben, so ist es aber auch weniger überraschend.)

Satz (Hausdorff, 1914, mit AC). Es sei $S:=\{x\in \mathbb R^3\colon \|x\|=1\}$ die $2$-Sphäre. Dann existieren eine Zerlegung\[S=\mathcal A\mathop{\dot\cup}\mathcal B\mathop{\dot\cup}\mathcal C\mathop{\dot\cup} Q,\]wobei $Q$ abzählbar ist, und Drehungen $\phi,\psi\in\mathrm{SO}(3)$, so dass\begin{align*}\phi[A]&=B\cup C,&\psi[A]&=B,&\psi^2[A]&=C.\end{align*}

Auch hier findet also schon eine wundersame Verdopplung einer Menge statt. Den Beweis dieses Satzes habe ich skizziert. Dabei bin ich Jech gefolgt. Dort kann man auch nachlesen, wie man daraus die Banach-Tarski-Zerlegung erhält. In der Tat setzt man $X=\{\lambda x\colon \lambda\in[0,1],\ x\in\mathcal A\cup Q\}$ und $Y=D\setminus X$. Es ist dann leicht, $X\approx D$ zu sehen, $Y\approx D$ erfordert mehr Mühe, aber keine schwierigen Hilfsmittel.

Die Konstruktion von Hausdorff ähnelt der einer nicht-messbaren Menge von Vitali, ist aber komplizierter. Und während bei Vitali das Einheitsintervall in abzählbar viele Teile zerlegt wird, wird hier die Sphäre in endlich viele Teile zerlegt.

Zermelo vs Peano

Wie haben die Altvorderen doch noch schön gestritten. Bekanntlich hat Zermelo in seinem Beweis des Wohlordnungssatzes das Auswahlaxiom (damals noch nicht so benannt)  formuliert und als besonderes Prinzip hervorgehoben. In einem späteren Aufsatz gibt er einen weiteren Beweis und antwortet auf Kritik. Besonders schön ist seine Antwort auf Peanos Kritik am Auswahlaxiom. Peano hat anscheinend bemängelt, dass das Auswahlaxiom in Peanos logischem Kalkül, dem „Formulaire“, nicht beweisbar wäre. Zermelo entgegnet zunächst, dass dies durchaus auch als Schwäche des Formulaire gewertet werden könne und schlägt sehr vernünftig vor, man solle doch zumindest die Konsequenzen des Auswahlaxioms untersuchen. Er kann dann aber doch nicht anders als wie folgt zu formulieren:

Dabei genügt es, diejenigen Theoreme, welche das Axiom notwendig erfordern, von denen zu trennen, bei welchen es entbehrt werden kann, um auch die gesamte Peanosche Mathematik als einen besonderen Zweig, als eine gewissermaßen künstlich verstümmelte Wissenschaft mit zu umfassen. 

Dann folgt noch der ultimative Seitenhieb:

Freilich hätte Herr Peano noch ein einfaches Mittel, die in Frage stehenden Sätze wie noch viele andere aus seinen eigenen Prinzipien zu beweisen. Er brauchte nur von der neuerdings viel erörterten ,,Russellschen Antinomie" Gebrauch zu machen, da sich aus widersprechenden Prämissen bekanntlich alles beweisen läßt. In der Tat schließen die Prinzipien des Formulaire, welche zwischen „Menge" und ,,Klasse" keinen Unterschied machen, diesen Widerspruch nicht aus. 

Autsch.

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)

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

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?

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

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:

1. Es gibt eine Folge $(a_n)_n$ algebraischer Zahlen, in der jede algebraische Zahl vorkommt.
2. 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.)