Kapitel 3
Im Umfeld von Gödels Theorem

1  Interpretationen der Gödel-Aussage G und übernatürliche Zahlen

Wir haben in Kapitel 2.5 einen wohlgeformten Ausdruck   G   kennengelernt, von dem wir beweisen konnten, dass weder er selbst noch sein Gegenteil   "NICHT G"   in der Peano-Arithmetik bewiesen werden können. Dieser Ausdruck lautete:

Dabei ist m die Gödelnummer der Aussage   M(x)   , die lautet:   "FÜR_ALLE y GILT:   NICHT B(x,y)"   , d.h. man kann   M(x)   als die m-te Aussage in einer vollständigen Aussagenliste ansehen. G ist demnach nichts Anderes als das Diagonalelement M(m).

G   bzw.   M(x)   enthalten eine Aussage   B(x,y)   , die eine Relation zwischen zwei Zahlen   x   und   y   herstellt:   B(x,y)   ist beweisbar, wenn   y   die Gödelnummer eines Beweises zum Diagonalelement der x-ten Aussage ist. Man sagt dann auch, x und y bilden ein Beweispaar. Andernfalls ist "NICHT B(x,y)" beweisbar.

Die Interpretation von G lautet also: Für alle y gilt, dass sie keine Beweisnummer zum Diagonalelement   M(m) = G   sind. Dabei ist m die Gödelnummer von M(x) und   M(m) = G   ist das entsprechende Diagonalelement.

Man kann G mit Hilfe einer einfachen logischen Ersetzungsregel (der sogenannte Austauschregel) etwas umformulieren. Die Austauschregel besagt, dass man in jeder wohlgeformten Zeichenkette den Substring "FÜR_ALLE y GILT: NICHT" ersetzen kann durch den Substring "NICHT ES_GIBT y:" . Damit lautet G so:

Interpretiert bedeutet dies: "Es gibt kein y, das eine Beweisnummer zum Diagonalelemt der m-ten Aussage (also zu G) bildet." Das entspricht unserer obigen Interpretation.

Analog können wir "NICHT G" aufschreiben:

oder gleichwertig dazu (siehe die zweite Formulierung von G):

Die Interpretation von "NICHT G" wäre folgende: "Es gibt ein y, das eine Beweisnummer zum Diagolalelemt der m-ten Aussage (also zu G) bildet."


Nun haben wir gesehen, dass weder   G   noch   "NICHT G"   in der Peano-Arithmetik bewiesen werden können, wenn die Peano-Arithmetik widerspruchsfrei ist. Also können wir entweder   G   oder   "NICHT G"   als neues Axiom zu den Peano-Axiomen hinzufügen, ohne dass dadurch neue Widersprüche entstehen. Sowohl   G   als auch   "NICHT G"   sind neue Aussagen, die nicht von den anderen Peano-Axiomen logisch abhängen (sonst wäre eine von beiden aus den Axiomen ableitbar).

Betrachten wir den Fall, dass wir die Aussage G zu den Axiomen hinzufügen. Das erscheint uns natürlich, denn G macht eine Aussage, die wir als wahr interpretieren. G sagt ja: "Ich (G) bin nicht aus den anderen Peano-Axiomen ableitbar". Und das stimmt ja, denn sonst könnten wir G nicht als neues Axiom hinzufügen.

Ist es uns damit gelungen, aus der Peano-Arithmetik eine vollständige widerspruchsfreie Theorie zu machen? Schließlich haben wir das Loch, dass aufgrund von Gödels Satz bestand, durch das Hinzufügen von G geschlossen. Im neuen formalen System "Peano-Arithmetik inclusive G" ist G nämlich sofort aus den Axiomen beweisbar, denn es ist selbst schon ein Axiom.

Man könnte nun allerdings eine neue Liste von Beweisen aufstellen, nämlich alle Ableitungen, die sich aufgrund der Peano-Axiome sowie G aufstellen lassen. Diese neue Liste enthält natürlich alle Beweise der alten Liste, die sich alleine aus den Peano-Axiomen aufstellen ließ. Hinzu kommen alle die Beweise, die G als weiteres Axiom benötigen.

Aber nun können wir die gesamte Argumentation aus Kapitel 2.5 wiederholen, diesmal allerdings auf Basis der neuen Beweisliste. Wir können eine neue entscheidbare Aussage B'(x,y) definieren: B'(x,y) ist beweisbar, wenn y die Gödelnummer eines Beweises aus der neuen Beweisliste zum Diagonalelement der x-ten Aussage ist. Andernfalls ist "NICHT B'(x,y)" beweisbar. Weiterhin definieren wir eine neue Aussage M'(x) mit Gödelnummer m'; sie lautet: "FÜR_ALLE y GILT: NICHT B'(x,y)". Das Diagonalelement M'(m'), das wir G' nennen wollen, lautet dann:

