Der Erste Unvollständigkeitssatz

von Kurt Gödel

Diplomarbeit
zur Erlangung des Magistergrades
an der Naturwissenschaftlichen Fakultät
der Universität Salzburg
eingereicht von Martin Thomaschütz

Salzburg, April 2001

Gewidmet der überabzählbar unendlichen Geduld meiner Eltern.

Mein Dank gilt Prof. Czermak für die Betreuung dieser Arbeit, für viele

interessante Vorlesungsstunden und für den pädagogischen Grundsatz:

Wer sich fürchtet, traut sich nicht fragen und wird daher auch nichts lernen."

Inhaltsverzeichnis

1 Die Grundlagenkrise der Mathematik 1
1.1 Cantors Mengentheorie 1
1.2 Die Paradoxa 3
1.2.1 Cantors Paradoxon (1899) 3
1.2.2 Russells Paradoxon (1902) 3
1.2.3 Das Paradoxon des Epimenides (auch: Lügnerparadoxon, um 600 v. Chr.) 4
1.2.4 Das Paradoxon des Proklos (um 450 n. Chr.) 4
1.2.5 Das Paradoxon von Grelling (1908) 5
1.2.6 Das Paradoxon von Berry (1906) 5
1.3 Wege aus dem Dilemma der Paradoxa 5
1.3.1 Die Einschränkung des Mengenbegriffes 6
1.3.2 Vermeidung von Selbstbezüglichkeit 7
1.3.3 Der Logizismus 8
1.3.4 Der Konstruktivismus 9
1.3.5 Der Formalismus (Metamathematik) 11
2 Grundlagen 13
2.1 Cantors Diagonalmethode 13
2.1.1 Die Überabzählbarkeit von R und P(N) 13
2.1.2 Die Überabzählbarkeit von P(M) für unendliche Mengen 18
2.1.3 Die Beweisidee der Diagonalmethode 20
2.2 Formale Systeme 20
2.2.1 Das MIU-System 20
2.2.2 Das pg-System 24
2.3 Formales Axiomensystem der Arithmetik (nach Peano) 29
2.3.1 Formale Sprache des PA-Systems 30
2.3.2 Axiome des PA-Systems 37
2.3.3 Schlussregeln 40
2.3.4 Beispiele für Beweise im PA-System 41
2.3.5 Ausdrückbar und repräsentierbar 43
2.3.6 -Unvollständigkeit und -Widersprüchlichkeit 44

ii

iii

3 Der Beweis 46
3.1 Beweisidee 47
3.2 Schritt 1: Gödelisierung 48
3.2.1 Ebene 1: Motivation 48
3.2.2 Ebene 2: Einfache Gödelisierungen 49
3.2.3 Ebene 3: Vollständige Gödelisierung des PA-Systems 57
3.3 Schritt 2: Aussagekraft des PA-Systems 60
3.3.1 Ebene 1: Motivation 60
3.3.2 Ebene 2: Programme mit begrenzten Schleifen 64
3.3.3 Ebene 3: Primitiv-rekursive Funktionen 71
3.4 Schritt 3: Im PA-System repräsentierte Funktionen 87
3.4.1 Ebene 1: Motivation 87
3.4.2 Ebene 2: Uninteressante" Unvollständigkeit 87
3.4.3 Ebene 3: Beweisidee für die Repräsentierbarkeit der primitiv-rekursiven Prädikate 88
3.5 Schritt 4: Diagonalmethode und Konstruktion von G 90
3.5.1 Ebene 1: Motivation 90
3.5.2 Ebene 2: Die Selbstbezüglichkeit im PA-System 91
3.5.3 Ebene 3: Das Diagonallemma 96
4 Folgerungen und Folgen 102
4.1 Folgerungen aus dem ersten Unvollständigkeitssatz 102
4.2 Folgen für die Mathematik 104
A Anhang 106
A.1 Formales System der Peano-Arithmetik (PA-System): 106
A.2 Einfache Gödelnummerierung des PA-Systems 107
A.3 Vollständige Gödelnummerierung des PA-Systems 107
A.4 Beweis für die Existenz nicht-primitiv-rekursiver Funktionen . . 108
A.5 Beweis für Lemma I aus 3.3.3 110

Kapitel 1

Die Grundlagenkrise der Mathematik

1.1 Cantors Mengentheorie

In der zweiten Hälfte des 19. Jahrhundert gelang es Georg Cantor (1845­1918), die verschiedenen Teilgebiete der Mathematik auf eine einheitliche Grundlage zu stellen: die Mengentheorie. Damit konnte man die natürlichen Zahlen definieren (als Äquivalenzklassen verschiedener Begriffsumfänge ­Grundlage der Zahlentheorie), die ganzen und die rationalen Zahlen (als geordnete Paare ganzer Zahlen) und die reellen Zahlen (z. B. durch unendliche Dezimalbrüche oder mittels Dedekindscher Schnitte ­ Grundlage der Analysis).

Die Geometrie ließ sich schon seit Ren´e Descartes (1596­1650) analytisch, d. h. mittels reeller Zahlen betreiben. Alles konnte zurückgeführt werden auf den Begriff der Menge, den Cantor folgendermaßen definierte: Unter einer Mannigfaltigkeit" oder Menge" verstehe ich nämlich allgemein jedes Viele, welches sich als Eines denken lässt, d. h. jeden Inbegriff bestimmter Elemente, welcher durch ein Gesetz zu einem Ganzen verbunden werden kann,[. . . ][2]

Eine Menge ist also eine Zusammenfassung von bestimmten, wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens zu einem Ganzen. Die Objekte heißen Elemente der Menge. Zwei Mengen sollen als gleichmächtig gelten, wenn es zwischen ihnen eine umkehrbar eindeutige (bijektive) Abbildung gibt, d. h. wenn man jedem Element der einen Menge genau ein Element der anderen Menge zuordnen kann. So lässt sich sehr leicht feststellen, ob die Anzahl der Studenten in einem Hörsaal (Menge A) gleich groß ist der Anzahl der Stühle im Hörsaal (Menge B), indem man die Studenten bittet, sich zu setzen. Bleibt kein Platz frei und muss kein Student mehr stehen, besteht eine umkehrbar eindeutige Abbildung zwischen der Menge A der Studenten und der Menge B der Stühle. Daher sind A und B gleichmächtig.