Hyperzirkularität und Berechenbarkeit. Metamathematische und philosophische Implikationen der Unvollständigkeit axiomatischer Systeme der Peano-Arithmetik

Master's Thesis , 2015 , 108 Pages , Grade: 1,00

Philosophy - Miscellaneous

Die heutige Erkenntnistheorie kann über die Ergebnisse der Grundlagenforschung der Mathematik nicht hinwegsehen. Die Resultate der Metamathematik sind nicht nur für die Philosophie der Mathematik, sondern auch für andere Disziplinen der Philosophie von herausragender Bedeutung. Schon die offenkundige strukturelle Isomorphie semantischer Paradoxien und formaler Konstruktionen der Metamathematik weist auf eine immanente Verwandtschaft der Problemstellung und des möglichen Lösungsansatzes hin. Während jedoch die Beschäftigung mit semantischen Paradoxien schon sehr früh als unfruchtbare Betätigung abgegolten wurde, zeigte sich die Metamathematik als fruchtbares und alles andere als triviales und apriorisches Gebiet philosophischer Erkenntnis. Dieser Fortschritt eröffnete nicht nur neue Bereiche innerhalb der Metamathematik und Mathematik selbst, sondern gab Anlass zur Annahme, dass auch eine Klärung der semantischen Paradoxien nicht mehr abwegig war. Dies mündete in der Erforschung der Möglichkeit der Definition eines adäquaten Wahrheitsbegriffes im Rahmen axiomatischer und philosophischer Wahrheitstheorien.

Diese Arbeit stellt sämtliche wesentlichen Resultate von Gödel und seinen Nachfolgern detailliert und Vollständig dar. Einige Beweisschritte wurden zum ersten mal systematisch aufbereitet. Zudem werden die Resultate in ihrem historischen und systematischen Kontext gewertet. Darauf aufbauend werden zuletzt Implikationen für die Philosophie abgeleitet.

Inhaltsverzeichnis

Abbildungsverzeichnis

I Einführung und Grundlagen
1 ÜberblickundFragestellungen
2 Historischer und ideengeschichtlicher Kontext
2.1 Arithmetische und mengentheoretische Preliminarien
2.2 Allgemeines zu formalen Systemen

II Metamathematik
3 Die semantische Variante des ersten Gödelschen Unvollständigkeitssatzes
4 Die schwache syntaktische Variante der Unvollständigkeitssätze
4.1 Der Aufbau der Gödelschen Originalarbeit 1931
4.2 Das System P
4.2.1 Definition der Syntax
4.2.2 Definition der Semantik
4.2.3 Definition der Axiome und Schlussregeln
4.2.4 Gödelisierung: Die Arithmetisierung der Syntax
4.2.5 Ein Vergleich des Systems P mit dem System der Principia Mathematica
4.3 Primitiv-rekursive Funktionen
4.4 Satz V: Der Zusammenhang zwischen dem System P und den primitiv-rekursiven Funktionen
4.5 Satz VI: ω -Widerspruchsfreiheit
4.6 Die schwache syntaktische Variante des ersten Unvollständigkeitssatzes
4.7 Der zweite Unvollständigkeitssatz
4.8 Zwischenbetrachtung: Das Diagonallemma
5 Die starke syntaktische Variante der Unvollständigkeitssätze
6 Nichtstandardmodelle der Peano-Arithmetik: Unvollständigkeit ohne Selbst- bezüglichkeit?
6.1 Grundlagen der Modelltheorie
6.2 Das Skolem-Gödel-Theorem
6.3 Der Vollständigkeitssatz
6.4 Satz von Löwenheim-Skolem
6.5 Unvollständigkeit modelltheoretisch: Kripkes Beweisskizze des ersten Unvoll- ständigkeitssatzes
6.6 Kommt Kripkes’ Beweis ohne Selbstbezüglichkeit aus?
7 Fünf Fehlinterpretationen der metamathematischen Resultate
8 Das natürliche Unabhängigkeitsphänomen der Goodstein-Folgen
8.1 Die Definition der Goodstein-Folgen
8.2 Der Satz von Goodstein
8.3 Der Satz von Kirby und Paris

III Erkenntnistheorie
9 Die Church-Turing-These
9.1 Berechenbarkeit
9.2 Die Turing-Maschine
9.3 Registermaschinen
9.4 Die Church-These
10 Der Antimechanismus
10.1 Einführung in die Lucas-Penrose-Debatte
10.2 Das Argument von Lucas
10.3 Slezaks externer Betrachter
10.4 Benacerrafs Analyse
10.5 Whiteleys Bemerkung
11 Das Phänomen der Hyperzirkularität
12 Schlussbetrachtungen und Ausblick

Literaturverzeichnis

Personen- und Sachverzeichnis

Abbildungsverzeichnis

3.1 Drei Varianten des ersten Unvollständigkeitssatzes

3.2 Selbstreflexive Sätze der natürlichen Sprache

3.3 Darstellung des Diagonalargumentes I

3.4 Darstellung des Diagonalargumentes II

Teil I Einführung und Grundlagen

Kapitel Überblick und Fragestellungen

Philetas of Cos am I, ’ Twas the Liar who made me die, And the bad nights caused thereby.

Epigraph des Philetas in Übersetzung von Stock, S. G. W. J.: Stoicism. A. Constable & Company, 1908

Die heutige Erkenntnistheorie kann über die Ergebnisse der Grundlagenforschung der Mathematik nicht hinwegsehen. Die Resultate der Metamathematik sind nicht nur für die Philosophie der Mathe- matik, sondern auch für andere Disziplinen der Philosophie von herausragender Bedeutung. Schon die offenkundige strukturelle Isomorphie semantischer Paradoxien und formaler Konstruktionen der Metamathematik weist auf eine immanente Verwandtschaft der Problemstellung und des möglichen Lösungsansatzes hin. Während jedoch die Beschäftigung mit semantischen Paradoxien schon sehr früh als unfruchtbare Betätigung abgegolten wurde, zeigte sich die Metamathematik als fruchtbares und alles andere als triviales und apriorisches Gebiet philosophischer Erkenntnis. Dieser Fortschritt eröffnete nicht nur neue Bereiche innerhalb der Metamathematik und Mathematik selbst, sondern gab Anlass zur Annahme, dass auch eine Klärung der semantischen Paradoxien nicht mehr abwegig war. Dies mündete in der Erforschung der Möglichkeit der Definition eines adäquaten Wahrheitsbegriffes im Rahmen axiomatischer und philosophischer Wahrheitstheorien.¹

Dennoch blieben viele dieser Ergebnisse engen Kreisen von Mathematikern und Logikern vorbehal- ten. Es hat so den Anschein, dass die erkenntnistheoretische Relevanz der Resultate nicht genügend antizipiert wird. Dies hat sowohl programmatische als auch praktische Gründe. Zum einen wird die formalisierte Herangehensweise an die Wirklichkeit oftmals als eine unzulässige Abstraktion derselben entwertet. Selbst erkenntnistheoretische Standpunkte, die in ihrer Architektonik den Versuch unter- nehmen, ”reinesDenken“zufiltrieren,verneineneineÄquivalenzzwischendiesemundderdeduktiven Methode des axiomatischen Formalismus. Zum anderen sind aber die Arbeiten von Gödel, Rosser, Church, Kripke, Tarski, Turing, Kleene und anderen Vorreitern der Metamathematik in ihrer forma- len Darstellungsweise für Außenstehende meist unzugänglich. Obwohl neuere Werke, wie beispielsweise Hoffmann (²⁰¹³ )² sowie Petzold (2008)³, versuchen dieser Problemlage entgegenzutreten, scheint die Diskrepanz zwischen der Metamathematik (Beweistheorie) und der Philosophie immer größer zu wer- den. In diesem Sinne bemerkt Thiel (1992), dass die ”Wirkung[derUnvollständigkeitssätzeaufdie Philosophie] - wie es scheint - noch längst nicht ihren Höhepunkt erreicht hat, [...Dies liegt] vor allem daran [...], daß es auch in der Metamathematik keinen Königsweg gibt und ohne gründliche Einarbei- tung in die Thematik und die dazu nötige Aneignung mathematischer Techniken eine Rezeption der Gödelschen Resultate kaum möglich ist. So hat ihre Diskussion durch Denker wie Max Bense, Micha- el Dummett, Paul Lorenzen, Heinrich Scholz (der Gödels Unvollständigkeitssätzen sogar den ’Rang einer zweiten nachkantischen Vernunftkritik’ zuerkennen wollte) und Ludwig Wittgenstein allgemein großes Interesse geweckt. Gleichzeitig herrscht jedoch eine gewisse Unsicherheit durch Mystifikation und oft windige Spekulationen in einem Teil der populären ’Gödel-Literatur’ und macht skeptisch auch gegenüber Hinweisen auf erkenntnistheoretische Konsequenzen der mit Gödel 1931 beginnenden Forschungen [...].“⁴ Eine der zentralen Aufgaben der Philosophie der Mathematik muss es daher sein (neben ihrem inhaltlichen Fragestellungen) einen Brückenschlag zwischen diesen Welten herzustellen. In gewisser Hinsicht widmet sich auch die vorliegende Arbeit dieser Zielsetzung. Zum einen soll dem jeweiligen Beweisgang Rechnung getragen werden indem formal exakt und vollständig der Beweis der Theoreme erbracht wird, zum anderen soll jedoch zugleich eine historische, theoretische und philoso- phische Verortung der Resultate stattfinden. Nur beide Aspekte zusammen können ein tiefgründigeres Verständnis der Resultate gewährleisten. Nicht zuletzt deshalb, weil Antworten für den Empfänger keinen Nutzen haben bevor er sich die entsprechenden Fragen gestellt hat, ist auch diese ideenge- schichtliche Verortung der Theoreme essentiell.