Analog zu Kapitel 2.5 können wir zeigen, dass weder G' noch "NICHT G'" aus den Peano-Axiomen inclusive G ableitbar sind. Das Loch bleibt immer bestehen, denn es basiert darauf, dass sich die Beweise in einer Liste vollständig auflisten lassen. Jeder Versuch, das Loch zu schließen, erzeugt ein neues Loch, das auf dem gleichen Mechanismus beruht.

Wir kennen bereits ein ähnliches nicht-stopfbares Loch (siehe Kapitel 2.3 ): Wenn wir versuchen, eine Liste aller überall definierten berechenbaren Funktionen aufzustellen (also eine Liste aller berechenbaren natürlichen Zahlenfolgen ohne Definitionslücken), so können wir mit Hilfe von Cantors Diagonalverfahren immer eine neue Funktion (Zahlenfolge) konstruieren, die noch nicht in der Liste vorhanden ist. Fügen wir diesen neue Funktion zur Liste hinzu, so können wir wieder eine weitere Funktion definieren, die auch in der neuen Liste nicht vorhanden ist, und so fort.


Betrachten wir nun die zweite Möglichkeit: statt   G   fügen wir   "NICHT G"   als neues Axiom zu den Peano-Axiomen hinzu. Auch dadurch entsteht kein Widerspruch.

Dennoch haben wir ein Problem, wenn wir uns die bisherige Interpretation von   "NICHT G"   ansehen. "NICHT G" war die Aussage   "ES_GIBT y: B(m,y)"   . Bisher haben wir diese Aussage so interpretiert: "Es gibt eine Zahl y, die eine Beweisnummer zum Diagolalelemt der m-ten Aussage (also zu G) bildet." Andererseits wissen wir aber, dass es innerhalb der Peano-Arithmetik keinen Beweis zu G gibt, wenn wir Widersprüche ausschließen. Demnach behauptet   "NICHT G"   in unserer Interpretation eine Unwahrheit. Wie aber können wir eine Unwahrheit als neues Axiom zu den Peano-Axiomen hinzufügen? Bricht damit nicht das ganze System zusammen?

Irgendetwas stimmt also nicht. "NICHT G" behauptet eine Unwahrheit, aber dennoch gibt es keinen Widerspruch in unserem so erweiterten formalen System, denn wir wissen, dass G nicht aus den Peano-Axiomen ableitbar ist - "NICHT G" kann also nicht mit der Aussage G kollidieren. Was kollidiert, ist unsere Interpretation von "NICHT G" mit der Tatsache, dass G nicht beweisbar ist.

Die Situation kommt uns bekannt vor (siehe Kapitel 2.1 ). Es war nicht möglich, das Parallelenaxiom aus den anderen Axiomen der Geometrie abzuleiten. Damit war es möglich, verschiedene Versionen des Parallelenaxioms hinzuzufügen. Beispielsweise könnten wir folgende Version als zusätzliches Axiom verwenden:

"Durch einen PUNKT geht keine GERADE, so dass diese eine andere vorgegenene GERADE nicht schneidet (wenn der PUNKT nicht auf der vorgegebenen GERADEn liegt)."

In unserer normalen Interpretation sagt dieser Satz eine Unwahrheit über Punkte und Geraden, denn man kann auf einem Blatt Papier genau eine Gerade durch einen Punkt ziehen, so dass die Gerade eine danebenliegende vorgegebene Gerade nicht schneidet: man zeichnet die Gerade einfach parallel zur vorgegebenen Geraden.

Dennoch widerspricht dieses Axiom nicht den Aussagen über PUNKTe und GERADEn aus den anderen vier geometrischen Axiomen. Wo also liegt der Denkfehler?

Der Fehler lag darin, dass wir intuitiv nur eine Interpretation für die Zeichenketten PUNKT und GERADE zugelassen hatten. Diese Interpretation ist jedoch aufgrund der vier geometrischen Axiome nicht zwingend. So kann man GERADE auch als Großkreis auf einer Kugel und PUNKT als gegenüberliegendes Punktepaar auf der Kugel interpretieren - und schon ergibt alles einen Sinn.

Auch bei "NICHT G" liegt der Fall ähnlich: wir haben ein Problem mit der bisherigen Interpretation von "NICHT G". Schauen wir uns also den scheinbaren Widerspruch genauer an und überlegen wir, ob wir eine Interpretation finden können, in der das Problem verschwindet.


Betrachten wir eine beliebige, aber natürliche Zahl g. Natürlich heisst, dass es ein Zahlzeichen (z.B. 27) für diese Zahl gibt, oder genauer: g muss sich als NACHFOLGER( NACHFOLGER ( ... (0)..)) schreiben lassen. Ist g eine Beweisnummer zur Aussage G ?

Wir kennen die Antwort schon, denn wir wissen, dass G nicht beweisbar ist. Aber wir wollen uns nochmal den entsprechenden Beweis aus Kapitel 2.5 ansehen, um zu erkennen, was genau wir da bewiesen haben. Der Beweis ging so:

