Mittwoch, 30. Oktober 2013

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.

Donnerstag, 24. Oktober 2013

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.

Mittwoch, 23. Oktober 2013

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),

Freitag, 18. Oktober 2013

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.

Donnerstag, 20. Juni 2013

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

Freitag, 14. Juni 2013

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.

Freitag, 7. Juni 2013

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.

Donnerstag, 30. Mai 2013

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.

Freitag, 17. Mai 2013

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*}


Freitag, 10. Mai 2013

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.

Montag, 6. Mai 2013

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)

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

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

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

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:
  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.)


Montag, 22. April 2013

Panorama 22. 4. 2013

Der Übungszettel zu diesem Abschnitt.


Der Fundamentalsatz der Algebra


Der Fundamentalsatz der Algebra besagt, dass jedes komplexe Polynom von positivem Grad eine Nullstelle hat.  Wir haben gesehen, dass daraus folgt, dass jedes solche Polynom in Linearfaktoren zerfällt, und auch, dass jedes reelle Polynom sich in (reelle) lineare und quadratische Faktoren zerlegen lässt.  Da aus letzterem auch folgt, dass jedes reelle Polynom ungeraden Grades eine reelle Nullstelle hat, und dies eng mit der Vollständigkeit von $\mathbb R$ zusammenhängt, sollten wir nicht verwundert sein, wenn Beweise des Fundamentalsatzes der Algebra nicht rein algebraisch sind.  Einen Beweis haben wir bereits in der Übung kennengelernt:  Königsberger gibt in seinem Analysis-Lehrbuch einen recht elementaren an, den er Argand zuschreibt, dazu später mehr.

Auch um noch ein wenig über komplexe Zahlen zu reden, haben wir eine andere Art des Beweises des Satzes besprochen.  Sei dazu \[p(z)=z^n+a_{n-1}z^{n-1}+\cdots+a_1z+a_0\]ein komplexes Polynom, $n>0$. Für $r\ge0$ definieren wir nun die geschlossene Kurve\begin{align*}\gamma_r\colon[0,2\pi]&\to\mathbb C\\\phi&\mapsto p(r(\mathrm{cos}\phi+i\,\mathrm{sin}\phi)).\end{align*}Für großes $r$ verhält sie sich in etwa wie\[\phi\mapsto(r(\mathrm{cos}\phi+i\,\mathrm{sin}\phi))^n=r^n(\mathrm{cos}\, n\phi+i\,\mathrm{sin}\,n\phi),\]läuft also $n$ mal um die $0$ herum.  Andererseits ist $\gamma_0$ eine konstante Kurve, die in $a_0$ verweilt.  Lassen wir nun $r$ von einem großen Wert nach $0$ laufen, so ändert sich $\gamma_r$ stetig mit $r$.  Dass dabei eine Kurve, die mehrfach um die Null läuft, in eine konstante übergeht, ist nur denkbar, wenn es ein $r$ gibt, für das $\gamma_r$ die Null trifft, wenn also $p$ eine Nullstelle hat.  Dies ist sicher kein strikter Beweis, aber mit Hilfe des Begriffs der Umlaufzahl kann man einen daraus machen. Außerdem ist das Argument hoffentlich anschaulich.

Wir haben dann den Beweis aus der 1799 eingereichten Dissertation von Gauß angesehen (s.a. auch diese Übersetzung). Zunächst ein modernisierter Überblick über den Beweis. Zu unserem gegebenen Polynom definieren wir zwei Teilmengen der komplexen Zahlen,\begin{align*}L_1&=\left\{z\colon \mathrm{Im}\,(p(z))=0\right\},&L_2&=\left\{z\colon \mathrm{Re}\,(p(z))=0\right\}.\end{align*}Es ist zu zeigen, dass diese einen gemeinsamen Punkt haben. Beide Mengen sind in kartesischen Koordinaten $z=x+iy$ als Nullstellenmengen von Polynomen in $x$ und $y$ gegeben, also algebraische Kurven, die im allgemeinen aus mehreren Komponenten bestehen. Wieder betrachten wir zunächst die Struktur weit draußen. Ein Kreis ausreichend großen Radius' schneidet $L_1$ und $L_2$ in je $2n$ sich abwechselnden Punkten.  Daraus schließt Gauß, dass sich im Inneren eines solchen Kreises die Kurven $L_1$ und $L_2$ schneiden müssen.