Die formale Wiedergabe der Beweise mündet jedoch nicht in einem Selbstzweck. Wir werden im Laufe der formalen Ausarbeitung der Beweisgänge nicht nur eine Grundlage für ein besseres Verständnis der philosophischen Implikationen ermöglichen, sondern zugleich auch einige Annahmen der Wissenschaftsgeschichte überprüfen. Die Beweise, die behandelt werden sollen, wurden zudem seitens der Autoren (allen voran Gödel und Rosser) nicht vollständig veröffentlicht. Eine vollständige Erarbeitung der Beweise geht somit über die Orginalarbeiten hinaus.

Bei einem derartigen Vorhaben stellt sich jedoch unweigerlich die Frage nach dem Umfang der zu be- handelnden Materie. Welche Resultate werden behandelt, welche nur am Rande erwähnt und welche gar ausgelassen? Das Kriterium einer derartigen Selektion kann nur methodologischer Natur sein und es ist offenkundig so, dass diese Arbeit neben den explizit formulierten Forschungsfragen ein generelles Interesse an einem bestimmten Phänomen, nämlich der Hyperzirkularität, an den Tag legt. Die Hy- perzirkularität, eine Begrifflichkeit die in der Metamathematik keine weite Verbreitung finden konnte, jedoch meines Erachtens das Phänomen einer strikten Selbstbezüglichkeit adäquat wiedergibt, steht für den Umstand, dass in einem genügend starken ⁵ formalen System Sätze konstruiert werden können, die die Eigenschaft einer gänzlichen Selbstreflexivität aufweisen. Wir werden auf dieses Phänomen noch zur genüge zu sprechen kommen. Es begleitet jedoch die Arbeit auch dort, wo es nicht explizit erwähnt wird. Alle behandelten Themen der Arbeit sind daher nur notwendige Präliminarien einer bis dato ungeklärten Fragestellung der Metamathematik, nämlich der Frage, ob folgende Äquivalenz postuliert werden kann: Hyperzirkularität ⇔ Unvollständigkeit Sind alle formalen Systeme, in denen Hyperzirkularität formuliert werden kann, zugleich auch (zumindest) negationsunvollständig? Kann die schen Ausdrückbarkeit als Synonym für die ”Stärke“einesSystemshinsichtlichderarithmeti- ”Stärke“hinsichtlichderHyperzirkularitätaufgefasst werden? Und, noch prekärer, ist die Hyperzirkularität eine conditio sine qua non für ein (negations)unvollständiges formales System?

Diese Fragen können in dieser Arbeit nicht zur Gänze geklärt werden. Wir werden jedoch im Kapitel zu Kripkes Beweis des ersten Unvollständigkeitssatzes (wiedergegeben durch Putnam (2000)⁶ ) zumin- dest einen ersten Schritt dahingehend tätigen, die Frage zu Klären, ob der Beweisgang von Kripke (von dem behauptet wird, er entbehre jeglicher selbstbezüglicher Konstruktionen) keinen Gebrauch der Hyperzirkularität macht oder, ob diese implizit dennoch angenommen wird.⁷ Obwohl diese Fragestellungen der Metamathematik, wie gesagt, nicht zur genüge geklärt werden können, werden an Stelle der Antworten die bisherigen Resultate der Metamathematik treten. Ausge- hend von einigen grundlegenden Voraussetzungen, wie dem Hauptsatz der elementaren Zahlentheorie, werden wir uns zunächst dem Cantorschen Theorem über überabzählbare Mengen annähern. Anhand von zwei Beweisen der Überabzählbarkeit der reellen Zahlen werden wir uns zum ersten Mal mit der Grundstruktur des Diagonalargumentes vertraut machen. Basierend auf den Überlegungen von Can- tor werden wir uns mit jenen logischen Paradoxien (Cantor-Russell Antinomie sowie die Antinomie von Richard) vertraut machen, die für die Entwicklung der Metamathematik grundlegend waren. Die Antinomie von Richard hat so beispielsweise den Vorteil, als eine Brücke zum ersten Gödelschen Theo- rem zu fungieren. Bei diesem Brückenschlag werden wir uns allem voran der Arbeiten von Mostowski (1952)⁸ und Stegmüller (1970)⁹ bedienen.

Der eigentliche Hauptteil des metamathematischen Abschnittes der Arbeit besteht in der kommen- tierten Wiedergabe des Beweisganges der Unvollständigkeitssätze. Wir werden dabei in Abhängigkeit von der Stärke des Resultates drei Varianten des (ersten) Unvollständigkeitssatzes unterscheiden:

1. Die semantische Variante: Die semantische Variante des ersten Unvollständigkeitssatzes ist der vergleichsweise einfachste und schwächste Satz den wir behandeln werden. Er zeigt, dass ein korrektes¹⁰ axiomatisches System der Peano-Arithmetik unvollständig ist. Gödel selbst widmet dieser semantischen Variante den ersten Teil seiner 1931 erschienen Arbeit. Wir werden uns bei den Darstellungen jedoch auf Smullyan (1992)¹¹ beziehen und Gödels Ausführungen nur am Rande behandeln. Obwohl zwischen diesen kein wesentlicher Unterschied herrscht, haben die Ausführungen von Smullyan (1992) zwei Vorteile: (1) sie heben die zugrunde liegenden Annahmen des Beweisganges explizit hervor. Somit kann ein besserer Abgleich zwischen der semantischen und der syntaktischen Variante des Satzes gewährleistet werden und (2) sie stellen das Diagonallemma explizit dar. Wir werden sehen, dass in Gödels Arbeit das Diagonallemma nicht explizit erwähnt wird (weder in seiner semantischen noch in seiner syntaktischen Variante). Zwar ist der Grundgedanke im Beweisgang vorzufinden, dessen Verallgemeinerung jedoch nicht. Heute wird der Beitrag zu dieser Verallgemeinerung sowie einer expliziten Formulierung des Diagonallemmas Carnap (1934)¹² zugeschrieben. Wir werden in einem eigenen Abschnitt sehen, dass dies nur bedingt richtig ist. Carnap formulierte zwar explizit als erster das Diagonallemma, jedoch nur in seiner semantischen Form. Die heute übliche syntaktische Darstellung ist in der Logischen Syntax der Sprache ¹³ nicht vorzufinden.

2. Die schwache syntaktische Variante: Im Hauptteil seiner Arbeit stellt Gödel (1931) ei- ne schwache syntaktische Variante des ersten Unvollständigkeitssatzes vor. Wir werden unter geringfügiger Anpassung der Notation Gödels Beweisgang in seiner vollen Länge wiedergeben. Dabei werden jene Beweisgänge, die Gödel nur skizzenhaft und ansatzweise getätigt hat, expli- zit und in voller Länge dargestellt. Entsprechend unserem Anliegen, die formalen Aspekte der Arbeit ideengeschichtlich zu verorten, werden die jeweiligen Abschnitte entsprechend kommen- tiert.¹⁴ In diesem Kontext sprechen wir von der schwachen syntaktischen Variante, da Gödel von der Annahme der ω -Konsistenz ausgeht. Im Anschluss an den ersten Unvollständigkeitssatz gehen wir kurz auf das erste seiner Resultate ein: den zweiten Unvollständigkeitssatz.

3. Die starke syntaktische Variante: Die Annahme der ω -Konsistenz wurde erstmals von Ros- ser (1936)¹⁵ durch die schwächere Annahme der simplen Konsistenz ersetzt. Deshalb sprechen wir hier von der starken Variante des ersten Unvollständigkeitssatzes. Rossers Arbeit orientiert sich stark an Gödel (1931). Große Teile des Beweisganges werden von Rosser übernommen. Er zeigt dadurch, dass lediglich geringfügige Änderungennotwendig sind um eine stärkere Variante des ersten Unvollständigkeitssatzes zu generieren (sogenannter Rosser-Trick). Dennoch bleiben die Ausführungen von Rosser skizzenhaft und unvollständig. Das Anliegen des Kapitels zur starken Variante des ersten Unvollständigkeitssatzes liegt somit auch darin, die zentrale Idee von Rosser vollständig (unter Beibehaltung der Notation und der Vorgehensweise) darzulegen. Nachdem die Unvollständigkeitssätze dargelegt wurden, soll zusätzlich eine alternative Art des Be- weisganges dargestellt werden. Diese geht auf Saul Kripke zurück, wurde jedoch erstmals von Hilary Putnam im Jahre 2000 publiziert.¹⁶ Von diesem Beweisgang wird behauptet, dass er ohne die An- wendung jeglicher Abwandlungen des Diagonallemmas auskommt. Dieser Behauptung soll in Kapitel 6 nachgegangen werden.