Angenommen, G (mit Gödelnummer m) wäre beweisbar, d.h. es gäbe einen Beweis von G mit einer Beweisnummer (nennen wir sie g). Somit wäre auch B(m,g) beweisbar.
G war die Aussage   "FÜR_ALLE y GILT: NICHT B(m,y)"   . Hier kann man für y eine beliebige natürliche Zahl einsetzen, beispielsweise g, und erhält somit die Aussage "NICHT B(m,g)". Damit folgt aus der angenommenen Beweisbarkeit von B(m,g), dass auch "NICHT B(m,g)" beweisbar ist -- die Peano-Arithmetik wäre damit widerspruchsvoll. Wenn wir umgekehrt Widerspruchsfreiheit der Peano-Arithmetik voraussetzen, so kann demnach G nicht beweisbar sein, d.h. B(m,g) ist für keine natürliche Zahl g beweisbar.

Nun ist andererseits B(m,g) für natürliche Zahlen m und g eine entscheidbare Aussage, wie wir aus Kapitel 2.5 wissen. Das bedeutet: Für natürliche Zahlen m und g ist entweder B(m,g) oder "NICHT B(m,g)" beweisbar. Wenn nun B(m,g) für keine natürliche Zahl g beweisbar ist, so folgt, dass "NICHT B(m,g)" für jede natürliche Zahl g beweisbar sein muss. Damit folgt:

Von jeder beliebigen natürlichen Zahl g können wir also einzeln zeigen, dass sie keine Beweisnummer zu G ist. Das gilt auch in unserem um die Aussage "NICHT G" erweiterten System. Damit haben wir die folgende Situation:

Jede natürliche Zahl g hat also die Eigenschaft, keine Beweiszahl von G zu sein, aber dennoch behauptet "NICHT G", dass es irgendeine Zahl (oder irgendein Objekt) y gibt, die diese Eigenschaft besitzt.

Wir müssen also in unserer Interpretation offenbar zwischen natürlichen Zahlen und nicht-natürlichen Zahlen (nennen wir sie übernatürliche Zahlen) unterscheiden. Versuchen wir es daher mit folgender Interpretation:

Mit dieser Interpretation löst sich der Widerspruch auf, denn   "NICHT G"   behauptet jetzt nur noch, dass es eine übernatürliche Beweiszahl von G gibt, während wir für jede natürliche Zahl (also eine Zahl mit Zahlzeichen) zeigen können, dass sie keine Beweiszahl von G ist.


Dennoch fühlen wir uns immer noch etwas unbehaglich, denn wir haben kein intuitives Gefühl dafür, was eine übernatürliche Zahl ist. Bei den natürlichen Zahlen war das anders: Hier hatten wir zuerst eine anschauliche Vorstellung davon, was natürliche Zahlen sind, und haben erst anschließend versucht, diese anschauliche Vorstellung durch das formale System der Peano-Arithmetik zu präzisieren. Und nun hat uns ausgerechnet diese Präzisierung gezeigt, dass durch die Peano-Axiome alleine unsere intuitive Vorstellung von natürlichen Zahlen nicht eindeutig eingefangen wird. Die Peano-Axiome lassen die Existenz merkwürdiger Objekte zu, die nicht mit unserer Vorstellung von natürlichen Zahlen übereinstimmen.

Wir sehen hier ein Phänomen, das in der Mathematik häufig anzutreffen ist: Man beginnt mit intuitiven mathematischen Konzepten. Irgendwann tauchen Fragen auf, die sich mit Hilfe der intuitiven Konzepte nicht mehr eindeutig beantworten lassen. Daher versucht man, die intuitiven Konzepte zu präzisieren und ein entsprechendes formales System aufzubauen, das auch diese komplexeren Fragen beantworten kann. Aber es gibt unerwartete Nebeneffekte:
Zum einen kann auch das formale System nicht alle Fragen beantworten, die sich innerhalb der intuitiven Konzepte stellen lassen (das zeigt Gödels Unvollständigkeitssatz) - noch nicht einmal die Widerspruchsfreiheit des Systems lässt sich beweisen!
Zum anderen zeigt das formale System neue Möglichkeiten auf, die in den intuitiven Konzepten gar nicht erkennbar waren. So lässt die Peano-Arithmetik die Existenz übernatürlicher Zahlen zu.

Häufig war es in der mathematischen Geschichte nun so, dass man bei der Präzisierung intuitiver mathematischer Konzepte auf unerwartete Effekte und Möglichkeiten stieß, an die man sich erst langsam gewöhnen musste. Erst im Laufe der Zeit wurde ihre Bedeutung klar, und man verstand den Hintergrund. Einige Beispiele:

1
Beim Versuch, die euklidische Geometrie zu axiomatisieren, stellte man fest, dass die ersten vier geometrischen Axiome Euklids mit verschiedenen Versionen des Parallelenaxioms verträglich sind. Das eröffnete die Möglichkeit für verschiedene Geometrien: die euklidische, die elliptische und die hyperbolische Geometrie. Alle diese Geometrien sind heute nützlich, insbesondere in der Physik (man denke an die allgemeine Relativitätstheorie).

