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?