Das Kapitel 7 widmet sich einigen metamathematischen und philosophischen Fehlimplikationen aus den bis dahin dargestellten Resultaten. Die Relevanz der Unvollständigkeitssätze für die mathemati- sche Praxis soll am Beispiel der Goodstein-Folgen dargelegt werden. Der Beweis, dass die Goodstein- Folgen stets (nach einer endlichen Anzahl von Gliedern) mit null enden, kann nicht in der Arithmetik selbst erbracht werden. Das natürliche Phänomen der Unabhängigkeit der Goodstein-Folgen wird in Kapitel 8 behandelt.

Zu guter letzt wird, um die erwähnte Brücke zwischen der Metamathematik und der Philosophie zu schlagen, lediglich ein Strang philosophischer Diskussion ausgewählt, der die Unvollständigkeitssätze als Ausgangspunkt nimmt: Die Mechanismusdebatte. Die Mechanismusdebatte erfolgte seit dem Jahr 1961 im Wesentlichen in zwei Richtungen: Die Diskussionen um den Aufsatz von Lucas (1961)¹⁷ sowie die Diskussionen um die Werke von Roger Penrose¹⁸. Wir werden im Lichte der bewiesenen Sätze ver- suchen, die Argumente der einzelnen Parteien abzuwiegen sowie den derzeitigen Stand der Diskussion abzubilden. Dabei werden wir uns nur auf den Strang der Lucas-Debatte beziehen.

Zusammenfassend kann gesagt werden, dass die zentralen Anliegen bzw. Forschungsfragen dieser Arbeit die folgenden sind:

- Eine vollständige Darstellung der Ergebnisse von Kurt Gödel und Barkley Rosser im Zusammen- hang mit den Unvollständigkeitssätzen unter Beachtung ihrer ideengeschichtlichen Verortung, der spezifischen Beweisgänge der Originalarbeiten und unter möglichst geringfügigen Anpas- sungen der Notation;
- Klärung der wissenschaftsgeschichtlichen Frage, ob Rudolf Carnap und in welcher Form als erster das Diagonallemma aufgestellt hat;
- Klärung der Frage, ob modelltheoretische Beweise (wie der Beweis von Kripke/Putnam) ohne Rekurs auf das Diagonallemma und die Kodierung auskommen;
- Brückenschlag zwischen den Resultaten der Beweistheorie und der Berechenbarkeitstheorie über die Arbeit von Alan Turing;
- Erarbeitung der Argumente von John Lucas im Rahmen der Antimechanismusdebatte sowie der zentralen Gegenargumente;
- Einführung des Begriffes der Hyperzirkularität.

Kapitel 2 Historischer und ideengeschichtlicher Kontext

” Z udereigentlichensoformalisiertenMathematikkommteine gewissermaßen neue Mathematik, eine Metamathematik, die zur Sicherung jener notwendig ist, in der - im Gegensatz zu den rein formalen Schlußweisen der eigentlichen Mathematik - das inhaltliche Schließen zur Anwendung kommt, aber lediglich zum Nachweis der Widerspruchsfreiheit der Axiome. In dieser Metamathematik wird mit den Beweisen der eigentlichen Mathematik operiert und diese letzteren bilden selbst den Gegenstand der inhaltlichen Untersuchungen. “

Hilbert, D.: Die logischen Grundlagen der Mathematik. J. Springer, 1922

Die Idee einer Axiomatisierung gewisser Bereiche der Mathematik kann bis in die Antike zurückverfolgt werden. Im dritten Jahrhundert vor unserer Zeitrechnung formulierte Euklid als erster eine Menge von Axiomen, die die Basis für die (euklidische) Geometrie darstellen sollten.¹ Die von ihm formulierten Axiome sollten jahrhundertelang die unangefochtene Basis der Geometrie bilden. Seitdem war ein deduktivistisch-axiomatischer Aufbau einer Theorie der Inbegriff der Exaktheit und Wohlfundiertheit eines jeden epistemologischen Systems.

Die rasante Entwicklung der Mathematik im 19. und 20. Jahrhundert parallel mit dem Auftreten im- manenter Paradoxien in Disziplinen, wie der naiven Mengenlehre, veranlassten Philosophen, Mathe- matiker und Logiker der Frage der Konsistenz eben dieser Disziplinen nachzugehen. Dies resultierte in der Entwicklung verschiedenster Programme hinsichtlich der Grundlagenlegung der Mathematik von denen der Logizismus von Frege und Russell sowie der Formalismus von Hilbert die namenhaftesten waren.

Hinsichtlich dieser Bemühungen wurde sowohl der Logizismus als auch das Hilbertprogramm als Emanation der Euklidischen Idee alsbald auf eine Probe gestellt, die sie nicht bestehen würden. Im Jahre 1930 bewies Kurt Gödel mit gerade einmal 23 Jahren ein mathematisches Theorem, dass weit- reichende Folgen auch außerhalb der Mathematik haben sollte.² Ein Jahr darauf wurde sein Beweis im Monatshefte für Mathematik und Physik unter dem Namen ” Ü ber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I “ publiziert. Der Analyse der Resultate dieses Aufsatzes, seiner Erweiterungen sowie einiger seiner metamathematischer und philosophischer Implikationen ist diese Arbeit gewidmet.

Der Titel von Gödels Aufsatz mag heute befremdlich anmuten, steht jedoch im engen Zusammen- hang mit der damaligen Grundlagenkrise der Mathematik sowie dem logizistischen Lösungsansatz von Bertrand Russell und Alfred Whitehead, der Principia Mathematica³. Die Principia Mathematica ist ein dreibändiges Werk über die Grundlagen der Mathematik, erstmals erschienen zwischen 1910 und 1913, dessen Motivation darin bestand alle mathematischen Wahrheiten aus einem wohldefinierten Satz von Axiomen und Schlussregeln (Inferenzregeln der symbolischen Logik) herzuleiten. In diesem Sinne war die Principia Mathematica in weiten Teilen konform mit dem Hilbertprogramm, dem zwei- ten großen Programm der Grundlagenmathematik. Um die Reichweite der Gödelschen Theoreme⁴ verstehen zu können, ist eine Auseinandersetzung mit den zentralen philosophischen Standpunkten und Projekten der damaligen Zeit unabdingbar.⁵

Der erwähnte Logizismus ist vielleicht die wichtigste und (neben dem Formalismus) produktivste Strömung innerhalb der Philosophie der Mathematik. Ihren Auftakt feiert diese Strömung mit der Schrift von Gottlob Frege aus dem Jahre 1879 mit dem Titel ” B egriffschrift.Einederarithmetischen nachgebildeten Formelsprache “.⁶ Mit der Publikation dieser Schrift rief Frege den Logizismus ins Leben: eine philosophische Strömung, die in ihrem Zentrum die Auffassung teilte, dass die Logik nicht nur ein Teilgebiet der Mathematik, sondern umgekehrt, die Mathematik ein Teilgebiet der Logik sei. Als solche könne die gesamte Mathematik innerhalb der Logik entwickelt werden. Dies hatte den Vorteil, dass mathematische Begrifflichkeiten exakt definiert werden könnten, indem sie auf feste logische Prinzipien zurückführbar wären.⁷ Da dieses Projekt nicht in der natürlichen Sprache, der es an Exaktheit mangelte, verwirklicht werden konnte, schuf Frege in der Begriffsschrift eine künstliche Sprache. Er bemerkt in diesem Zusammenhang folgendes:⁸

Universität Wien Physik und Mathematik bei Hans Hahn und reichte schon im Jahr 1929 seine Dissertation mit dem Titel ” Ü ber die Vollständigkeit des Logikkalküls “ ein.Gödel, K.:

Über die Vollständigkeit des Logik- kalküls (1929). In Collected Works, Volume I, Publications 1929-1936. Feferman Solomon, 1986 Das Resultat dieser Arbeit, nämlich der Beweis der Vollständigkeit des Prädikatenkalküls erster Stufe, war ein erster Erfolg im Rahmen des Hilbertprogramms. Mit seiner zweiten wichtigen Arbeit sollte er jedoch diesen Optimismus relativieren. Zwei Jahre später habilitierte er (gerade einmal mit 24 Jahren) mit der Arbeit ” Ü ber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I “. Im Zeitraum zwischen 1933 bis 1938 lehrte er als Privatdozent an der Universität Wien. Seine Ausreise in die Vereinigten Staaten applizierte Gödel zusammen mit seiner Frau Adele Nimbursky, bald nach der Annexion Österreichs durch das ”Groß- deutsche Reich“ sowie den darauffolgenden Ausbruch des zweiten Weltkrieges. Im selben Jahr wurde Gödel ordentliches Mitglied des Institute for Advanced Study in Princeton. Die amerikanische Staatsbürgerschaft erlangte Gödel im Jahre¹⁹⁴⁸. Im Jahre¹⁹⁵¹ erhielt er den Einstein-Preis und war ab¹⁹⁵⁷ Mitglied der amerikanischen Akademie der Wissenschaften. Gödel starb am¹⁴. Januar¹⁹⁷⁹ bedingt durch seine gesundheitliche Anfälligkeit sowie durch seine psychischen Erkrankungen.