2
Als man sich über mathematische Funktionen und ihre Darstellung als Kurven Gedanken machte, tauchten Fragen nach der Glattheit einer solchen Kurve auf. Man erkannte, dass sich viele Kurven in einem Stück zeichnen lassen, ohne dass man beim Zeichnen den Stift absetzen musste. Weiterhin waren die meisten Kurven glatt, d.h. sie wiesen keine Ecken (d.h. keine plötzlichen Richtungswechsel) auf. Um diese intuitiven Konzepte zu präzisieren, definierte man schließlich den Begriff der Stetigkeit (d.h. man muss den Stift nicht absetzen) und den Begriff der Differenzierbarkeit (d.h. es gibt keine Ecken). Es war eine große Überaschung, als man herausfand, dass sich eine überall stetige, aber nirgends differenzierbare Kurve definieren ließ, also eine Kurve, die sich in einem Stück durchzeichnen lässt, aber die an jeder Stelle eine Ecke besitzt. An eine solche Kurve hatte bei der Definition von Stetigkeit und Differentierbarkeit niemand gedacht, und dennoch erlaubten die neuen Begriffe diese Möglichkeit.

3
Bereits die Griechen der Antike hatten sich über die mathematische Beschreibung von Entfernungen und Längen Gedanken gemacht. Natürliche Zahlen eignen sich zwar zum Zählen, nicht aber zur Angabe beliebiger Längen. Die Griechen kamen daher auf die Idee, Längen durch Brüche anzugeben. So ist jedem klar, was mit 2/3 Meter gemeint ist: Man teilt einen Meter in drei gleich große Teile und legt davon zwei hintereinander. Nun glaubten die Griechen, dass sich jede beliebige Länge exakt durch einen Bruch ausdrücken lässt. Diese Annahme war naheliegend, denn man fand heraus, dass sich zwischen zwei beliebigen Brüchen immer noch ein weiterer Bruch befand, egal wie nahe die beiden Brüche bereits einander waren. Dazu braucht man einfach nur den Mittelwert der beiden Brüche zu bilden. So befindet sich zwischen den beiden Brüchen 7/1000 und 8/1000 der Bruch 15/2000 . Man sagt, die Brüche liegen dicht hintereinander, d.h. in jedem noch so kleinen Zwischenraum liegen unendlich viele Brüche. Damit lassen sich Längen immer beliebig genau durch Brüche angeben.
"Beliebig genau" ja, aber eben nicht ganz genau. Die Griechen waren sehr überascht, als sie herausfanden, dass sich beispielsweise die Diagonale eines Quadrats mit Kantenlänge Eins nicht durch einen Bruch ausdrücken lässt. Man kommt zwar mit Brüchen beliebig nahe heran, aber die Länge der Diagonalen selbst ist kein Bruch (der Satz von Pythagoras zeigt, dass die Diagonale die Länge "Wurzel aus 2" hat, und man kann rel. leicht zeigen, dass kein Bruch mit sich selbst multipliziert die Zahl 2 ergeben kann). Erst die Definition des Begriffs der reellen Zahlen löste das Problem. Und wieder war man sehr überascht, als man herausfand, dass sich reelle Zahlen nicht in einer Liste vollständig erfassen lassen (der Beweis erfolgt mit Hilfe von Cantors Diagonalverfahren, das wir ja bereits gut kennen). Brüche dagegen lassen sich in einer unendlichen Liste erfassen, z.B. so:
1, 1/2, 2, 1/3, 2/2, 3, 1/4, 2/3, 3/2, 4, 1/5, 2/4, 3/3, 4/2, 5, ...
Erkennen Sie das Schema?