Im Gegensatz zu dieser Darstellung vermeidet Gauß die Benutzung komplexer Zahlen im Beweis.  Die Formulierung des Satzes, die er benutzt, ist die Zerlegbarkeit eines reellen Polynoms in lineare und quadratische Faktoren.  Wo wir oben beispielsweise von der Teilmenge $L_1$ der komplexen Zahlen geredet haben, führt er zunächst in der Ebene Polarkoordinaten $r$ und $\phi$ ein und definiert die Linie als Schnitt des Funktionsgraphen der Funktion \[r^n\mathrm{sin}\,n\phi+a_{n-1}r^{n-1}\mathrm{sin}\,(n-1)\phi+\cdots+r\,\mathrm{sin}\,\phi\](dies ist, da die Koeffizienten bei ihm reell sind gleich dem Imaginärteil von $p(r(\mathrm{cos}\,\phi+i\,\mathrm{sin}\,\phi))$, ich habe unsere Bezeichnungen der Variablen beibehalten) mit der Ebene. Dies geschieht in den Abschnitten 16 und 17, die wir uns gemeinsam angesehen haben.

Wir haben uns Abbildung 4 angesehen, die das Beispiel $x^4-2x^2+3x+10$ zeigt, siehe die Fußnote in Abschnitt 18.

Freitag, 19. April 2013

Panorama 19. 4. 2013

Die Erklärung der Galoisgruppe war hoffentlich in der Vorlesung etwas anschaulicher als hier, das ich hier auf das tabellarische Aufführen der Permutationen verzichtet habe.
Denen, die etwas Algebrakenntnisse haben, empfehle ich, sich die Begriffe der Galoisgruppe und der Auflösbarkeit einer Gruppe zusätzlich anderswo anzusehen, da ich hier bemüht war, Begriffe aus der Algebra zu vermeiden.
Was wir in den letzten zehn Minuten zum Fundamentalsatz der Algebra gesagt haben, habe ich hier nicht wiedergegeben.


Lösbarkeit algebraischer Gleichungen durch Radikale


Nachdem Lagrange das Lösen algebraischer Gleichungen durch Radikale, also das Finden von Lösungen, die sich unter Verwendung von nur Wurzeln und den Körperoperationen schreiben lassen, systematisiert hatte und man dennoch keine allgemeinen Lösungen für Gleichungen höheren als vierten Grades gefunden hatte, konnte man annehmen, dass diese vielleicht gar nicht existierten.  Die Nichtexistenz dieser Lösungen wurde von Abel nach einem früheren lückenhaften Versuch von Ruffini 1823(?) bewiesen.

Heute beweist man dieses Ergebnis meist mit Hilfe der Galois-Theorie.  Diese basiert auf Ideen von Galois, der 1832 genauer die Frage beantwortete, welche algebraischen Gleichungen durch Radikale lösbar sind.

Galois-Theorie


Wir betrachten als Beispiel die Gleichung \[x^4-6x^2+2=0.\]  Diese ist offensichtlich leichter lösbar als eine allgemeine Gleichung vierten Grades, denn wir können $y=x^2$ substituieren, und erhalten $y=3\pm\sqrt7$ und damit \begin{align*}x_1&=\sqrt{3+\sqrt7},&x_2&=\sqrt{3-\sqrt7},\\ x_3&=-\sqrt{3+\sqrt7},& x_4&=-\sqrt{3-\sqrt7}.\end{align*}Nun sind „von $\mathbb Q$ aus gesehen“ alle diese Nullstellen gleich gut, denn keine von ihnen hat eine algebraische Eigenschaft, die nicht daraus folgte, Nullstelle von $x^4-6x^2+2$ zu sein. (Offenbar müsste man dies präzisieren, wenn man sich das Thema ernsthaft mathematisch erschließen wollte.) Es sind aber nicht alle möglichen Reihenfolgen der vier Nullstellen ununterscheidbar, denn bei der oben gewählten gilt $x_1+x_3=0$, nicht aber $x_1+x_2=0$.  Überlegen wir uns nun (im Vertrauen darauf, dass alle weiteren algebraischen Relationen zwischen den Nullstellen hieraus bereits folgen), welche weiteren Reihenfolgen der Nullstellen diese Gleichung erfüllen, so erhalten wir insgesamt acht: Die Wahl von $x_1$ ist frei und bestimmt $x_3$, danach gibt es noch zwei Möglichkeiten, die restlichen beiden Nullstellen auf $x_2$ und $x_4$ zu verteilen. Mehr Struktur sieht man, wenn man diese acht Reihenfolgen als Permutationen der vier Nullstellen ansieht, sie bilden dann eine Untergruppe der Gruppe aller Permutationen der vier Nullstellen.  Diese heißt die Galoisgruppe der Gleichung, wir bezeichnen sie hier mit $\mathrm{Gal}(x^4-6x^2+2)$.  Sie ist in diesem Fall isomorph Symmetriegruppe eines Vierecks (der Diedergruppe mit $8$ Elementen, bei mir $D_8$, in der Wikipedia $D_4$ genannt).  Dies ist eine nicht kommutative Gruppe.