Gödels Gesamtwerk reicht von zentralen Sätzen der Metamathematik bis hin zu phänomenologischen Erörterungen. Dennoch war sein direkter Einfluss auf die Philosophie eher gering. Bekannt ist, dass er sich seit dem Jahr¹⁹⁴³ vermehrt philosophischen Fragen gewidmet hat. Für weiterführende biographische Angaben siehe beispielsweise Goldstein, R.: Incompleteness: The Proof and Paradox of Kurt Gödel (Great Discoveries). W. W. Norton, 2006 . Für Gödels philosophische Auffassungen siehe beispielsweise Wang, H.: A Logical Journey: From Gödel to Philosophy. MIT Press

” [ es]mussteallesaufdieLückenlosigkeitderSchlussketteankommen.Indemichdie- se Forderung auf das strengste zu erfüllen trachtete, fand ich ein Hindernis in der Un- zulänglichkeit der Sprache, die bei aller entstehenden Schwerfälligkeit des Ausdrucks doch, je verwirklichter die Beziehungen wurden, desto weniger die Genauigkeit erreichen ließ, welche mein Zweck verlangte. Aus diesem Bedürfnisse ging der Gedanke der vorliegenden Begriffsschrift hervor. “ Mit der Begriffsschrift war Frege überzeugt einen formalen Rahmen geschaffen zu haben in dem er sein logizistisches Programm verwirklichen konnte. Basierend auf der Begriffsschrift publizierte er anschließend im Jahre 1884 die ” G rundlagenderArithmetik “.⁹ IndiesemWerkwollteernunentgültig die Arithmetik innerhalb der Logik begründen. Ein derartiges Vorhaben hatte jedoch eine exakte De- finition des Zahlenbegriffes als Voraussetzung. Um dies zu bewerkstelligen wählte Frege einen auf den ersten Blick unproblematischen mengentheoretischen Ansatz. Er griff dabei auf die Arbeiten von Georg Cantor (¹⁸⁹² )¹⁰ zurück. Cantors Arbeit bot die Möglichkeit Mengen über ihre Mächtigkeit zu verglei- chen. Für Frege war nun n eine Zahl, wenn eine Menge A existiert, so dass n die Mächtigkeit von A darstellt. Man kann daher die Definition des Zahlenbegriffes bei Frege folgendermaßen wiedergeben:¹¹

(i) Die Mächtigkeit einer Menge X ist die Gesamtheit aller Mengen, die gleichmächtig zu X sind.
(ii) n ist eine Zahl, wenn eine Menge X existiert, so dass n die Mächtigkeit von X ist. (iii) 0 ist die Mächtigkeit der leeren Menge.
(iv) 1 ist die Mächtigkeit der Menge, die nur aus 0 besteht.
(v) Die Zahl n ist der Nachfolger der Zahl m, wenn es eine Menge X und ein Element a von X gibt, so dass n die Mächtigkeit von X ist und m die Mächtigkeit der Menge X ohne das Element a (also von X \ {a}).
(vi) n ist eine endliche (natürliche Zahl), wenn n ein Element aller Mengen Y ist, für die gilt: 0 ist Element von Y und ist k Element von Y , dann auch der Nachfolger von k.

“

Frege konnte zum damaligen Zeitpunkt die Problematik, die sich aufgrund der Definition des Zahlenbegriffes über die naive Mengenlehre ergeben würde, nicht abschätzen. Fünf Jahre nach der Publikation der Grundlagen publizierte Frege die Grundgesetze der Arithmetik,¹² in denen er weitreichende Formalisierungen der Arithmetik basierend auf dem Konzept seiner Begriffsschrift, durchführte. Der zweite Band der Grundgesetze wurde daraufhin im Jahre 1903 publiziert.

Freges Anstrengungen wurden jedoch schon im Jahre 1902, d. h. vor der Publikation des zweiten Bandes der Grundgesetze, zunichte gemacht. In einem Brief vom 16. Juni 1902 bemerkte Bertrand Russell, einer der wenigen damaligen Mathematiker, die sich ernsthaft mit der Arbeit Freges aus- einandergesetzt hatten, dass im Aufbau der Grundgesetze bei Frege ein Einfallstor für Paradoxien existierte. Der Grundgesetz V bei Frege ermöglichte die Konstruktion von Mengen, die zu einem Wi- derspruch führten, der mit den bisherigen Mitteln nicht aufzulösen war. Russell bemerkt in seinem Brief folgendes:¹³

” [ ...]NurineinemPunktbinicheinerSchwierigkeitbegegnet.Siebehaupteneskönne auch die Funktion das unbestimmte Element bilden. Dies habe ich früher geglaubt, jedoch jetzt scheint mir diese Ansicht zweifelhaft, wegen des folgenden Widerspruchs: Sei w das Prädikat, ein Prädikat zu sein, welches von sich selbst nicht prädizirt werden kann. Kann man w von sich selbst prädizieren? Aus jeder Antwort folgt das Gegenteil. Deshalb muss man schließen, dass w kein Prädikat ist. Ebenso gibt es keine Klasse (als Ganzes) derjenigen Klassen, die als Ganze sich selbser nicht angehören. Daruas schließe ich, dass unter gewissen Umständen eine definierbare Menge kein Ganzes bildet. “

Wir wollen kurz auf die Bemerkung von Russell eingehen. Im Wesentlichen gibt diese den Grund- gedanken der Russellschen Antinomie wieder. Gemäß Definition gilt für das Prädikat P folgendes:¹⁴

Abbildung in dieser Leseprobe nicht enthalten

Das Prädikatenprädikat w trifft daher auf jene Prädikate P zu, die sich selbst nicht prädizieren. Nun stellt sich die Frage was mit w selbst ist. Prädiziert sich w selbst? Aus der obigen Definition folgt:

Abbildung in dieser Leseprobe nicht enthalten

Aus dem obigen resultiert unmittelbar folgende Äquivalenz:

Abbildung in dieser Leseprobe nicht enthalten

Falls daher das Prädikatenprädikat w auf sich selbst zutrifft, trifft es zugleich nicht auf sich selbst zu. Dies stellt eine logische Formulierung der Russellschen Antinomie dar. Die mengentheoretische Formulierung würde analog erfolgen und bildet die Brücke zum Grundsatz V bei Frege. Frege bemerkte als Antwort darauf folgendes:¹⁵

” I hreEntdeckungdesWiderspruchshatmichauf ’ sHöchsteüberraschtund,fastmöchte ich sagen, bestürtzt, weil dadurch der Grund, auf dem ich die Arithmetik sich aufzubauen dachte, in ’ s Wanken gerät. Es scheint danach, dass die Umwandlung der Allgemeinheit einer Gleichheit in eine Wertverlaufsgleichheit ( § ⁹ meiner Grundgesetze) nicht immer erlaubt ist, dass mein Gesetz V ( § ²⁰. S.³⁶ ) falsch ist und dass meine Ausführungen im § ³¹ nicht genügen [...] “

Wir wollen an dieser Stelle nicht näher auf das erwähnte Grundgesetz bei Frege eingehen, da es für den Fortgang unserer Arbeit keine direkte Relevanz hat. Frege selbst gab aufgrund dieser Umstände seine Auffassung auf, dass die Arithmetik ein Zweig der Logik sei und dass demnach in der Arithmetik alles rein logisch bewiesen werden könnte.

Während jedoch Frege keine Perspektive mehr für das logizistische Programm sah, erfuhr Russell selbst im Jahre 1906 einen scheinbaren Durchbruch. Dieser war jedoch von jahrelangen Bemühungen um die Auflösungen der sich ergebenen Widersprüche begleitet. So schreibt Russell in seiner Autobio- graphie folgendes:¹⁶

” A ttheendoftheLentTerm,AlysandIwentbacktoFemhurst,whereIsettowork to write out the logical deduction of mathematics which afterwards became Principia Ma- thematica. I thought the work was nearly finished, but in the month of May I had an intellectual set-back almost as severe as the emotional set-back which I had had in Fe- bruary. Cantor had a proof that there is no greatest number, and it seemed to me that the number of all the things in the world ought to be the greatest possible. Accordingly, I examined his proof with some minuteness, and endeavoured to apply it to the class of all the things there are. This led me to consider those classes which are not members of themselves, and to ask whether the class of such classes is or is not a member of itself. I found that either answer implies its contradictory. At first I supposed that I should be able to overcome the contradiction quite easily, and that probably there was some trivial error in the reasoning. Gradually, however, it became clear that this was not the case. Burali-Forti had already discovered a similar contradiction, and it turned out on logical analysis that there was an affinity with the ancient Greek contradiction about Epimenides the Cretan, who said that all Cretans are liars. A contradiction essentially similar to that of Epimenides can be created by giving a person a piece of paper on which is written: ’ The statement on the other side of this paper is false. ’ The person turns the paper over, and finds on the other side: ’ The statement on the other side of this paper is true. ’ It seemed unworthy of a grown man to spend his time on such trivialities, but what was I to do? There was something wrong, since such contradictions were unavoidable on ordinary premises. Trivial or not, the matter was a challenge. Throughout the latter half of 1901 I supposed the solution would be easy, but by the end of that time I had concluded that it was a big job. I therefore decided to finish The Principles of Mathematics, leaving the solution in abeyance. In the autumn Alys and I went back to Cambridge, as I had been invited to give two terms ’ lectures on mathematical logic. These lectures contained the outline of Principia Mathematica, but without any method of dealing with the contradictions.[...] I was trying hard to solve the contradictions mentioned above. Every morning I woulf sit down before a blank sheet of paper. Throughout the day, with a brief interval for lunch, I would stare at the blank sheet. Often when evening came it was still empty. [...] the two summers of 1903 and 1904 remain in my mind as a period of complete intelectual deadlock. It was clear to me that I could not get on without solving the contradictions, and I was determined that no difficulty should turn me aside from the completion of Prin- cipia Mathematica, but it seemed quite likely that the whole of the rest of my life might be consumed in looking at the blank sheet of paper. “