4
Zu Beginn der Neuzeit beschäftigte man sich häufig mit Berechnungen, die Quadratwurzeln enthielten. Leider war es dabei oft ein Hindernis, dass die Quadratwurzel einer negativen Zahl nicht definiert war, denn das Quadrat jeder Zahl ist positiv. Wenn man sich aber einfach nicht um dieses Problem kümmerte und rein schematisch in Rechen-Zwischenschritten mit Wurzeln negativer Zahlen rechnete, so erhielt man dennoch sinnvolle Ergebnisse. So kam man auf die Idee, Rechnungen dieser Art zu formalisieren, indem man die Wurzel aus (-1) einfach als "I" (Abkürzung für "imaginäre Einheit" bezeichnete und Rechenregeln für I aufstellte. Eine dieser Regeln lautet: I*I=(-1) .
Bie vielen Mathematikern rief diese Vorgehensweise lauten Protest hervor: Was für eine Zahl sollte I denn sein? Der Name sagt es ja schon: "imaginäre Einheit". In der Vorstellung war I ein merkwürdiges, imaginäres Objekt, das man zwar wie eine Zahl handhaben konnte, das aber keine reelle Zahl war. Dennoch war formal alles in Ordnung: man konnte präzise Rechenregeln für I aufstellen. Das folgende Zitat des deutschen Philosophen und Mathematikers Gottfried Wilhelm Leibniz (1648-1716) zeigt uns, wie die damaligen Mathematiker über I dachten:
"Der göttliche Geist hat eine feine und wunderbare Ausflucht gefunden in jenem Wunder der Analysis, dem Monstrum der realen Welt, fast ein Amphibium zwischen Sein und Nicht-Sein, welches wir die imaginäre Einheit nennen."
Und der schweizerische Mathematiker Leonhard Euler (1707-1783) schrieb:
"... so ist klar, dass die Quadratwurzeln von Negativ-Zahlen nicht einmal unter die möglichen Zahlen können gerechnet werden: folglich müssen wir sagen, dass dieselben ohnmögliche Zahlen sind. Und dieser Umstand leitet uns auf den Begriff von solchen Zahlen, welche ihrer Natur nach ohnmöglich sind, und gemeiniglich imaginäre Zahlen, oder eingebildete Zahlen genennt werden, weil sie bloß allein in der Einbildung statt finden."
Die Aufregung legte sich erst, als Carl Friedrich Gauß (1777-1855) den Begriff der Multiplikation von Zahlen erweiterte auf die Multiplikation von Pfeilen in der zweidimensionalen Ebene. Eine reelle Zahl ist dabei ein Pfeil entlang der x-Achse, und I ist der Pfeil entlang der y-Achse mit Länge Eins. Die Multiplikation eines Pfeils mit einem anderen Pfeil entspricht dabei einer Drehstreckung: die Längen der Pfeile werden multipliziert, und die Winkel zur x-Achse werden addiert. Und so bekommt die Formel I*I=(-1) plötzlich eine anschauliche Bedeutung.


Mit den übernatürlichen Zahlen geht es uns nun so ähnlich wie unseren Vorfahren vor 200 Jahren mit der imaginären Einheit I. Wir können zwar formal im System Peano-Arithmetik inclusive "NICHT G" damit umgehen, aber wir haben kein intuitives Konzept davon, was das bedeutet. Für uns sind übernatürliche Zahlen zunächst lediglich irgendwelche Objekte, deren Regeln durch das formale System festgelegt sind.

Nun arbeitet aber ein Mathematiker nicht wie ein formales System. Menschen denken eher in Bildern, nicht so sehr in Formeln. Es ist daher wichtig, eine intuitive Vorstellung von den mathematischen Begriffen zu entwickeln. Dies ist auch sicher der Grund für das Unbehagen, dass unsere Vorfahren bei der Verwendung von I beschlich. Man möchte wissen, was vor sich geht.

Man kann sich übernatürliche Zahlen als Objekte vorstellen, die größer als alle natürlichen sind, also als unendlich große ganze Zahlen. Die Peano-Axiome erlauben den Umgang mit solchen unendlich großen Größen, obwohl dies zunächst gar nicht beabsichtigt war.

Aber wie groß ist nun beispielsweise die übernatürliche Zahl y, die eine Beweisnummer zu G ist? Die Antwort, die uns das formale System gibt, ist die folgende: Sie muss so groß sein, dass sie Struktur eines Beweises von G geeignet spezifiziert. Das hilft uns zwar zunächst nicht wirklich weiter, aber mehr Information gibt das formale System nicht her. Weiter unten mehr dazu!

Übernatürliche Zahlen sind nützlich! Man kann mit Ihrer Hilfe über-reelle Zahlen definieren und ein komplettes Gebiet der Mathematik analog zur gewohnten Analysis aufbauen: die sogenannte Nicht-Standard-Analysis. So kann man die bei Physikern sehr beliebten infinitesimalen Größen wie dx und dy als Kehrwerte von über-reellen Zahlen auffassen. Das bei Mathematikern verpönte, bei Physikern dafür umso beliebtere direkte Rechnen mit Ausdrücken wie dy/dx kann auf einmal mathematisch sauber definiert werden! Wer sich dafür interessiert, findet die Details dazu in Kapitel 4.5.


Es gibt einen Weg, übernatürliche Zahlen explizit zu konstruieren und dadurch eine gewisse anschauliche Vorstellung von Ihnen zu gewinnen (siehe Kapitel 4.5 sowie www.wikipedia.com/wiki/Hyperreal_numbers ). Dabei muss man ähnlich wie bei den komplexen Zahlen vorgehen: Man sucht mathematische Objekte, von denen eine Teilmenge sich wie gewöhnliche (natürliche bzw. reelle) Zahlen verhält, eine anderer Teilmenge jedoch die gewünschten Eigenschaften aufweist, die natürliche bzw. reelle Zahlen nicht aufweisen. Genauso ging Gauß vor, als er komplexe Zahlen mit zweidimensionalen Vektoren identifizierte, wobei Vektoren entlang der x-Achse den reellen Zahlen entsprechen.

Um natürliche und übernatürliche Zahlen darzustellen, wollen wir versuchen, sie mit unendlichen natürlichen Zahlenfolgen zu identifizieren. Eine natürliche Zahl entspricht dabei einer Zahlenfolge, die diese natürliche Zahl endlos wiederholt. Die natürliche Zahl 1 entspricht also der Zahlenfolge (1,1,1,1,...), die 2 entspricht der Zahlenfolge (2,2,2,2,...) und so weiter. Eine übernatürliche Zahl würde dann einer nicht-konstanten Zahlenfolge entsprechen, z.B. der Zahlenfolge (1,2,3,4,...).

Die Addition und Multiplikation zweier Zahlenfolge ist nun einfach dadurch definiert, dass man die einzelnen Einträge Stück für Stück addiert bzw. multipliziert. So ist (n,n,n,...) + (m,m,m,...) = (n+m, n+m, n+m, ...) und (n,n,n,...) * (m,m,m,...) = (n*m, n*m, n*m, ...). Für konstante Folgen ist unmittelbar klar, dass damit die gewohnten Rechenregeln mit natürlichen Zahlen auf das Rechnen mit Folgen übertragen werden, denn man führt ja dieselbe Rechenoperation einfach nur mit unendlich vielen Kopien durch.

Auch bei nicht-konstanten Folgen addieren bzw. multiplizieren wir die entsprechenden Einträge, d.h. allgemein legen wir fest:

Auch hier können wir nachprüfen, dass alle gewohnten Rechenregeln auch für die so definierte Addition und Multiplikation von Zahlenfolgen gelten.

Wir wollen aber nicht nur die Addition und Multiplikation von natürlichen und übernatürlichen Zahlen abbilden. Auch alle anderen Eigenschaften, die sich aus den Axiomen ergeben, wollen wir darstellen. So wollen wir bei zwei Zahlenfolgen sagen können, welche von beiden größer ist, oder wann beide gleich groß sind. So soll z.B. y+1 > y gelten, auch wenn y eine übernatürliche Zahl ist (also nicht durch eine konstante Zahlenfolge dargestellt wird).

Betrachten wir beispielsweise die beiden Zahlenfolgen a = (5,6,7,8,9,...) und b = (2,4,6,8,10,12,...). Welche von beiden soll die größere sein?

Diesmal können wir nicht einfach Eintrag für Eintrag miteinander vergleichen, denn bei den ersten drei Elementen ist a größer, ab dem fünften Element ist dagegen b größer. Wir müssen festlegen, welche Einträge für den Vergleich relevant sein sollen. Dabei sollen aber auf jeden Fall unendlich viele Einträge berücksichtigt werden, denn sonst hätten wir nicht unendliche Zahlenfolgen betrachten müssen.

Wir wollen hier nicht ins Detail gehen, wie man festlegt, welche Einträge relevant sein sollen. Mathematiker sprechen davon, dass eine solche Festlegung durch einen freien Ultrafilter, gegeben ist. Details dazu siehe Kapitel 4.5. Uns soll hier einfach genügen, dass es irgendwie geht, die relevanten Einträge festzulegen. Im obigen Beispiel würden wir z.B. sagen, dass alle Einträge ab der fünften Stelle relevant sind, d.h. a ist kleiner als b .

Generell legt man nicht im Voraus für beliebige Folgen fest, welche Einträge relevant sind, sondern man wählt zu Beginn eine bestimmte Menge aus zueinander verträglichen Festlegungen (den sogenannten Ultrafilter) und sucht dann zum Vergleich zweier konkreter Zahlenfolgen eine passende Festlegung aus dieser einmal gewählten Menge aus. Man kann zeigen, dass man in der Menge aus zueinander verträglichen Festlegungen immer eine Festlegung finden kann, die diesen Vergleich zweier Zahlenfolgen eindeutig macht, d.h. dass alle relevanten Einträge der einen Folge kleiner (bzw. größer bzw. gleich) als die der anderen Zahlenfolge sind. Wichtig ist immer, dass unendlich viele Einträge als relevant berücksichtigt werden. Und man kann auch zeigen, dass die einmal gewählte Menge aller zueinander verträglichen Festlegungen keine zweite Festlegung enthält, bei der aus "a ist kleiner als b" auf einmal "a ist größer als b" würde - genau dies bedeutet verträglich. Es gibt übrigens mehrere Möglichkeiten, eine Menge aus zueinander verträglichen Festlegungen aufzustellen. Man muss sich nur für eine davon entscheiden (egal, welche) und dann für alle Vergleiche bei dieser Menge bleiben, aus der man dann passende Index-Festlegungen auswählen kann.

Man definiert also für eine vorgegebene Menge aus zueinander verträglichen Index-Festlegungen (nennen wir sie U für Ultrafilter):

Weiterhin legen wir fest, dass zwei Folgen a und b gleich sind, wenn a kleiner-gleich b und b kleiner-gleich a ist. Es gibt also viele Folgen, die die gleiche natürliche und übernatürliche Zahl repräsentieren. So repräsentiert auch die Folge (2,3,2,2,2,5,2,2,...) die Zahl 2, wenn nur endlich viele Einträge ungleich 2 sind.

Betrachten wir nun die Folge y = (1,2,3,4,5,...) und fragen, wie groß die dadurch repräsentierte übernatürliche Zahl y ist. Die oben getroffenen Festlegungen führen dazu, dass diese Zahl größer ist als jede natürliche Zahl n (dargestellt durch eine konstante Zahlenfolge (n,n,n,...) ). Denn für den Größenvergleich zählen wir einfach diejenigen Einträge als relevant, ab denen die aufsteigenden Einträge von y größer als n sind - und das sind immer unendlich viele Einträge, während nur endlich viele Einträge weggelassen wurden.

Damit haben wir eine Darstellung für eine übernatürliche Zahl gefunden, die größer als jede natürliche Zahl ist. Und es gibt noch größere übernatürliche Zahlen. So ist y+1 = (2,3,4,5,...) um 1 größer als y . Die Folge (2,3,4,5,...) ist der NACHFOLGER der Folge (1,2,3,4,...). Damit wird auch klar, dass eine übernatürliche Zahl nicht als NACHFOLGER der natürlichen Zahl Null (dargestellt durch die Folge (0,0,0,...) ) dargestellt werden kann.

Wir können nun alle Peano-Axiome auch für solche Folgen und damit für übernatürliche Zahlen nachweisen. Unser formales System ist damit in der Lage, solche Folgen zu beschreiben - eine Interpretation, an die wir damals überhaupt nicht gedacht haben!

Im Grunde fasst man in unendlich großen Zahlen den üblichen Grenzwertprozess (n geht gegen Unendlich) aus der Standard-Analysis in einem mathematischen "Zahl-Objekt" kompakt zusammen. Und das tut man gerade so, dass Beziehungen wie n+1>n erhalten bleiben, auch wenn n gegen Unendlich geht. Das Anwachsen von n bis Unendlich wird dadurch abgebildet, dass man die gesamte unendliche Zahlenfolge, die n beim Anwachsen durchschreitet, zu einem einzigen mathematischen Objekt zusammenfasst.

Ganz analog lassen sich auch übernatürliche reelle Zahlen definieren. Diese umfassen dann auch unendlich kleine (also infinitesimale) Zahlen, die sich z.B. durch Folgen wie (1, 1/2, 1/3, 1/4, ...) darstellen lassen. Auf diese Weise erhält man eine mathematisch präzise Beschreibung von den in der Physik und den Ingenieurwissenschaften so beliebten infinitesimalen Ausdrücken wie dx und dy - wir hatten es oben bereits erwähnt. Weiteres dazu siehe Kapitel 4.5.


Mit dieser Veranschaulichung übernatürlicher Zahlen wollen wir uns nun noch einmal den Gödelschen Ausdruck   "NICHT G"   ansehen, der uns auf die Möglichkeit übernatürlicher Zahlen aufmerksam gemacht hat. Wie können wir   "NICHT G"   interpretieren und damit den scheinbaren Widerspruch auflösen, der uns oben beschäftigt hat?

"NICHT G" war der Ausdruck   "ES_GIBT y: B(m,y)"   . Gleichzeitig wissen wir, dass für jede natürliche Zahl g der Ausdruck   "NICHT B(m,g)"   beweisbar ist. Das von   "NICHT G"   behauptete y muss also eine übernatürliche Zahl sein, die durch eine nicht-konstante Zahlenfolge dargestellt werden kann.

Überlegen wir uns noch einmal, wie man ermittelt, ob B(m,g) oder "NICHT B(m,g)" für natürliche Zahlen m und g beweisbar ist: Man sucht aus der Liste aller wohlgeformten Aussagen mit einer freien Variablen die m-te heraus und bildet das Diagonalelement. Anschließend sucht man aus der Liste aller Beweise den g-ten heraus und sieht nach, ob er einen Beweis zum Diagonalelement ist. Falls ja, so ist B(m,g) beweisbar, andernfalls ist "NICHT B(m,g)" beweisbar. Dieser Algorithmus hält garantiert an, wenn m und g natürliche Zahlen sind, d.h. B(m,g) ist für natürliche Zahlen m und g entscheidbar (d.h. entweder B(m,g) oder "NICHT B(m,g)" sind beweisbar).

Wie sieht es nun aus, wenn wir eine übernatürliche Zahl y als Beweisnummer einsetzen? In diesem Fall läuft der obige Algorithmus auf ein Problem: Er versucht, den Beweis mit Nummer y zu finden, doch diese Suche läuft ergebnislos immer weiter, denn beim Absuchen der Beweisliste findet der Algorithmus keine y-te Zeile (alle Zeilennummern sind natürliche Zahlen, aber y ist größer als jede dieser Zahlen). Daher kann der Algorithmus nicht entscheiden, ob B(m,y) oder "NICHT B(m,y)" vorliegt, und wir können gefahrlos einfach behaupten, dass B(m,y) vorliegt - genau das tun wir ja, wenn wir "NICHT G" als Axiom hinzufügen.

Aber was bedeutet es, wenn wir behaupten, B(m,y) liegt vor? Es bedeutet nicht, dass es einen Beweis von G innerhalb der Peano-Arithmetik gibt, denn der obige Algorithmus findet keinen entsprechenden Beweis. Die Interpretation, dass Beweisbarkeit von B(m,y) die Existenz eines Beweises von G in der Peano-Arithmetik bedeutet, ist nur für natürliche Zahlen y sinnvoll, denn dann ist Beweisbarkeit von B(m,y) gleichbedeutend damit, dass ein Beweis in der Peano-Arithmetik-Beweisliste gefunden werden konnte.

Welche andere Interpretation von B(m,y) gibt es dann für ein übernatürliches y? Tatsächlich könnte es möglich sein, B(m,y) so zu interpretieren, dass es die Existenz eines Beweises von G außerhalb der Peano-Arithmetik ausdrückt. Einen solchen Beweis gibt es nämlich, denn im Jahr 1936 konnte Gerhard Gentzen die Widerspruchsfreiheit der Peano-Arithmetik beweisen (siehe Wikipedia: Gentzen's consistency proof ), und daraus folgt wiederum die Aussage G, wie wir aus Kapitel 2.6 wissen. Für den Beweis verwendete Gentzen bestimmte Baumstrukturen, die über die Fähigkeiten der Peano-Arithmetik hinausgehen -- man muss gleichsam über die natürlichen Zahlen hinaus weiterzählen können, um den Beweis durchzuführen (transfinite Induktion, mehr dazu siehe Kapitel 4.6 ). Das passt gut zu der Übernatürlichkeit von y in B(m,y).

Fassen wir noch einmal zusammen, was geschieht, wenn wir   "NICHT G"   als Axiom hinzunehmen:


Was halten Sie von folgender Behauptung, die man manchmal in populären Texten findet?

Uff -- das hört sich ja erst mal plausibel an, aber wir sollten es nun besser wissen! So hat G nur dann die Bedeutung "Ich bin nicht in dem formalen System F beweisbar", wenn wir für die Beweis-Variable y in G nur natürliche Zahlen zulassen. Damit wählen wir eine Interpretation (ein Modell), in der G wahr ist. Es gibt aber andere Interpretationen, in denen G die folgende Bedeutung haben könnte: "Ich bin nicht in einem übergeordneten formalen System F' beweisbar" (d.h. es gibt keine übernatürliche Beweiszahl y). Das kann falsch sein, denn in dem übergeordneten System F' lässt sich vielleicht die Widerspruchsfreiheit von F zeigen, woraus wiederum G folgt.

Es ist also keineswegs so, dass G wahr ist und wir das im Gegensatz zum formalen System F erkennen. Wir haben in der Behauptung lediglich eine Interpretation gewählt, in der G wahr ist, indem wir für die Variablen nur natürliche Zahlen zugelassen haben. Diese Interpretation ist aber nicht zwingend für das formale System F.

Falls wir nur natürliche Zahlen für die Variablen zulassen, so erkennt das formale System F übrigens dasselbe wie wir: Aus der Aussage CONS (siehe Kapitel 2.6) folgt G, wobei CONS für die Widerspruchsfreiheit steht und G für die Aussage Ich bin nicht in F beweisbar. F sagt uns also in dieser Interpretation: Wenn ich widerspruchsfrei bin, dann ist G nicht beweisbar. Das ist genau das, was wir auch erkennen können, denn auch wir müssen Widerspruchsfreiheit voraussetzen.

Wenn wir dagegen auch übernatürliche Zahlen für die Variablen zulassen, dann muss CONS nicht mehr unbedingt für die Widerspruchsfreiheit von F stehen, und auch G behauptet nicht mehr, dass es nicht beweisbar sei. Wenn wir "NICHT G" als Axiom hinzunehmen, so folgt daraus "NICHT CONS" (denn aus CONS folgt ja G) -- also bedeutet "NICHT CONS" offenbar irgendetwas anderes, aber jedenfalls nicht Widersprüchlichkeit von F.

Man sieht, wie vorsichtig man sein muss, denn Wahrheit kann von der Interpretation abhängen! Wenn man es aber richtig macht, so passt alles wunderbar zusammen und scheinbare Widersprüche lösen sich in Luft auf. Wer mehr zu Modellen und Interpretationen wissen möchte, findet Details dazu in Kapitel 4.4 . Dort findet man auch Gödels Vollständigkeitssatz der klassischen Logik:

Ein formales System ist also sehr wohl in der Lage, universell wahre Aussagen auch zu beweisen. Keiner kann es ihm jedoch verdenken, wenn es den Beweis zu verweigert, sobald Wahrheit von der Interpretation abhängt.


zurück zum Inhaltsverzeichnis

last modified on 15 April 2008