Den Zusammenhang der Struktur der Gruppe mit den bei der Lösung der Gleichung gemachten Wahlen können wir noch weiter verdeutlichen.  Wir können fragen, was die verschieden Elemente der Galoisgruppe mit der Zahl $\sqrt7$ machen.  Dies ist möglich, weil sich $\sqrt7$ als algebraischer Ausdruck in $x_1,\ldots,x_4$ schrieben lässt.  In der Vorlesung haben wir den schönen Ausdruck $\frac12(x_2x_4-x_1x_3)$ gefunden.  Jede zur Galoisgruppe gehörende Permutation bildet diesen Ausdruck nun auf sich selbst oder auf sein Negatives ab.  Dies beschreibt einen Gruppenhomomorphismus von $\mathrm{Gal}(x^4-6x^2+2)$ in eine zweielementige Gruppe.  Der Kern dieser Abbildung ist auch abelsch.  Er entspricht den Vorzeichenwahlen bei den äußeren Wurzeln.

Wir kommen nun zu einer weiteren wesentlichen
Definition. Es sei $G$ eine endliche Gruppe.  Dann heißt $G$ auflösbar, wenn ein $n\in\mathbb N$, Untergruppen $G=G_0\supset G_1\supset\cdots\supset G_n=\{1\}$, abelsche Gruppen $A_0,\dots,A_{n-1}$ und Gruppenhomomorphismen $\phi_j\colon G_j\to A_j$ mit $\mathrm{ker} \,\phi_j=G_{j+1}$ existieren.

Damit können wir Galois' Ergebnis formulieren.
Satz. Es sei $f$ ein irreduzibles Polynom.  Dann sind äquivalent:
  • Die Gleichung $f=0$ ist durch Radikale lösbar.
  • Die Galoisgruppe von $f$ ist auflösbar.

Die Idee ist dabei, dass einerseits eine Lösung der Gleichung wie in unserem Beispiel (in dem wir einiges unterschlagen haben) angedeutet zu den Homomorphismen $\phi_j$ führt, und dass andererseits die Untergruppen, die zeigen, dass die Galoisgruppe auflösbar ist, zu einer Anleitung führt, wie die Gleichung mit Hilfe von sukzessiven Lagrangeresolventen zu lösen ist.

Weiteres:
  • Galois beschreibt eine Methode, wie man zumindest prinzipiell die Galoisgruppe eines Polynoms berechen kann.
  • Für jedes $n$ gibt es Polynome $n$-ten Grades, deren Galoisgruppe die Gruppe aller Permutationen der $n$ Nullstellen ist, also die symmetrische Gruppe $S_n$.  In der Tat ist das in gewisser Weise der Normalfall.  Ein einfaches Beispiel für ein Polynom fünften Grades mit voller Galoisgruppe ist $x^5-x-1$.
  • Die symmetrische Gruppe $S_n$ ist genau dann auflösbar, wenn $n\le 4$. Zusammen mit dem vorhergehenden Punkt beweist das den Satz von Abel-Ruffini.