Der Durchbruch gelang Russell im Jahr 1906 mit seiner Typentheorie. Er publizierte diese im Jahre 1908 im American Journal of Mathematics unter dem Titel ” M athematicalLogicasBased on the Theory of Types “. Er bemerkte in dieser Arbeit die analoge Struktur aller auftretenden Paradoxien hinsichtlich ihrer Selbstreferenz:¹⁷

” I nalltheabovecontradictions(whicharemerelyselectionsfromanindefinitenumber) there is a common characteristic, which we may describe as self.reference of reflexivness.

[...] In each contradiction something is said about all cases of some kind, and from what is said a new case seems to be generated, which both is an is not of same kind as the cases of which all were concerned is what was said. “

Mit der Definition von Typen von Elementen der Objektsprache konnte Russell diese Selbst- bezüglichkeit scheinbar umgehen. Er formulierte im Grunde zwei hierarchische Ordnungen, die mit- einander verzweigt waren und somit ein verzweigtes Typensystem bildeten. Dieser Umstand wurde später von Frank Plumpton Ramsey wesentlich vereinfacht als er zeigte, dass die zweite Hierarchie le- diglich zur Vermeidung semantischer Paradoxien notwendig sei, die aus einer Vermengung von Objekt- und Metasprache resultierte. Eine adäquate Trennung dieser beiden macht diese Typisierung obso- let. Dies ist auch ein Grund wieso Gödel, wie wir später sehen werden, in seiner Arbeit nicht das verzweigte Typensystem von Russell, sondern ein primitives und leicht nachvollziehbares Typensys- tem heranzieht.¹⁸ Gödel wird zudem zeigen, dass auch unter den Annahmen eines Typensystems die Vollständigkeit und Widerspruchsfreiheit der Principia Mathematica zugleich nicht gewährleistet werden kann.

2.1 Arithmetische und mengentheoretische Preliminarien

Nachdem wir nun einen kurzen Einblick in die historische Entwicklung der Problemlage erfahren haben, wollen wir einige technische Preliminarien näher erläutern, auf die in späteren Teilen der Arbeit rekurriert wird. Das Diagonalverfahren, zum ersten Mal gebraucht von Georg Cantor, steht im engen Zusammenhang mit dem später zu behandelnden Diagonallemma bzw Fixpunkttheorem. Wir werden sehen, dass die Struktur des Diagonalverfahrens bei Cantor im Grunde den Kern des Originalbeweises des Gödelschen Unvollständigkeitssatzes vorwegnimmt.

Definition 2.1.1 (Abzählbare Mengen)

Abbildung in dieser Leseprobe nicht enthalten

Wir wollen im Folgenden gleich mehrere wichtige Sätze der Zahlentheorie und der Mengenlehre einführen, die in der späteren Ausführung eine wichtige Rolle spielen werden. Um den Begriff der Abzählbarkeit von Mengen näher zu erläutern, betrachten wir nun die Menge aller Primzahlen. Die erste Frage, die sich an dieser Stelle stellt, ist, ob diese Menge unendlich oder endlich ist. Der Be- weis der Unendlichkeit der Menge der Primzahlen wurde schon im dritten Jahrhundert vor unserer Zeitrechnung von Euklid vorgelegt. Doch die Beantwortung dieser Frage gibt noch keine Auskunft darüber, ob die Menge abzählbar oder überabzählbar ist. Eine surjektive Funktion mit der Domäne in der Menge der natürlichen Zahlen und der Kodomene in der betrachteten Funktion setzt nicht voraus, dass die betrachtete Funktion unendlich viele Elemente besitzen muss (da keine Injektivität vorausgesetzt wird). Der Beweis, dass die Menge der Primzahlen abzählbar unendlich ist muss daher aus zwei separaten Bestandteilen bestehen: dem Beweis, dass die Menge unendlich viele Elemente besitzt sowie dass sie abzählbar ist. Bevor wir jedoch den eigentlichen Beweis anstellen benötigen wir noch zwei weitere Hilfssätze.¹⁹

Satz 2.1.1 (Fundamentalsatz der elementaren Zahlentheorie)

Abbildung in dieser Leseprobe nicht enthalten

Dabei sind die Primzahlen p α und ihre Exponenten e α , mithin alle Faktoren p e α α b isaufihre Reihenfolge eindeutig bestimmt.

Beweis : Wir nehmen für eine gegebene natürliche Zahl n an, dass zwei verschiedene Primfak- torzerlegungen möglich sind. Demnach gilt [Abbildung in dieser Leseprobe nicht enthalten] sowie [Abbildung in dieser Leseprobe nicht enthalten]²⁰ Wir nehmen weiters an, dass n die kleinste natürliche Zahl ist, die mehr als eine Primzahlzerlegung aufweist. Ohne Beschränkung der Allgemeinheit können wir nun annehmen, dass [Abbildung in dieser Leseprobe nicht enthalten]In diesem Falle können wir die positive Zahl m angeben mit

Abbildung in dieser Leseprobe nicht enthalten

Gemäß der Konstruktion von m, gilt m < n. Wir können den obigen Ausdruck für m jedoch auch folgendermaßen umformen:

Abbildung in dieser Leseprobe nicht enthalten