Galois' Arbeit war auch der Beginn der Gruppentheorie.  Alle bei ihm auftauchenden Gruppen sind Untergruppen von Permutationsgruppen, der abstrakte Begriff einer Gruppe wie wir ihn heute kennen, war noch unbekannt.  Das ist aber ohnehin keine Einschränkung der Allgemeinheit, denn es ist ohnehin jede Gruppe isomorph zu einer Untergruppe einer symmetrischen Gruppe.

Montag, 15. April 2013

Panorama 15. 4. 2013

Mir ist bewusst, dass ich in der Vorlesung etwas zuviel versucht habe.  Sie sollten den ersten Teil aber noch völlig verstehen können und ebenso den zweiten Absatz des zweiten Teils (ohne dass Sie (\ref{disc}) nachrechnen müssten).  Wenn Sie von dem Rest eine Idee mitnehmen, genügt dies.

Mehr zur Cardanischen Formel


Wir untersuchen zunächst, wann die Bedingung \(D>0\) aus der Formel erfüllt ist.

Proposition. Es seien \(p,q\in\mathbb R\), \(D:=\left(\frac q2\right)^2+\left(\frac p3\right)^3\). Dann hat das Polynom \(f(x)=x^3+px+q\)
  • genau eine reelle Nullstelle, und diese ist einfach, wenn D>0,
  • eine reelle Nullstelle mindestens zweiter Ordnung, wenn D=0,
  • drei verschiedene reelle Nullstellen, wenn D<0.

Beweisskizze.  Der interessante Fall ist \(p<0\).  Dann hat \(f\) ein lokales Maximum bei \(x_a:=-\sqrt{-\frac p3}\) und ein lokales Minimum bei \(x_b:=\sqrt{-\frac p3}\).  Man errechnet, dass \(f(x_a)f(x_b)=4D\).  Also ist für \(D=0\) eines der lokalen Extrema eine doppelte Nullstelle, für \(D>0\) hat \(f\) an beiden lokalen Extrema gleiches Vorzeichen, also keine Nullstelle dazwischen und damit genau eine, für \(D<0\) hat \(f\) an beiden lokalen Extrema verschiedenen Vorzeichen, also eine Nullstelle dazwischen und insgesamt drei Nullstellen.


Im Falle dreier reeller Nullstellen ist die Formel also zuächst einmal nicht anwendbar. Bombelli beschreibt 1572, dass man die Nullstelle \(4\) des Polynoms \(x^3-15x-4\) aus Cardanos Formel dennoch erhalten kann, indem man
\begin{align*}x&=\sqrt[3]{2+\sqrt{-121}}+\sqrt[3]{2-\sqrt{-121}}\\
&=\sqrt[3]{2+11\sqrt{-1}}+\sqrt[3]{2-11\sqrt{-1}} \\&=\left(2+\sqrt{-1}\right)+
\left(2-\sqrt{-1}\right)=4\end{align*}rechnet.

Natürlich erkennen wir das heute als Rechnen mit komplexen Zahlen.  Wir halten fest:  Hier ist ein mit reellen Zahlen gestelltes Problem, dessen reelle Lösung wir erhalten, indem wir mit komplexen Zwischenergebnissen rechnen.  Dies war eine Motivation, komplexe Zahlen zu studieren.  Es sollte erwähnt werden, dass auch bei Cardano schon im Ansatz Quadratwurzeln aus negativen Zahlen vorkommen.

Man sieht oben, dass, wenn wir \(2+\sqrt{-1}\) als dritte Wurzel aus \(2+11\sqrt{-1}\) wählen (es gibt derer ja drei), wir die „passende“ Wurzel aus \(2-11\sqrt{-1}\) wählen müssen, um als Summe eine der reellen Nullstellen zu erhalten.  Wir formulieren dies aus moderner Sicht, also von Anfang an komplexe Zahlen zulassend.

Vorbemerkung. Ist $u\in\mathbb C$ mit $u^3=a\ne0$ und $\tilde u$ eine andere dritte Wurzel aus $a$, also $\tilde u^3=a$, so ist $(\tilde u/u)^3=1$, die beiden unterscheiden sich also durch eine komplexe Zahl, deren dritte Potenz $1$ ist, eine dritte Einheitswurzel. Diese lassen sich einerseits leicht in Polarkoordinaten angeben, es handelt sich um $\mathrm{exp}\left(k\cdot\frac{2\pi i}3\right)=\mathrm{cos}\left(k\cdot\frac{2\pi}3\right)+i\mathrm{sin}\left(k\cdot\frac{2\pi}3\right)$ mit $k=0,1,2$.  Eine andere Art, sie zu beschreiben ist als Nullstellen von $z^3-1=(z-1)(z^2+z+1)$.  Neben der $1$ sind es also die beiden Nullstellen von $z^2+z+1$.  Ist $\zeta$ eine solche, so ist $\zeta^2$ die andere, denn dann ist $(z-\zeta)(z-\zeta^2)=z^2-(\zeta+\zeta^2)z+\zeta^3=z^2+z+1$.  Für ein solches $\zeta$ sind also $1$, $\zeta$, $\zeta^2$ die drei dritten Einheitswurzeln. Aus der Darstellung in Polarkoordinaten oder aus $\zeta^2+\zeta+1=0$ sieht man, dass die beiden dritten Einheitswurzeln außer der $1$ sich als $-\frac12\pm\frac12\sqrt3 i$ schreiben lassen.

Proposition. Es seien \(p,q\in\mathbb C\), \(D:=\left(\frac q2\right)^2+\left(\frac p3\right )^3\) und \(u,v\in\mathbb C\) mit \(u^3 = -\frac q2+\sqrt D\), \(v^3 = -\frac q2-\sqrt D\) (mit der selben Wahl für die Quadratwurzel) und \(uv=-\frac p3\), und ist außerdem \(\zeta^2+\zeta+1=0\), so sind\begin{align}\label{x123}x_1&=u+v,&x_2&=\zeta u+\zeta^2 v,&x_3&=\zeta^2u+\zeta v\end{align} die drei Nullstellen des Polynoms \(x^3+px+q\).

Um dies unabhängig von unserer Herleitung zu verifizieren, genügt es wegen \begin{multline*}(x-x_1)(x-x_2)(x-x_3)=\\=x^3-(x_1+x_2+x_3)x^2+(x_2x_3+x_1x_3+x_1x_2)x-x_1x_2x_3\end{multline*} zu überprüfen, dass
\begin{equation}\label{sigmapq}\begin{aligned}
\sigma_1:=&x_1+x_2+x_3&&=0,\\
\sigma_2:=&x_2x_3+x_1x_3+x_1x_2&&=p,\\
\sigma_3:=&x_1x_2x_3&&=-q.
\end{aligned}\end{equation}Dies ist leicht getan.

An dieser Stelle sollten wir darauf hinweisen, dass Cardano auch Lösungsformeln für quartische Gleichungen, also Nullstellen von Polynomen vierten Grades, angegeben hat. Diese hat er seinem Schüler Ferrari zugeschrieben.

Der Beitrag Lagranges

Nun wissen wir zwar eigentlich alles über Cardanos Formel, das es zu wissen gibt, aber um eine bessere Vorstellung von dem, was folgt, erlangen zu können, wollen wir noch eine weitere Sichtweise betrachten.  Dazu machen wir einen Zeitsprung zu einem weiteren italienischen Mathematiker, der allerdings auch in Berlin und Paris gewirkt hat, Lagrange.  Zu algebraischen Gleichungen hat er 1770 und 1771 Arbeiten verfasst.