Betrachten wir die zwei Ausdrücke in (2 . 6) und (2 . 9). Da q f 11 aus (2 . 9) sowie [Abbildung in dieser Leseprobe nicht enthalten] keine gemeinsamen Faktoren besitzen, muss der Ausdruck ([Abbildung in dieser Leseprobe nicht enthalten]¹ 1 bzw.

Abbildung in dieser Leseprobe nicht enthalten

mit w ∈ N. Dies bedeutet jedoch, dass q f ¹ keine Potenz der Primzahl p 1 ist. Dies steht jedoch mit der anfängliche Annahme im Widerspruch. Daher existiert für die Zahl n nur eine Primfaktorzerlegung.

Satz 2.1.2 (die Unendlichkeit der Primzahlen) Die Menge der Primzahlen ist abzählbar unendlich.

Abbildung in dieser Leseprobe nicht enthalten

Beweis : Nehmen wir an, die Menge der Primzahlen (nennen wir sie P ∇) sei endlich. Aufgrund dessen, dass P ∇ ⊂ N und die Menge der natürlichen Zahlen N wohlgeordnet ist, gilt Folgendes:

Abbildung in dieser Leseprobe nicht enthalten

Die Primzahl p i ist somit die größte Zahl in der Menge der Primzahlen. Wir werden nun eine Zahl konstruieren, die ebenfalls eine Primzahl ist, jedoch größer sein wird als p i. Da dies unserer Anfangsannahme widerspricht, schließen wir daraus auf die Unendlichkeit der Primzahlenmenge. Bei der genannten Zahl handelt es sich um

Abbildung in dieser Leseprobe nicht enthalten

Da diese Zahl größer als 1 ist und mit keiner der Primzahlen der Menge P ∇ restlos teilbar ist, ist sie ebenfalls eine Primzahl und es gilt [Abbildung in dieser Leseprobe nicht enthalten]obwohl[Abbildung in dieser Leseprobe nicht enthalten]. Für den Beweis der Abzählbarkeit der Primzahlenmenge genügt es eine surjektive Funktion mit f[Abbildung in dieser Leseprobe nicht enthalten]zu konstruieren. Dies wäre Beispielsweise die Funktion [Abbildung in dieser Leseprobe nicht enthalten]eine Primzahl ist.

Wie wir gesehen haben, kann eine surjektive Funktion, die über die Abzählbarkeit eine Menge Auskunft gibt, oftmals mit Leichtigkeit angegeben werden.²¹ Allgemein können wir festhalten, dass jede endliche Menge abzählbar ist. Obwohl wir weiter oben eine Menge kennengelernt haben, die unendlich und abzählbar ist, kann dies nicht für alle unendlichen Mengen gleichermaßen behauptet werden. Diese Erkenntnis gibt das Cantorsche Theorem wieder, dass eine Menge konstruiert die überabzählbar ist.

Definition 2.1.2 (Potenzmenge)

Sei M eine Menge. Die Potenzmenge P M von M ist definiert als die Menge aller Teilmengen von M .

Wir wollen nun die Eigenschaften der Potenzmenge hinsichtlich ihrer Abzählbarkeit untersuchen. Die Anzahl der Elemente einer Menge M wird noch als Mächtigkeit (oder Kardinalität) der Menge bezeichnet und als |M| dargestellt. Zwei Mengen sind demnach gleichmächtig, wenn eine bijektive Abbildung zwischen ihnen existiert.

Wir wollen in diesem Sinne die Mächtigkeit der Potenzmenge P M im Vergleich zur Menge M unter- suchen.²²

Satz 2.1.3 Die Mächtigkeit der Potenzmenge P M beträgt für eine endliche Menge M

Abbildung in dieser Leseprobe nicht enthalten

Beweis : Der obige Satz resultiert aus einer einfachen Variation mit Wiederholung.²³ Nehmen wir eine beliebige Menge K ⊂ P M. Jedes Element der Menge M kann nun Element der Menge K sein oder auch nicht. Für jedes Element gibt es daher zwei Möglichkeiten. Da die Menge M per Definition |M| Elemente besitzt gibt es insgesamt

Abbildung in dieser Leseprobe nicht enthalten

Teilmengen von M. Dass die Mächtigkeit der Potenzmenge zudem höher ist als die Mächtigkeit der entsprechenden Menge resultiert direkt aus der Bernoulli Ungleichung

Abbildung in dieser Leseprobe nicht enthalten

Falls die Menge M jedoch unendlich ist, ist eine derartige Ableitung der Mächtigkeit für die Po- tenzmenge nicht ohne weiteres möglich. Wir müssen uns in diesem Fall anderer Verfahren bedienen. Smith (2013), auf den wir an dieser Stelle rekurrieren, unterscheidet zwei verschiedene Vorgehens- weisen beim Beweis der Überabzählbarkeit der Potenzmenge der Menge der natürlichen Zahlen. Wir werden an dieser Stelle beide Beweise darstellen, da der eine den Vorteil hat das Diagonalverfahren (und damit teilweise auch das spätere Diagonallemma) auf eine grafisch intuitive Weise darzustellen und der andere einige mengentheoretische Manipulationen der semantischen Beweisskizze des ersten Unvollständigkeitssatzes vorwegnimmt.²⁴

Satz 2.1.4

Die Potenzmenge P N der Menge der natürlichen Zahlen N istüberabzählbar.

Beweis I : Nehmen wir an es gäbe eine surjektive Funktion f: N[Abbildung in dieser Leseprobe nicht enthalten] N, die die Potenzmenge der natürlichen Zahlen abzählt. Wir definieren nun die Diagonalmenge D mit

Abbildung in dieser Leseprobe nicht enthalten

Aufgrund der Definition der Potenzmenge, ist auch D ⊂ P N. Da jedoch die Funktion f alle Elemente von P N abzählt, so gibt es auch ein d ∈ N mit

Abbildung in dieser Leseprobe nicht enthalten

Die Ausdrücke (2 . 17) sowie (2 . 19) ergeben dann zusammen für jede natürliche Zahl n

Abbildung in dieser Leseprobe nicht enthalten

Demnach gilt analoges für d selbst

Abbildung in dieser Leseprobe nicht enthalten

was einen offensichtlichen Widerspruch darstellt. `

Beweis II : Wir haben schon erwähnt, dass es sich bei der Mächtigkeit der Potenzmenge um Variationen mit Wiederholung handelt. Nehmen wir wiederum an, dass die Potenzmenge abzählbar ist. Dies ist gleichbedeutend damit, dass wir die Teilmengen der Menge der natürlichen

Zahlen auflisten können:

Abbildung in dieser Leseprobe nicht enthalten

Die Liste der Teilmengen ist derart dargestellt, dass für alle i, j ∈ N gilt b ij ∈ { 0 , 1 }. In Abhängigkeit davon, ob die entsprechende natürliche Zahl in der Teilmenge ist, nimmt b ij den Wert 1 an, andernfalls 0. Ändert man nun alle Werte für alle b ii, so erhalten wir auf der Diago- nale eine neue Teilmenge, die, obwohl Element der Potenzmenge, nicht in der ursprünglichen Liste zu finden war. Egal wie lang diese Liste nun ist (und wir wissen sogar, dass sie unendlich ist) wird diese Teilmenge in ihr nicht enthalten sein. Damit sind wir beim Widerspruch zu den Ausgangsannahme angelangt.

Die obige Darstellung nimmt im Wesentlichen die Grundstruktur des späteren semantischen (aber auch syntaktischen) Diagonallemmas oder Fixpunkttheorems schon vorweg. Ein Versuch eines Brückenschlags zwischen der Cantorschen Diagonalisierung und dem Diagonallemma bei Gödel und Carnap über die Antinomie von Richard ist bei Gaifmann (2006)²⁵ zu finden, ist jedoch für unser Anliegen von geringem Wert.²⁶

2.2 Allgemeines zu formalen Systemen

An dieser Stelle wollen wir nun einige Begrifflichkeiten im Zusammenhang mit formalen Systemen definieren, von denen in der Arbeit laufend gebraucht gemacht wird:

Definition 2.2.1 (Metaeigenschaften formaler Systeme)

1. Widerspruchsfreiheit: Ein formales System heißt widerspruchsfrei, wenn eine Formel nie- mals gleichzeitig mit ihrer Negation aus den Axiomen abgeleitet werden kann.
2. Negationsvollständigkeit: Ein formales System heißt negationsvollständig, wenn für jede Formel, die Formel selbst oder deren Negation aus den Axiomen abgeleitet werden kann.
3. Korrektheit: Ein formales System heißt korrekt, wenn jede Formel, die innerhalb des formalen Systems bewiesen werden kann, inhaltlich wahr ist.
4. Vollständigkeit: Ein formales System heißt vollständig, wenn jede Formel, die inhaltlich wahr ist, auch innerhalb des formalen Systems bewiesen werden kann.

Der Beweis der Widerspruchsfreiheit eines formalen axiomatischen Systems kann auf zwei Arten erfolgen. Man kann durch eine Interpretation des System diesem eine ”semantischeEbene“hinzufügen und mithilfe dieser einen relativen Widerspruchsbeweis konstruieren. Dieser bestünde dann im Beweis der Widerspruchsfreiheit des Systems unter der Annahme der Widerspruchsfreiheit seiner Interpre- tation. Ein derartiges Verfahren ist in der Mathematik nicht neu. Schon Hilbert bewies die relative Widerspruchsfreiheit der euklidischen Geometrie unter Rekurs auf die Arithmetik. Er konstruierte dabei einen speziellen Zahlenbereich, so dass die bestehenden Beziehungen zwischen den Objekten der euklidischen Geometrie bestimmten Beziehungen zwischen den Objekten des Zahlenbereichs ent- sprachen. Somit war die Widerspruchsfreiheit der euklidischen Geometrie auf jene der Arithmetik zurückgeführt.²⁷ Was an dieser Stelle jedoch ausblieb, war ein absoluter Beweis der Widerspruchsfrei- heit der Arithmetik selbst. Wenn sich nämlich herausstellen sollte, dass die Arithmetik selbst nicht widerspruchsfrei ist, ist die Zielsetzung des relativen Widerspruchsbeweises der euklidischen Geometrie verfehlt. Die Kette der relativen Widerspruchsbeweise muss somit bei einem absoluten Widerspruchs- beweis einer bestimmten Interpretation enden, will man die Widerspruchsfreiheit aller betrachteten Systeme gewährleisten.

Wir gehen nun daran zu sehen, ob dies möglich ist.

Teil II Metamathematik

Kapitel 3 Die semantische Variante des ersten Gödelschen

Unvollständigkeitssatzes

Gödel teilte seine Publikation zu den Unvollständigkeitssätzen aus dem Jahre 1931 in vier Abschnitte auf. Der erste stellt eine, von Gödel selbst vorausgeschickte Beweisskizze, der Unvollständigkeitssätze dar. Zugleich war dies auch die semantische Variante des ersten Unvollständigkeitssatzes. Der Vorteil einer derartigen Eröffnung liegt in der Möglichkeit den Beweisgang vereinfacht wiederzugeben und zentrale Ideen darzustellen, ohne sich im Detail der formalen Ableitungen zu verlieren. Gödels Ar- gumentationsstruktur tritt dadurch klar zum Vorschein. Der eigentliche syntaktische Beweis ist dann nurmehr eine Verschärfung des bisherigen Gedankenganges. Unweigerlich muss man sich jedoch der Annahmen des semantischen Beweises in Abgrenzung zu den syntaktischen Beweisen bewusst wer- den. Die Grafik auf der nächsten Seite gibt einen Überblick über den Zusammenhang zwischen den zugrunde liegenden Systemen und dem was daraus folgt.

Gödel beginnt seine Arbeit mit einer kurzen Bestandsaufnahme des damaligen Forschungsstandes auf dem Gebiet der Grundlagen der Mathematik:¹

” DieEntwicklungderMathematikinderRichtungzugr öß ererExaktheithatbekanntlich dazu geführt, daßweite Gebiete von ihr formalisiert wurden, in der Art, daßdas Bewei-

sen nach einigen wenigen mechanischen Regeln vollzogen werden kann. Die umfassendsten derzeit aufgestellten formalen Systeme sind das System der Principia Mathematik (PM) einerseits, das Zermelo-Fraenkelsche (von J. v. Neumann weiter ausgebildete) Axiomen- system der Mengenlehre andererseits. Diese beiden Systeme sind so weit, daßalle heute in der Mathematik angewandeten Beweismethoden in ihnen formalisiert, d. h. auf einige wenige Axiome und Schlußregeln zurückgeführt sind. Es liegt daher die Vermutung nahe, daßdiese Axiome und Schlußregeln dazu ausreichen, alle mathematischen Fragen, die sich in den betreffenen Systemenüberhaupt formal ausdrücken lassen, auch zu entschei- den. Im Folgenden wird gezeigt, daßdies nicht der Fall ist, sondern daßes in den beiden angeführten Systemen sogar relativ einfache Probleme aus der Theorie der gewöhnlichen ganzen Zahlen gibt, die sich aus den Axiomen nicht entscheiden lassen. “

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Drei Varianten des ersten Unvollständigkeitssatzes

Quelle: Eigene Darstellung basierend auf Hoffmann (2013): S. 144

Wie will Gödel seine Vermutung unter Beweis stellen? Er schafft es die Unvollständigkeitssätze zu beweisen indem er verschiedenste Neuerungen im Bereich der Metamathematik einführt. Kurz zusammenfassend sind dies:

1. Die Arithemtisierung der Syntax
2. Die Grundidee der Diagonalisierung bzw. das Diagonallemma
3. Die Anwendung primitiv-rekursiver Funktionen

Eine detaillierte Behandlung der Arithmetisierung der Syntax erfolgt erst bei der Darstellung der syntaktischen Variante des Beweises im Kapitel 4. Wir nehmen für die Zwecke der semantischen Variante einfach an, dass eine eineindeutige Kodierung der Syntax möglich ist. Die hiesige Darstellung der semantischen Variante des Unvollständigkeitssatzes unterscheidet sich jedoch in ihrer Darstellung von Gödel (1931) und orientiert sich an Smullyan (1992)². Begründet wird dies durch eine explizitere Ausarbeitung der zugrunde liegenden Annahmen des Beweises.³ Bevor wir uns dem Beweis selbst zuwenden, definieren wir zunächst einen Begriff den wir im Laufe der Arbeit immer wieder gebrauchen werden und der sozusagen das zentrale Phänomen der Arbeit darstellt:

Definition 3.0.2 (Hyperzirkularität)

Ein (formales) System ist hyperzirkulär (besitzt demnach die Eigenschaft der Hyperzirkularität) wenn in diesem ein Satz formuliert werden kann, derüber sich selbst spricht. Die Eigenschaft der Hyperzirkularität ist demnach mit strikter Selbstreflexion gleichzusetzen. Ein hyperzirkulärer Satz wäre ein Satz, der eine Funktion seiner eigenen Gödelnummer darstellt. Formal kann man dies folgendermaßen ausdrücken:

Abbildung in dieser Leseprobe nicht enthalten

Wir werden, die hier verwendeten, Begriffe im Laufe der Arbeit erarbeiten und vertiefen. Gehen wir von einer Sprache L aus. Für eine Darstellung der Hyperzirkularität brauchen uns die Eigenschaften dieser Sprache nicht näher zu interessieren. Diese Sprache besteht nun unter anderem aus Ausdrücken, in denen wiederum Prädikate H und S vorzufinden sind. Natürlich können die Sätze dieser Sprache entweder wahr oder falsch sein. Im ersteren Fall ist der Satz ein Element von T, im zweiten ein Element von F. Die Ausgangsannahme ist nun, dass die Sprache L vollständig und widerspruchslos ist. Dies bedeutet nichts anderes als, dass alle wahren Sätze zugleich auch beweisbar sind und für alle falschen Sätze, die Negation dieser beweisbar ist (deshalb auch (R)efutable). Demnach ist P (Provable) eine Untermenge von T und R (Refutable) eine Untermenge von F. Die Mengen R und T sind, gemäß den Annahmen, disjunkte Mengen, d. h. sie haben keine gemeinsamen Elemente. Das System L ist demnach korrekt.⁴ Die Beweisskizze besteht nun darin zu zeigen, dass derartige Annahmen zu einem Widerspruch führen: sie ist demnach eine Reductio ad absurdum.

Nehmen wir an es existiert eine Funktion ψ, die aus einem beliebigen Prädikat und einer Zahl einen Satz generiert. Unter der Annahme einer solchen Funktion können wir die Ausdrückbarkeit von Zahlenmengen definieren:

Definition 3.0.3 (Ausdrü ckbarkeit einer Menge von Zahlen durch ein Prädikat)

Für jede Menge A an Zahlen ( A ist eine Teilmenge der natürlichen Zahlen), wird diese durch ein Prädikat H ausgedrückt gerade dann wenn:

Abbildung in dieser Leseprobe nicht enthalten

Nun ist jedoch nicht jede Menge von Zahlen zugleich auch in einer Sprache ausdrückbar. Die folgende Definition erklärt diesen Sachverhalt:

Definition 3.0.4 (Ausdrü ckbarkeit einer Menge von Zahlen)

Eine Menge A ist ausdrückbar in einer Sprache L wenn A durch ein Prädikat der Sprache L ausdrückbar ist.

Doch für derartige Überlegungen bedarf es nicht einer formalen Sprache L. Auch in der normalen Sprache können Dingen gewisse Eigenschaften zugesprochen werden und auf diese Art Mengen festgelegt werden. Der Grund wieso die Untersuchungen jedoch in einer formalen Sprache geführt werden, besteht in der Unmöglichkeit gewisse Konstruktionen in der normalen Sprache darzustellen. So ist die Hyperzirkularität, der zentrale Aspekt des Gödelschen Beweises, lediglich in einer formalen Sprache ausdrückbar. Versuchen wir dies anhand eines einfachen Beispiels darzulegen:

Der Satz

” D ieserSatzistfalsch. “

ist eine Abwandlung des bekannten Lügner-Paradoxons. Im alltäglichen Sprachgebrauch ist dieser Satz ein Beispiel für ein semantisches Paradoxon. Der Grund dafür besteht offensichtlich in der Selbst- bezüglichkeit des Satzes. Auch Gödel geht in seiner Arbeit von diesem Satz aus und will Selbst- bezüglichkeit generieren. Doch er schafft dabei viel mehr. Während der obige Satz eine zirkuläre Konstruktion darstellt, hat es Gödel in seiner Arbeit geschafft Hyperzirkularität zu konstruieren. Es ist sehr wichtig zu bemerken, dass die nominelle Komponente des Satzes, d. h. ⁴ Siehe dazu auch die Definition in Abschnitt 2.2

Abbildung in dieser Leseprobe nicht enthalten⁵

Abbildung 3.2: Selbstreflexive Sätze der natürlichen Sprache

Quelle: Eigene Darstellung

Dies schaffte Gödel durch die Anwendung zweier Hilfsmittel: Der Gödelisierung und des Diagonal- lemmas. Wir werden die Arithmetisierung der Syntax erst an einer späteren Stelle behandeln (nämlich beim syntaktischen Beweis), da wir uns bisher zu wenig mit den Grundzeichen des Systems beschäftigt haben. Wir müssen daher im Rahmen des semantischen Beweises annehmen, dass eine eineindeutige Kodierung der Syntax durchführbar ist. Dies bedeutet, dass jedem Zeichen, jeder Formel und jeder Beweiskette eine eindeutige Zahl zugeordnet werden kann. Wie dies bewerkstelligt werden kann sehen wir in Kapitel 4.2.4.

Definition 3.0.5 (Funktionen und Mengen) Wir definieren folgende Funktionen:

- Die Funktion ψ : Die Funktion ψ , wie schon oben erläutert, generiert aus einer beliebigen Zahl und einem beliebigen Prädikat einen Satz.
- Die Funktion g : Die Funktion g ordnet einem beliebigen Ausdruck der Sprache L einein- deutig eine natürliche Zahl zu. Die Funktion g bildet die Ausdrücke der Sprache L bijektiv auf die Menge der natürlichen Zahlen ab. Sie steht für die Gödelisierung der Syntax und wird im Detail in Kapitel 4.2.4 behandelt.
- Die Funktion d : Unter der Anwendung der definierten Funktion g gilt g (E n) = n . Die Gödelnummer des Ausdrucks E ist somit die natürliche Zahl n . Um diesem Umstand Aus- druck zu verleihen, schreiben wir die Gödelnummer von E im Index. Die Diagonalisierung von E n steht für den Ausdruck E n (n) . Im Falle, dass E n ein Prädikat ist, ist seine Diago- nalisierung ein Satz im Sinne der, weiter oben definierten, Funktion ψ . d (n) ist dann die Gödelnummer des Ausdrucks E n (n) und wird Diagonalfunktion genannt.
- Die Menge A : Die Zahlenmenge A beinhaltet all jene Elemente, die nicht in A sind.
- Die Menge A : Für die Elemente der Zahlenmenge [Abbildung in dieser Leseprobe nicht enthalten]

Für die weitere Darstellung benötigen wir drei Hypothesen, die von Gödel in seinem Aufsatz bewiesen wurden:

[...]

---

¹ Siehe dazu beispielsweise Field, H.: Saving Truth From Paradox. OUP Oxford, 2008;Soames, S.: Understanding Truth. Oxford University Press, 1999 sowie Burgess, A.G. und Burgess, J.P.: Truth. Princeton University Press, 2011

² Hoffmann, D. W.: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis. Spektrum Akademischer Verlag, 2013.

³ Petzold, C.: The annotated Turing: a guided tour through Alan Turing’s historic paper on computability and the Turing machine. Wiley Pub., 2008.

⁴ Thiel, Ch.: Kurt Gödel: Die Grenzen der Kalküle. UTB Vandenhoeck, 1992, S. 147.

⁵ Genügend Stark steht in diesem Kontext stets für genügend stark um die Geltung der Unvollständigkeitssätze zu gewährleisten. Im Hauptteil des metamathematischen Abschnittes werden wir sehen, dass Gödel zeigt, dass nicht nur das System P, sondern auch das System P . A . (für Peano-Arithmetik) ein derartiges System darstellt. Zudem weiß man heute, dass die Robinson-Arithmetik Q nicht nur ebenfalls ein derartiges System darstellt, sondern zugleich auch das einfachste System darstellt, dass noch immer genügend stark ist um die Unvollständigkeitssätze zu gewährleisten.

⁶ Putnam, H.: Nonstandard Models and Kripke’s Proof of the Godel Theorem. 2000.

⁷ An dieser Stelle soll auf einen wichtigen Aspekt hingewiesen werden. Ebenso wie unsere oben gestellten Fragen, ist auch die Frage, ob der Beweisgang des ersten Unvollständigkeitssatzes ohne eine Art von Selbst- bezüglichkeit (oder irgendeiner Abwandlung des Diagonallemmas) auskommen kann nicht geklärt. Unsere Fragestellung ist jedoch viel tiefgreifender. Die Voraussetzung der Hyperzirkularität muss sich nicht expli- zit im Beweisgang niederlegen. Auch wenn Beweise existieren, die keine selbstbezüglichen Konstruktionen benötigen (ob dem so ist werden wir zumindest bei Kripke nachgehen) heißt dies nicht, dass das zugrunde liegende System nicht hyperzirkulär sein muss. Die Frage bezieht sich auf etwas grundlegenderes als die bloße Methodologie des Beweisganges.

⁸ Mostowski, A.: Sentences undecidable in formalized arithmetic: An exposition of the theory of Kurt Gödel. 1952.

⁹ Stegmüller, W.: Unvollständigkeit und Unentscheidbarkeit. Springer, 1970.

¹⁰ Die wichtigsten Begrifflichkeiten im Zusammenhang dem axiomatischen Systemen werden im Abschnitt

¹⁴ Dieser Ansatz wird jedoch lediglich beim Satz V des Gödelschen Beweisganges relativiert. Es handelt sich dabei um den Beweis der Darstellbarkeit aller primitiv-rekursiven Funktionen in P. Obwohl ein zentraler Aspekt des Beweises, ist dieser Teilbeweis durch seine mangelnde Bedeutung für unser Anliegen und einen enormen Schreibaufwand charakterisiert. Wir werden uns daher nur mit Erläuterungen hinsichtlich des Satzes V begnügen. Gödel selbst hat es nicht viel anders gemacht.

¹⁵ Rosser, B.: Extensions of Some Theorems of Gödel and Church. The Journal of Symbolic Logic, 1 09 1936, Nr. 3.

¹⁶ Putnam: Nonstandard Models and Kripke’s Proof of the Godel Theorem. ¹⁷ Lucas, J. R.: Minds, Machines and Gödel. Philosophy, 36 04 1961, Nr. 137.

¹⁸ Penrose, R.: The Emperor’s New Mind: Concerning Computers, Minds, and the Laws of Physics. Pen- guin Books, 1989 sowie Penrose, R.: Shadows of the Mind: A Search for the Missing Science of Consciousness. Vintage, 1995

¹ Hauff, J.K.F.: Euklids Elemente: das erste bis zum sechsten, sammt dem eilften und zwoelften Buche. In der neuen Academischen Buchhandlung, 1807.

² Kurt Gödel wurde am 28. April 1906 in Brünn (damals Österreichisch-UngarischeMonarchie) geboren. Sein Studium absolvierte er an der Universität Wien in den Fächern Physik und Mathematik bei Hans Hahn. Seit 1926 war er zudem aktives Mitglied des Wiener Kreises. Dort fand Gödel auch seine ersten Anregungen sich mit zentralen Fragen der Grundlagen der Mathematik auseinanderzusetzen. In diesem Zusammenhang besuchte er die Vorlesungen von Rudolf Carnap, David Hilbert und Wilhelm Ackermann. Er studierte an der

³ Whitehead, A.N./Russell, B.: Principia Mathematica. University Press, 1912.

⁴ Die Gödelschen Unvollständigkeitssätze werden mit den Begriff der Gödelschen Theoreme synonym ver- wendet.

⁵ Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis, Vgl. S. 66f.

⁶ Frege, G. und Angelelli, I.: Begriffsschrift und andere Aufsätze. Georg Olms, 1964.

⁷ Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis, Vgl. S. 44f.

⁸ Frege: Begriffsschrift und andere Aufsätze, S. X.

⁹ Frege, G.: Die Grundlagen der Arithmetik: eine logisch mathematische Untersuchung über den Begriff der Zahl. W. Koebner, 1884.

¹⁰ Cantor, G.: Über eine elementare Frage der Mannigfaltigkeitslehre. In Jahresbericht der Deutschen Mathematiker-Vereinigung. Deutsche Mathematiker-Vereinigung and Gutzmer, A. and Wölffing, E., 1892, v. 1-2.

¹¹ Bedürftig, T. und Murawski, R.: Philosophie der Mathematik. De Gruyter, 2010, S. 87.

¹² Frege, G.: Grundgesetze der arithmetik: begriffsschriftlich abgeleitet. H. Pohle, 1893, Grundgesetze der Arithmetik v. 1.

¹³ Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis, S. 76.

¹⁴ Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis, Vgl. S. 78.

¹⁵ A. a. O., S. 80.

¹⁶ Russell, B.: The Autobiography of Bertrand Russell: Vol.: 1 : (1872-1914) : 1967. George Allen and Unwin Limited, 1967, S. 149f.

¹⁷ Russell, B.: Mathematical Logic as Based on the Theory of Types. American Journal of Mathematics,

30 07 1908, Nr. 3, S. 224.

¹⁸ Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis, Vgl. S. 88.

¹⁹ Für folgende Ausführungen vergleiche auch Heuser, H.: Lehrbuch der Analysis: Mit 810 Aufgaben, zum Teil mit Lösungen. Teubner, 2006, Vgl. S. 398ff

²⁰ Wir werden vereinfacht annehmen, dass die Primzahlen paarweise verschieden sind. Falls zwei Primzahlen p n und q m gleich sein sollten, so würden diese in einem ersten Schritt gekürzt werden. Der Beweisgang würde daraufhin gleich verlaufen.

²¹ Hinweis für Zahlenpaare siehe Smith, P.: An Introduction to Gödel’s Theorems. Cambridge University Press, 2013, S. 11

²² Deiser, O.: Einführung in Die Mengenlehre. Springer, 2010, Vgl. S. 145ff.

²³ Siehe dazu beispielsweise Mladenović, P.: Kombinatorika. Društvo matematičara SR Srbije, 1989, S. 10ff

²⁴ Smith: An Introduction to Gödel’s Theorems, Vgl. S.12ff.

²⁵ Gaifman, H.: Naming and Diagonalization, from Cantor to Gödel to Kleene. Logic Journal of the IGPL, October 2006.

²⁶ So bemerkt auch Stegmüller (1970): ” D ieAntinomievonRichard,einesderhäufigangeführtenBeispiele logischer Paradoxien, kann durchüberführung aus der vagen Alltagssprache in ein nach präzisen Regeln auf- gebautes zahlentheoretisches System S sukzessive in das erste Theorem von Gödel umgeformt werden. Durch dieseüberführung verschwindet der antinomische Charakter des ersten Satzes und an die Stelle einer anti- nomischen Behauptung tritt ein wichtiges metamathematisches Resultat. Man kann geradezu sagen, daßdie Leistung Gödels darin bestand, die Fehler zu korrigieren, die für das Zustandekommen jener Antinomie ver- antwortlich zu machen sind, dabei aber zugleich die bei der Konstruktion der Antinomie verwendeten korrekten Schlüsse bezubehalten und sie in geschickter Weise für sein Theorem auszuwerten “ . Siehe dazu Stegmüller: Unvollständigkeit und Unentscheidbarkeit, S. 1

²⁷ Hoffmann: Die Gödel’schen Unvollständigkeitssätze: Eine geführte Reise durch Kurt Gödels historischen Beweis.

¹ Gödel, K.: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. 38 1931, Nr. 1, S. 173f.

² Smullyan: Godel’s Incompleteness Theorems, Vgl. S. 5ff.

³ An dieser Stelle werden nur einige wenige, für den semantischen Beweisgang notwendige Aspekte behandelt. Eine detaillierte Darstellung des Systems folgt dann im Kapitel zum syntaktischen Beweis.

⁴ Siehe dazu auch die Definition in Abschnitt 2.2

⁵ Wir sehen schon an dieser Stelle, dass ein derartiger Satz in der natürlichen Sprache nicht konstruiert werden kann. Wir kommen auf diesen Umstand nochmals im Kapitel 11 zu sprechen.

• College: University of Vienna (Institut für Philosophie)
• Course: Mathematische Philosophie
• Grade: 1,00
• Author: MSc, MA Edin Boskovic (Author)
• Publication Year: 2015
• Pages: 108
• Catalog Number: V314374
• ISBN (eBook): 9783668132405
• ISBN (Book): 9783668132412
• Language: German
• Tags: Gödel, Unvollständigkeit, Metamathematik, Hilbert, Cantor, Frege, Logik, Philosophie, Incompleteness, Kontinuumhypothese, Roser, Lucas, Antimechanismus, Mechanismus