Ausgangspunkt sind die Gleichungen (\ref{sigmapq}).  Die dort vorkommenden Polynome in den Variablen $x_1$, $x_2$, $x_3$, die wir $\sigma_1$, $\sigma_2$, $\sigma_3$ genannt haben, sind symmetrisch, das heißt, vertauscht man in ihnen zwei der Variablen, so ändern sie sich nicht.  In der Tat ist es so, dass sich jedes symmetrische Polynom in $x_1$, $x_2$, $x_3$ als Polynom in den Ausdrücken $\sigma_1$, $\sigma_2$, $\sigma_3$ schreiben lässt, daher heißen letztere die elementarsymmetrischen Polynome.  Dieses Umschreiben lässt sich sogar ganz systematisch tun, aber damit wollen wir uns hier nicht beschäftigen.  Wir betrachten aber das an sich interessante Beispiel \[(x_1-x_2)(x_1-x_3)(x_2-x_1)(x_2-x_3)(x_3-x_1)(x_3-x_2).\]Da hier jeder Term $(x_i-x_j)$ mit $i\ne j$ genau einmal vorkommt, ist dieses Polynom symmetrisch, muss sich also mit Hilfe von $\sigma_1$, $\sigma_2$, $\sigma_3$ schreiben lassen, und in der Tat findet man \begin{multline}\label{disc}(x_1-x_2)(x_1-x_3)(x_2-x_1)(x_2-x_3)(x_3-x_1)(x_3-x_2)=\\=-\sigma_1^2\sigma_2^2+4\sigma_1^3\sigma_3+4\sigma_2^3+27\sigma_3^2-18\sigma_1\sigma_2\sigma_3,\end{multline}was nachrechnen kann, wer an so etwas Spaß hat. Setzen wir nun die Werte aus (\ref{sigmapq}) ein und unsere alte Definition von $D$, so erhalten wir \begin{multline*}(x_1-x_2)(x_1-x_3)(x_2-x_1)(x_2-x_3)(x_3-x_1)(x_3-x_2)=\\=4p^3+27q^2=108D.\end{multline*}Wir sehen also erneut und völlig unabhängig von obigem, dass $D$ genau dann Null ist, wenn zwei der Nullstellen gleich sind, das Polynom also eine mehrfache Nullstelle hat!  Weiterhin beobachten wir, dass in diesem Ausdruck jeder Term zweimal mit verschiedenem Vorzeichen vorkommt.  Setzen wir \[t:=(x_1-x_2)(x_1-x_3)(x_2-x_3),\] so haben wir also \[t^2=-108D.\]Wir erkennen hier etwas, das wir oben bereits überprüft haben, nämlich, dass, wenn alle Nullstellen reell sind, $D\le0$ sein muss, denn dann ist ja $t^2\ge0$.

Wir haben damit noch etwas anderes erreicht.  Das Polynom $t$ ist nicht symmetrisch, es ändert das Vorzeichen, wenn wir zwei der Variablen vertauschen.  Es lässt sich also nicht durch die elementarsymmetrischen Polynome und dadurch durch $p$ und $q$ ausdrücken.  Fügen wir also zu $p$ und $q$ noch $t$, dass wir ja als $t=\sqrt{-108D}$ definiert denken können, so können wir mehr Polynome in $x_1$, $x_2$, $x_3$ ausdrücken als vorher. Das ist gut, denn wir wollen ja schließlich $x_1$ ausdrücken, und erlauben uns dabei, Wurzeln zu benutzen.

Noch etwas Notation.  Wir bezeichnen mit $\tau$ die Permutation, die $x_2$ und $x_3$ vertauscht und schreiben beispielsweise \begin{align*}\tau\cdot\sigma_2&=\tau\cdot(x_1x_2x_3)=x_1x_3x_2=\sigma_2,\\\tau\cdot t&=\tau\cdot((x_1-x_2)(x_1-x_3)(x_2-x_3))=(x_1-x_3)(x_1-x_2)(x_3-x_3)=-t.\end{align*}Ebenso bezeichnen wir mit $\sigma$ (eine schlechte Wahl, da diese Permutation nichts mit den $\sigma_i$ zu tun hat, aber da ich sie in der Vorlesung gewählt habe, bleibe ich dabei) die zyklische Permutation, die $x_1$ durch $x_2$ ersetzt, $x_2$ durch $x_3$ und $x_3$ durch $x_1$.  Wir haben damit\[\sigma\cdot t=(x_2-x_3)(x_2-x_1)(x_3-x_1)=t,\]diese Permutation lässt $t$ also unverändert.

Nun endlich zu dem Ansatz von Lagrange, der Lagrange-Resolvente.  Er definiert, wieder mit unserer dritten Einheitswurzel $\zeta$, die $\zeta^2+\zeta+1=0$ erfüllt,\begin{align*}s_1&=x_1+x_2+x_3,\\s_2&=x_1+\zeta x_2+\zeta^2 x_3,\\s_3&=x_1+\zeta^2x_2+\zeta x_3.\end{align*}Gelingt es uns nun, Formeln für $s_1$, $s_2$, $s_3$ zu finden, so haben wir damit auch welche für $x_1$, $x_2$, $x_3$, denn\begin{align}\label{lri}3x_1&=s_1+s_2+s_3,\\3x_2&=s_1+\zeta^2 x_2+\zeta x_3,\\3x_3&=s_1+\zeta s_2+\zeta^2x_3.\end{align}Von den drei neuen Ausdrücken ist nur $s_1$ symmetrisch.  In der Tat haben wir $s_1=\sigma_1=0$.  Wir sehen sofort\begin{align*}\tau\cdot s_2&=s_3,&\tau\cdot s_3&=s_2.\end{align*}Außerdem\[\sigma\cdot s_2=x_2+\zeta x_3+\zeta^2 x_1=\zeta^{-1}s_2.\]Daraus folgt aber\[\sigma\cdot s_2^3=\zeta^{-3}s_2^3=s_2^3,\]$s_2^3$ hat also eine Symmetrie, die $s_2$ nicht hat (wie oben $t^2$ im Vergleich zu $t$), was hilfreich ist.  Denn wir haben ebenso $\sigma\cdot s_3^3=s_3^3$ und damit\begin{align*}\sigma\cdot(s_2^3+s_3^3)&s_2^3+s_3^3,&\tau\cdot(s_2^3+s_3^3)=s_3^3+s_2^3=s_2^3+s_3^3.\end{align*}Da aber jede Permutation der drei Variablen $x_1$, $x_2$, $x_3$ sich durch mehrfache Anwendung von $\sigma$ und $\tau$ ergibt, ist $s_2^3+s_3^3$ symmetrisch und lässt sich daher als Polynom in den elementarsymmetrischen Polynomen und damit in $p$ und $q$ schreiben.  Ähnlich haben wir\begin{align*}\sigma\cdot(s_2^3-s_3^3)&=s_2^3-s_3^3,&\tau\cdot(s_2^3-s_3^3)&=-(s_2^3-s_3^3),\end{align*}$s_2^3-s_3^3$ ist also nicht symmetrisch, aber $(s_2^3-s_3^3)t$ ist es.  Damit können wir für $s_2^3-s_3^3$ einen Ausdruck in $p$, $q$ und $t$ erhalten.  Damit haben wir dann für $s_2^3=\frac12\left((s_2^3+s_3^3)+(s_2^3-s_3^3)\right)$ einen Ausdruck in $p$, $q$ und $t$, also
\[s_2=\sqrt[3]{\text{ein Ausdruck in $p$, $q$, $t$}},\]
was mit $s_1=0$ und $s_3=\tau\cdot s_2$ in (\ref{lri}) eingesetzt Formeln für $x_1$, $x_2$, $x_3$ liefert.

Nachtrag: Da es mir ums Prinzip und um die Rolle von Permutationen in der Rechnung ging, habe ich in der Vorlesung keine konkreten Formeln angegeben.  In der Tat ergibt sich aber leicht (mit weniger Aufwand als für $t^2=-108D$ oben), dass \begin{align*}s_2^3+s_3^3&=2\sigma_1^3-9\sigma_1\sigma_2+27\sigma_3=-27q,\\s_2^3-s_3^3&=3(\zeta-\zeta^2)t.\end{align*}Mit $\zeta-\zeta^2=\sqrt{-3}$, ergibt sich also\begin{align*}s_2^3&=\frac12\left(-27q+3\sqrt{-3}t\right),\\s_3^3&=\frac12\left(-27q-3\sqrt{-3}t\right),\\\end{align*}und schließlich mit $3x_1=s_2+s_3$\[x_1=\sqrt[3]{-\frac q2+\frac{\sqrt{-3}}{18}\sqrt{-4p^3-27q^2}}+\sqrt[3]{-\frac q2-\frac{\sqrt{-3}}{18}\sqrt{-4p^3-27q^2}},\]worin man wieder die Cardanische Formel erkennt.  Dabei haben wir nur das Detail unterschlagen, wie man sieht, wie die beiden Kubikwurzeln passend zueinander gewählt werden müssen.




Freitag, 12. April 2013

Panorama 12. 4. 2013

Vorweg:  Ich habe das Buch, das ich gezeigt habe, um zu demonstrieren, dass Lehrbücher 1930 nicht viel anders als heute waren, nur unvollständig genannt.  Es war Van der Waerdens „Algebra I“.  Allerdings sehe ich nun, dass ich ausgerechnet eine Seite aus einem Kapitel, dass in der ersten Auflage gar nicht vorhanden war, genommen habe.  Wer 1970 getippt hatte, lag also sehr gut.

Die Vorlesung war heute zweigeteilt.  Zuerst habe ich ein wenig über Fachzeitschriften und Mathematik im Internet geredet.  Ich habe diese Folien benutzt.

Dies sind die Links daraus:

Im zweiten Teil haben wir uns kurz mit quadratischen, dann vor allem mit kubischen Gleichungen beschäftigt.  Für letzteres war für mich Kapitel 1 von Bewersdorff, Algebra für Einsteiger, 3. Aufl. eine wesentliche Vorlage.
Das Hauptergebnis war die von Cardano publizierte (s.a. Tartaglia) Herleitung einer Lösungsformel für kubische Gleichungen. Ich gebe sie hier noch einmal in Kurzform an.  Ausgehend von \[
(u+v)^3 - 3uv(u+v) - (u^3 +v^3) = 0,
\]was sich auch geometrisch deuten lässt, sieht man, dass \(x=u+v\) eine Lösung ist, wenn \(uv = - \frac p3\) und \(u^3+v^3 = -q\).  Ersteres ist äquivalent zu \( u^3v^3 = -\left(\frac p3\right)^3\).  Diese beiden Gleichungen sind nun aber genau dann erfüllt, wenn \(u^3\) und \(v^3\) die beiden Lösungen der quadratischen Gleichung \(w^2 + q w -\left(\frac p3\right)^3 \) sind. (Diesen Punkt hätte ich in der Vorlesung mehr betonen sollen.)  Damit erhält man schon den folgenden
Satz. Seien \(p,q\in\mathbb R\), \(D:=\left(\frac q2\right)^2+\left(\frac p3\right)^3\ge0\). Dann ist\[
x=\sqrt[3]{-\frac q2 + \sqrt D} + \sqrt[3]{-\frac q2 - \sqrt D}
\]eine Lösung der Gleichung
\[ x^3+px+q=0.
\]Dabei ist für \(r<0\) der Ausdruck \(\sqrt[3]r\) als \(-\sqrt[3]{-r}\) zu verstehen.



Dienstag, 9. April 2013

Panorama 8. 4. 2013

Inhaltlich ist in der ersten Sitzung nichts passiert, aber wir haben die folgenden Mathematiker erwähnt.

Geometer, die auch schon wussten, dass die Wurzel aus zwei irrational ist:
Der Mathematiker, der unter anderem die arabischen Ziffern nach Europa brachte:
Die Begründer der Differential- und Integralrechnung:
Zur Fundierung selbiger wie wir sie heute kennen:
Zum Begriff des metrischen Raumes:
Der Mathematiker, mit dessen Namen \(e^{\pi i}=-1\) verbunden ist:
Unser erster mathematischer Ausflug wird sich mit Nullstellen von Polynomen beschäftigen:
Der zweite mit Mengenlehre und Logik:
Der dritte mit Topologie, er wird nach Euler und Gauß die folgenden beinhalten:
Als ein weiteres Beispiel eines vor nicht allzu langer Zeit gelösten Problems habe ich die Fermatsche Vermutung genannt:

Panorama der Mathematik im Sommersemester 2013

Für Kommentare und kurze Zusammenfassungen zu der Vorlesung Panorama der Mathematik möchte ich diesen Blog benutzen, um den Hörerinnen und Hörern der Vorlesung (und auch anderen) auf einfache Art Kommentare zu ermöglichen.  Ich möchte aber bitten, diesen Blog nicht für rein organisatorische Fragen zu benutzen.

Mathematik kann hier übrigens mit MathJax gesetzt werden, allerdings kann man bei Kommentaren leider nicht das Ergebnis vor der Veröffentlichung überprüfen.

Alle Einträge anzeigen.