Gödels Unvollständigkeitssätze (Gödel's incompleteness theorems)

Gödels Unvollständigkeitssätze sind zwei Sätze der mathematischen Logik, die sich mit den Grenzen der Beweisbarkeit in formalen axiomatischen Theorien befassen. Diese…

Gödels Unvollständigkeitssätze stellen grundlegende Aussagen innerhalb der mathematischen Logik dar und befassen sich mit den inhärenten Grenzen der Beweisbarkeit innerhalb formaler axiomatischer Systeme. Die Veröffentlichung dieser Erkenntnisse durch Kurt Gödel im Jahr 1931 markierte einen entscheidenden Moment sowohl für die mathematische Logik als auch für die Philosophie der Mathematik. Es wird allgemein verstanden, dass diese Theoreme die Unmöglichkeit von Hilberts Programm demonstrieren, das eine umfassende und konsistente axiomatische Grundlage für die gesamte Mathematik schaffen wollte.

Gödels Unvollständigkeitssätze sind zwei Theoreme der mathematischen Logik, die sich mit den Grenzen der Beweisbarkeit in formalen axiomatischen Theorien befassen. Diese 1931 von Kurt Gödel veröffentlichten Ergebnisse sind sowohl für die mathematische Logik als auch für die Philosophie der Mathematik von Bedeutung. Die Theoreme werden so interpretiert, dass sie zeigen, dass Hilberts Programm, einen vollständigen und konsistenten Satz von Axiomen für die gesamte Mathematik zu finden, unmöglich ist.

Der erste Unvollständigkeitssatz besagt, dass jedes konsistente axiomatische System, dessen Theoreme rekursiv aufzählbar sind (d. h. durch einen Algorithmus generiert werden können), nicht alle wahren Aussagen über die Arithmetik natürlicher Zahlen umfassen kann. Folglich bleiben innerhalb eines solchen konsistenten formalen Rahmens bestimmte wahre Aussagen über natürliche Zahlen zwangsläufig unbeweisbar. Umgekehrt wird es auch Aussagen über natürliche Zahlen geben, die falsch sind, deren Falschheit jedoch nicht formal innerhalb desselben Systems nachgewiesen werden kann.

Der zweite Unvollständigkeitssatz, der auf dem ersten aufbaut, zeigt, dass kein solches formales System seine eigene Konsistenz beweisen kann.

Unter Verwendung eines Diagonalarguments leiteten Gödels Unvollständigkeitssätze eine Reihe miteinander verbundener Erkenntnisse über die inhärenten Beschränkungen formaler Systeme ein. Zu den späteren Entwicklungen gehörte Tarskis Undefinierbarkeitssatz, der sich mit der formalen Undefinierbarkeit der Wahrheit befasst; Churchs Demonstration, dass Hilberts Entscheidungsproblem unentscheidbar ist; und Turings Theorem, der das Fehlen eines Algorithmus beweist, der das Halteproblem lösen kann.

Formale Systeme: Vollständigkeit, Konsistenz und effektive Axiomatisierung

Gödels Unvollständigkeitssätze sind auf formale Systeme anwendbar, die über eine ausreichende Komplexität verfügen, um die grundlegende Arithmetik natürlicher Zahlen zu artikulieren, vorausgesetzt, diese Systeme sind sowohl konsistent als auch effektiv axiomatisiert. Im Bereich der Logik erster Ordnung werden formale Systeme häufig als formale Theorien bezeichnet. Im weitesten Sinne stellt ein formales System einen deduktiven Rahmen dar, der einen spezifischen Satz von Axiomen und Regeln für die symbolische Manipulation (oder Inferenzregeln) umfasst, die die Ableitung neuer Theoreme aus den ursprünglichen Axiomen ermöglichen. Die Peano-Arithmetik erster Ordnung ist ein Beispiel für ein solches System, bei dem alle Variablen zur Darstellung natürlicher Zahlen bestimmt sind. Umgekehrt artikulieren in Systemen wie der Mengenlehre nur eine Teilmenge der Sätze des formalen Systems Aussagen über natürliche Zahlen. Entscheidend ist, dass sich die Unvollständigkeitssätze auf die formale Beweisbarkeit innerhalb dieser definierten Systeme beziehen und sie von informellen Vorstellungen der Beweisbarkeit unterscheiden.

Formale Systeme können verschiedene Eigenschaften aufweisen, insbesondere Vollständigkeit, Konsistenz und das Vorhandensein einer effektiven Axiomatisierung. Die Unvollständigkeitstheoreme zeigen jedoch, dass Systeme mit einem ausreichenden Grad an Arithmetik nicht alle drei dieser Kriterien gleichzeitig erfüllen können.

Effektive Axiomatisierung

Ein formales System wird als effektiv axiomatisiert (oder alternativ effektiv generiert) bezeichnet, wenn seine Sammlung von Theoremen rekursiv aufzählbar ist. Diese Bedingung impliziert die theoretische Existenz eines Rechenalgorithmus, der in der Lage ist, alle Theoreme innerhalb des Systems aufzulisten, ohne irgendwelche Nicht-Theoreme einzubeziehen. Anschauliche Beispiele für effektiv generierte Theorien umfassen die Peano-Arithmetik und die Zermelo-Fraenkel-Mengentheorie (ZFC).

Wahre Arithmetik, ein theoretisches Konstrukt, umfasst alle wahrheitsgemäßen Aussagen über Standard-Ganzzahlen, ausgedrückt in der Sprache der Peano-Arithmetik. Während diese Theorie sowohl Konsistenz als auch Vollständigkeit aufweist und einen ausreichenden Umfang an Arithmetik beinhaltet, fehlt ihr entscheidend ein rekursiv aufzählbarer Satz von Axiomen, wodurch sie die Voraussetzungen für die Unvollständigkeitssätze nicht erfüllt.

Vollständigkeit

Eine axiomatische Menge gilt als syntaktisch (oder Negation-) vollständig, wenn für jede in ihrer Sprache formulierte Aussage entweder die Aussage selbst oder ihre Negation formal aus den Axiomen abgeleitet werden kann. Diese spezifische Definition der Vollständigkeit ist für Gödels ersten Unvollständigkeitssatz relevant. Es sollte nicht mit der semantischen Vollständigkeit verwechselt werden, was bedeutet, dass die axiomatische Menge alle semantischen Tautologien beweisen kann, die der angegebenen Sprache innewohnen. In seinem eindeutigen Vollständigkeitssatz (der nicht mit den hier diskutierten Unvollständigkeitssätzen verwechselt werden sollte) zeigte Gödel, dass die Logik erster Ordnung semantische Vollständigkeit besitzt. Allerdings mangelt es ihm an syntaktischer Vollständigkeit, da bestimmte Sätze, die in der Sprache der Logik erster Ordnung ausgedrückt werden können, allein anhand ihrer grundlegenden Axiome weder bewiesen noch widerlegt werden können.

Hilbert und andere Mathematiker gingen davon aus, dass innerhalb eines mathematischen Systems irgendwann eine Axiomatisierung entdeckt werden würde, die den Beweis oder die Widerlegung (durch den Nachweis ihrer Negation) jeder mathematischen Formel ermöglichen würde.

Ein formales System kann syntaktisch unvollständig sein, entweder aufgrund seines Designs, wie es in verschiedenen Logiken üblich ist, oder aufgrund der Auslassung oder Unentdecktheit wesentlicher Axiome. Beispielsweise bleibt die euklidische Geometrie unvollständig, wenn das Parallelpostulat fehlt, da bestimmte Aussagen innerhalb ihres sprachlichen Rahmens, einschließlich des Parallelpostulats selbst, nicht aus den bestehenden Axiomen abgeleitet werden können. Analog ist die Theorie dichter linearer Ordnungen unvollständig, wird aber durch die Einbeziehung eines zusätzlichen Axioms, das die Abwesenheit von Endpunkten in der Ordnung behauptet, vollständig. Die Kontinuumshypothese, eine in der Sprache von ZFC formulierte Aussage, ist in ZFC nicht beweisbar, wodurch ZFC unvollständig wird. In diesem speziellen Szenario gibt es keinen offensichtlichen Kandidaten für ein neues Axiom, um diese Unvollständigkeit zu beheben.

Peano-Arithmetik erster Ordnung scheint konsistent zu sein. Unter der Annahme seiner Konsistenz verfügt es über einen unendlichen, aber rekursiv aufzählbaren Satz von Axiomen und ist in der Lage, ausreichend Arithmetik zu kodieren, um die Hypothesen des Unvollständigkeitssatzes zu erfüllen. Folglich ist die Peano-Arithmetik nach dem ersten Unvollständigkeitssatz unvollständig. Dieser Satz liefert ein konkretes Beispiel für eine arithmetische Aussage, die in Peanos Arithmetik weder beweisbar noch widerlegbar ist. Darüber hinaus gilt diese Aussage auch im Standardmodell. Darüber hinaus kann keine effektiv axiomatisierte, konsistente Erweiterung der Peano-Arithmetik Vollständigkeit erreichen.

Konsistenz

Eine Menge von Axiomen gilt als konsistent, wenn keine Aussage und ihre Negation aus diesen Axiomen abgeleitet werden können; umgekehrt gilt es als inkonsistent. Im Wesentlichen zeichnet sich ein konsistentes axiomatisches System durch seine Widerspruchsfreiheit aus.

Die Konsistenz der Peano-Arithmetik kann anhand von ZFC nachgewiesen werden, wenn auch nicht intern. Analog dazu kann ZFC selbst seine eigene Konsistenz nicht intern beweisen. Das System ZFC, ergänzt um das Axiom „Es existiert ein unzugänglicher Kardinal“, begründet jedoch die Konsistenz von ZFC, denn wenn κ den kleinsten solchen Kardinal darstellt, dann stellt V_κ innerhalb des von Neumann-Universums ein Modell von ZFC dar, und eine Theorie ist genau dann konsistent, wenn sie ein Modell besitzt.

Sollten alle darin enthaltenen Aussagen Würde man die Sprache der Peano-Arithmetik als Axiome übernehmen, wäre die resultierende Theorie vollständig, würde einen rekursiv aufzählbaren Satz von Axiomen besitzen und in der Lage sein, sowohl Addition als auch Multiplikation zu beschreiben. Dennoch würde es einer solchen Theorie an Konsistenz mangeln.

Weitere Beispiele inkonsistenter Theorien ergeben sich aus den Paradoxien, die sich manifestieren, wenn das Axiomschema des uneingeschränkten Verstehens innerhalb der Mengenlehre postuliert wird.

Systeme mit Arithmetik

Die Unvollständigkeitssätze sind ausschließlich auf formale Systeme anwendbar, die in der Lage sind, eine ausreichende Menge an Fakten über natürliche Zahlen nachzuweisen. Ein Paradebeispiel für eine solche ausreichende Sammlung ist die Menge der Theoreme innerhalb der Robinson-Arithmetik Q. Während bestimmte Systeme, wie die Peano-Arithmetik, Aussagen über natürliche Zahlen direkt artikulieren können, verfügen andere, wie die ZFC-Mengenlehre, über die Fähigkeit, Aussagen über natürliche Zahlen innerhalb ihres eigenen sprachlichen Rahmens zu interpretieren. Beide Ansätze eignen sich für die Anwendung der Unvollständigkeitssätze.

Die Theorie algebraisch abgeschlossener Körper mit einer bestimmten Charakteristik ist vollständig, konsistent und durch eine unendliche, aber rekursiv aufzählbare Menge von Axiomen gekennzeichnet. Dennoch ist es weder möglich, ganze Zahlen innerhalb dieser Theorie zu kodieren, noch kann die Theorie die Ganzzahlarithmetik beschreiben. Eine vergleichbare Veranschaulichung ist die Theorie der realen geschlossenen Felder, die grundsätzlich den Axiomen von Tarski für die euklidische Geometrie entspricht. Folglich stellt die euklidische Geometrie selbst, wie sie von Tarski formuliert wurde, eine vollständige, konsistente und effektiv axiomatisierte Theorie dar.

Die Presburger-Arithmetik umfasst einen Satz von Axiomen für natürliche Zahlen, der ausschließlich die Additionsoperation umfasst und die Multiplikation bewusst weglässt. Dieses System ist vollständig, konsistent und rekursiv aufzählbar und kann die Addition, aber nicht die Multiplikation natürlicher Zahlen kodieren. Dies zeigt, dass eine Theorie in der Lage sein muss, sowohl Addition als auch Multiplikation und nicht nur Addition zu kodieren, damit Gödels Theoreme anwendbar sind.

Dan Willard (2001) untersuchte bestimmte schwache arithmetische Systeme, die über ausreichende arithmetische Beziehungen verfügen, um die Gödel-Nummerierung zu formalisieren, aber nicht über die funktionale Fähigkeit zur Multiplikation verfügen und daher den zweiten Unvollständigkeitssatz nicht beweisen konnten; Insbesondere sind diese Systeme konsistent und in der Lage, ihre eigene Konsistenz zu beweisen.

Konfliktierende Ziele

Die Auswahl eines Axiomsatzes zielt typischerweise darauf ab, die Ableitung korrekter Ergebnisse zu maximieren und gleichzeitig den Beweis etwaiger fehlerhafter Aussagen auszuschließen. Beispielsweise könnte man sich eine Reihe wahrer Axiome vorstellen, die in der Lage sind, jede wahre arithmetische Aussage über natürliche Zahlen zu beweisen (Smith 2007, S. 2). Im Standardrahmen der Logik erster Ordnung beweist eine inkonsistente Axiomenmenge von Natur aus jede Aussage, die in ihrer Sprache ausgedrückt werden kann, ein Phänomen, das manchmal als Explosionsprinzip bezeichnet wird, und macht sie dadurch automatisch vollständig. Umgekehrt stellt eine Axiomenmenge, die sowohl Vollständigkeit als auch Konsistenz erreicht, eine maximale Sammlung nicht widersprüchlicher Theoreme dar.

Das in früheren Diskussionen zu Peano-Arithmetik, ZFC und ZFC + beobachtete Muster „Es existiert ein unzugänglicher Kardinal“ ist im Allgemeinen unveränderlich. Insbesondere kann das System ZFC + „Es existiert ein unzugänglicher Kardinal“ intern keine eigene Konsistenz herstellen. Darüber hinaus mangelt es an Vollständigkeit, wie die Kontinuumshypothese zeigt, die innerhalb von ZFC + unentscheidbar bleibt: „Es existiert ein unzugänglicher Kardinal“.

Der erste Unvollständigkeitssatz zeigt, dass innerhalb formaler Systeme, die elementare Arithmetik ausdrücken können, eine endliche, vollständige und konsistente Liste von Axiomen unerreichbar ist. Jede konsistente axiomatische Ergänzung lässt andere wahre Aussagen unweigerlich unbeweisbar, selbst mit dem neu aufgenommenen Axiom. Sollte ein Axiom eingeführt werden, das das System vervollständigt, wird diese Vollständigkeit auf Kosten der Inkonsistenz erreicht. Darüber hinaus kann selbst eine unendliche Liste von Axiomen nicht gleichzeitig vollständig, konsistent und effektiv axiomatisiert werden.

Erster Unvollständigkeitssatz

Gödels erster Unvollständigkeitssatz wurde ursprünglich als „Satz VI“ in Gödels 1931 erschienener Veröffentlichung „On Formally Undecidable Propositions of Principia Mathematica and Related Systems I“ vorgestellt. Die Hypothesen des Theorems wurden anschließend von J. Barkley Rosser (1936) durch die Anwendung von Rossers Trick verfeinert. Der resultierende Satz, der Rossers Verfeinerung beinhaltet, kann auf Englisch wie folgt formuliert werden, vorausgesetzt, dass ein „formales System“ eine effektive Erzeugung impliziert.

Erster Unvollständigkeitssatz: „Jedes konsistente formale System F, innerhalb dessen ein gewisser Umfang elementarer Arithmetik ausgeführt werden kann, ist unvollständig; d. h. es gibt Aussagen der Sprache von F, die in F weder bewiesen noch widerlegt werden können.“ (Raatikainen 2020)

Die unbeweisbare Aussage G_F, die durch den Satz identifiziert wird, wird allgemein als „Gödel-Satz“ bezeichnet und bezieht sich auf das System F. Die Demonstration beinhaltet die Konstruktion eines spezifischen Gödel-Satzes für das System F; Allerdings weist eine unendliche Vielzahl von Aussagen innerhalb der Systemsprache identische Eigenschaften auf, darunter beispielsweise die Konjunktion des Gödel-Satzes mit jedem logisch gültigen Satz.

Jedes effektiv generierte System besitzt einen einzigartigen Gödel-Satz. Man kann ein erweitertes System F' konstruieren, das die Gesamtheit von F umfasst und um G_F als zusätzliches Axiom erweitert wird. Diese Erweiterung wird kein vollständiges System ergeben, da Gödels Theorem weiterhin auf F' anwendbar bleibt und somit die Vollständigkeit von F' ausschließt. Folglich ist G_F aufgrund seines axiomatischen Status tatsächlich ein Theorem innerhalb von F'. Da G_F lediglich seine Unbeweisbarkeit in F behauptet, führt seine Beweisbarkeit innerhalb von F' zu keinem Widerspruch. Wenn sich der Unvollständigkeitssatz jedoch auf F' ausdehnt, wird für F' eine neuartige Gödel-Aussage G_F ' entstehen, die dessen anhaltende Unvollständigkeit demonstriert. Die Aussage G_F ' weicht von G_F ab, indem sie sich auf F' anstelle von F bezieht.

Syntaktische Form des Gödel-Satzes

Der Gödel-Satz ist so formuliert, dass er einen indirekten Selbstbezug aufweist. Es geht davon aus, dass ein durch eine bestimmte Verfahrenssequenz konstruierter Satz innerhalb von F nicht beweisbar ist. Dennoch ist diese Konstruktionssequenz genau so konzipiert, dass der resultierende Satz tatsächlich G_F selbst ist. Folglich behauptet der Gödel-Satz G_F implizit seine eigene Unbeweisbarkeit innerhalb des formalen Systems F.

Mit der Aufstellung des ersten Unvollständigkeitssatzes zeigte Gödel, dass das Konzept der Beweisbarkeit innerhalb eines formalen Systems vollständig mithilfe arithmetischer Funktionen artikuliert werden kann, die auf den Gödel-Zahlen basieren, die den Sätzen des Systems zugewiesen sind. Somit kann ein System, das in der Lage ist, numerische Fakten zu beweisen, indirekt auch Fakten zu seinen eigenen Aussagen feststellen, abhängig von seiner tatsächlichen Generierung. Untersuchungen zur Beweisbarkeit von Aussagen innerhalb eines solchen Systems werden dadurch zu Fragen nach den arithmetischen Eigenschaften von Zahlen selbst, die das System entscheiden könnte, wenn es vollständig wäre.

Während sich der Gödel-Satz indirekt auf Aussagen innerhalb des Systems F bezieht, offenbart seine Interpretation als arithmetische Behauptung folglich einen direkten Bezug ausschließlich auf natürliche Zahlen. Sie geht davon aus, dass keine natürliche Zahl eine bestimmte Eigenschaft besitzt, die durch eine primitive rekursive Beziehung definiert wird (Smith 2007, S. 141). Dementsprechend kann der Gödel-Satz innerhalb der Sprache der Arithmetik unter Verwendung einer einfachen syntaktischen Struktur formuliert werden. Insbesondere kann es als arithmetische Formel formuliert werden, die aus einer Reihe führender universeller Quantoren besteht, gefolgt von einem quantorenfreien Körper (diese Formeln befinden sich auf der Ebene $\Pi _{1}^{0}$ 14§ §1718§ {\displaystyle \Pi _{1}^{0}} der arithmetischen Hierarchie). Darüber hinaus kann der Gödel-Satz durch die Anwendung des MRDP-Theorems als Erklärung neu ausgedrückt werden, dass ein bestimmtes Polynom mit mehreren Variablen und ganzzahligen Koeffizienten niemals zu Null ausgewertet wird, wenn seine Variablen durch ganze Zahlen ersetzt werden (Franzén 2005, S. 71).

Wahrheit des Gödel-Satzes

Der erste Unvollständigkeitssatz legt fest, dass der Gödel-Satz G_F, formuliert innerhalb einer geeigneten formalen Theorie F, innerhalb von F nicht beweisbar ist. Da diese Unbeweisbarkeit, wenn man sie als arithmetische Aussage interpretiert, genau dem entspricht, was der Satz indirekt behauptet, ist der Gödel-Satz tatsächlich wahr (Smoryński 1977, S. 825; 28–33). Folglich wird der Satz G_F häufig als „wahr, aber unbeweisbar“ charakterisiert (Raatikainen 2020). Da der Gödel-Satz jedoch seine eigene beabsichtigte Interpretation nicht formal definieren kann, muss seine Wahrheit, insbesondere für G_F, durch eine außerhalb des Systems durchgeführte Metaanalyse ermittelt werden. Typischerweise kann diese Metaanalyse innerhalb des schwachen formalen Systems durchgeführt werden, das als primitive rekursive Arithmetik bekannt ist und die Implikation Con(F)→G_F demonstriert, wobei Con(F) eine kanonische Aussage darstellt, die die Konsistenz von F bestätigt (Smoryński 1977, S. 840; Kikuchi & Tanaka 1994, S. 403).

Während der Gödel-Satz einer konsistenten Theorie wahr ist, wenn er als Aussage über die beabsichtigte Interpretation der Arithmetik betrachtet wird, wird er in bestimmten nicht standardmäßigen Arithmetikmodellen falsch sein, eine Folge des Gödel-Vollständigkeitssatzes (Franzén 2005, S. 135). Dieser Satz legt fest, dass, wenn ein Satz unabhängig von einer Theorie ist, die Theorie Modelle besitzt, in denen der Satz wahr ist, und andere Modelle, in denen er falsch ist. Wie bereits erwähnt, ist der Gödel-Satz für ein System F eine arithmetische Behauptung, die die Nichtexistenz einer Zahl mit einer bestimmten Eigenschaft behauptet. Der Unvollständigkeitssatz zeigt, dass diese Behauptung unabhängig vom System F bleibt, und die Wahrheit des Gödel-Satzes ergibt sich aus der Tatsache, dass keine natürliche Standardzahl die fragliche Eigenschaft aufweist. Jedes Modell, bei dem der Gödel-Satz falsch ist, muss daher ein Element enthalten, das diese Eigenschaft innerhalb dieses Modells erfüllt. Ein solches Modell ist zwangsläufig „nicht standardisiert“, was bedeutet, dass es Elemente enthält, die keiner standardmäßigen natürlichen Zahl entsprechen (Raatikainen 2020, Franzén 2005, S. 135).

Beziehung zum Lügnerparadoxon

Im einleitenden Abschnitt von „On Formally Undecidable Propositions in Principia Mathematica and Related Systems I“ identifiziert Gödel Richards Paradoxon und das Lügnerparadoxon ausdrücklich als semantische Parallelen zu seinen Erkenntnissen zur syntaktischen Unvollständigkeit. Das Lügnerparadoxon wird bekanntlich in der Aussage ausgedrückt: „Dieser Satz ist falsch.“ Eine Analyse dieses Satzes offenbart seinen inhärenten Widerspruch: Wenn er wahr wäre, wäre er aufgrund seiner eigenen Behauptung falsch; umgekehrt, wenn es falsch wäre, wäre es dann wahr. Ein Gödel-Satz mit der Bezeichnung G für ein System F stellt eine analoge Behauptung zum Lügnersatz dar, ersetzt jedoch den Begriff der Wahrheit durch den der Beweisbarkeit. Konkret erklärt G: „G ist im System F nicht beweisbar.“ Die anschließende Untersuchung der Wahrheit und Beweisbarkeit von G stellt eine formalisierte Version der logischen Analyse dar, die auf die Wahrheitsbedingung des Lügnersatzes angewendet wird.

Es ist nicht möglich, in einem Gödel-Satz „nicht beweisbar“ durch „falsch“ zu ersetzen, da das Prädikat „Q ist die Gödel-Zahl einer falschen Formel“ nicht als arithmetische Formel dargestellt werden kann. Dieses als Undefinierbarkeitssatz von Tarski bekannte Prinzip wurde unabhängig von Gödel während seiner Arbeit am Beweis des Unvollständigkeitssatzes und von Alfred Tarski, dem Namensgeber des Satzes, entdeckt.

Erweiterungen von Gödels Originalergebnis

Im Vergleich zu den in Gödels Aufsatz von 1931 dargelegten Theoremen weisen viele zeitgenössische Formulierungen der Unvollständigkeitstheoreme in zwei Hauptaspekten eine größere Allgemeingültigkeit auf. Diese verallgemeinerten Aussagen sollen auf eine breitere Klasse von Systemen anwendbar sein und schwächere Annahmen hinsichtlich der Konsistenz einbeziehen.

Während Gödel die Unvollständigkeit des Principia Mathematica-Systems, eines spezifischen arithmetischen Rahmenwerks, demonstrierte, stellte er fest, dass eine parallele Demonstration für jedes effektive System mit einem bestimmten Grad an Ausdruckskraft erfolgen könne. Gödel kommentierte diese breitere Anwendbarkeit in der Einleitung seines Aufsatzes, beschränkte seinen Beweis jedoch aus Gründen der Konkretheit auf ein einziges System. In modernen Aussagen des Theorems ist es üblich, die Bedingungen der Wirksamkeit und Ausdruckskraft als Grundhypothesen für den Unvollständigkeitssatz zu formulieren und damit seinen Anwendungsbereich über ein bestimmtes formales System hinaus zu erweitern. Die genaue Terminologie zur Beschreibung dieser Bedingungen war noch nicht entwickelt, als Gödel seine Ergebnisse im Jahr 1931 veröffentlichte.

Die anfängliche Formulierung und Demonstration von Gödels Unvollständigkeitssatz erforderte die Prämisse, dass das fragliche formale System nicht nur konsistent, sondern insbesondere ω-konsistent war. Ein System wird als ω-konsistent definiert, wenn es nicht ω-inkonsistent ist. Umgekehrt weist ein System eine ω-Inkonsistenz auf, wenn es ein Prädikat P enthält, für das es zwar ~P(m) für jede bestimmte natürliche Zahl m beweist, aber gleichzeitig die Existenz einer natürlichen Zahl n beweist, die P(n) erfüllt. Dies impliziert, dass das System die Existenz einer Zahl mit der Eigenschaft P behauptet, gleichzeitig aber widerlegt, dass eine bestimmte Zahl diese Eigenschaft instanziiert. Während ω-Konsistenz von Natur aus Konsistenz mit sich bringt, ist das Gegenteil nicht der Fall; Konsistenz garantiert keine ω-Konsistenz. Im Jahr 1936 erweiterte J. Barkley Rosser den Unvollständigkeitssatz durch die Einführung eines modifizierten Beweises, bekannt als Rossers Trick, der lediglich die Konsistenz des Systems erforderte und damit die strengere Bedingung der ω-Konsistenz beseitigte. Diese Verfeinerung ist in erster Linie von technischer Bedeutung, da alle wahrheitsgemäßen formalen Theorien der Arithmetik – diejenigen, deren Axiome allgemein wahre Aussagen über natürliche Zahlen sind – von Natur aus ω-konsistent sind, wodurch Gödels ursprünglicher Satz auf sie anwendbar ist. Die robustere Iteration des Unvollständigkeitssatzes, die nur Konsistenz anstelle von ω-Konsistenz postuliert, wird heute allgemein als Gödels Unvollständigkeitssatz oder Gödel-Rosser-Satz anerkannt.

Der zweite Unvollständigkeitssatz

In jedem formalen System F, das grundlegende Arithmetik beinhaltet, kann eine Formel mit der Bezeichnung Cons(F) kanonisch konstruiert werden, um die Konsistenz von F darzustellen. Diese Formel artikuliert die Eigenschaft, dass keine natürliche Zahl existiert, was eine formale Ableitung innerhalb des Systems F kodiert, die in einem syntaktischen Widerspruch gipfelt. Häufig wird der syntaktische Widerspruch als „0=1“ instanziiert, was Cons(F) zu der Behauptung führt, dass keine natürliche Zahl eine Ableitung von „0=1“ aus den Axiomen von F kodiert.

Gödels zweiter Unvollständigkeitssatz zeigt, dass diese kanonisch definierte Konsistenzaussage, Cons(F), unter allgemeinen Annahmen nicht sein kann formal in F selbst bewiesen. Dieser Satz wurde ursprünglich als „Satz XI“ in Gödels wegweisender Veröffentlichung von 1931 „On Formally Undecidable Propositions in Principia Mathematica and Related Systems I“ vorgestellt. Für die nachfolgende Darstellung beinhaltet die Bezeichnung „formalisiertes System“ implizit die Annahme, dass F effektiv axiomatisiert ist. Der Satz besagt, dass für jedes konsistente System F, das in der Lage ist, einen ausreichenden Grad an elementarer Arithmetik auszudrücken, die Konsistenz von F nicht durch Beweis innerhalb von F selbst festgestellt werden kann. Dieser Satz übertrifft den ersten Unvollständigkeitssatz an Stärke, vor allem weil die im ersten Satz formulierte Aussage die Konsistenz des Systems nicht explizit zum Ausdruck bringt. Der Beweis des zweiten Unvollständigkeitssatzes wird erreicht, indem der Beweis des ersten Unvollständigkeitssatzes direkt im System F.

formalisiert wird

Konsistenz formalisieren

Eine wesentliche technische Nuance besteht innerhalb des zweiten Unvollständigkeitssatzes bezüglich der Methodik zur Darstellung der Konsistenz von F als Formel innerhalb der Sprache von F. Es gibt mehrere Ansätze, um die Konsistenz eines Systems zu artikulieren, und diese verschiedenen Formalisierungen führen nicht immer zu gleichwertigen Ergebnissen. Die spezifische Formel Cons(F), auf die im zweiten Unvollständigkeitssatz Bezug genommen wird, stellt eine besondere Formalisierung der Konsistenz dar.

Alternative Formalisierungen, die die Konsistenz von F behaupten, könnten sich innerhalb von F als inäquivalent erweisen, wobei einige sogar beweisbar sind. Beispielsweise ist die Peano-Arithmetik erster Ordnung (PA) in der Lage, die Konsistenz „der größten konsistenten Teilmenge von PA“ zu demonstrieren. Da PA selbst jedoch konsistent ist, ist seine größte konsistente Teilmenge per Definition PA selbst; Somit beweist PA in dieser spezifischen Interpretation „seine eigene Konsistenz“. Entscheidend ist, dass PA nicht beweist, dass seine größte konsistente Teilmenge tatsächlich die Gesamtheit von PA ist. (Hier bezieht sich „größte konsistente Teilmenge von PA“ auf das maximal konsistente Anfangssegment der PA-Axiome, wie durch eine bestimmte effektive Aufzählung bestimmt.)

Die Hilbert-Bernays-Beweisbedingungen

Der konventionelle Beweis des zweiten Unvollständigkeitssatzes geht davon aus, dass das Beweisbarkeitsprädikat Prov_A(P) den Hilbert-Bernays-Beweisbedingungen entspricht. Da #(P) die Gödel-Zahl bezeichnet, die einer Formel P entspricht, legen diese Beweisbarkeitsbedingungen Folgendes fest:

Sollte F einen Beweis für P liefern, folgt daraus, dass F Prov_A(#(P)) beweist.
F begründet die erste Hilbert-Bernays-Bedingung und zeigt insbesondere, dass F Prov_A(#(P)) → beweist Prov_A(#(Prov_A(#(P)))).
F beweist auch die zweite Hilbert-Bernays-Bedingung, die ein Analogon des Modus Ponens ist: Prov_A(#(P → Q)) ∧ Prov_A(#(P)) → Prov_A(#(Q)).

Bestimmte Systeme wie die Robinson-Arithmetik sind ausreichend robust, um die Prämissen des ersten Unvollständigkeitssatzes zu erfüllen, erfüllen jedoch nicht die Hilbert-Bernays-Bedingungen. Umgekehrt ist die Peano-Arithmetik robust genug, um diese Bedingungen zu bestätigen, eine Eigenschaft, die alle Theorien gemeinsam haben, die an Stärke die Peano-Arithmetik übertreffen.

Implikationen für Konsistenznachweise

Gödels zweiter Unvollständigkeitssatz legt ferner fest, dass ein System F§34§, sofern es die zuvor beschriebenen technischen Bedingungen erfüllt, nicht die Konsistenz eines Systems F§910§ beweisen kann, das selbst die Konsistenz von F§1516§ beweist. Der Grund dafür ist, dass ein solches System F§2122§ zeigen kann, dass, wenn F§2728§ die Konsistenz von F§3334§ beweist, F§3940§ nachweislich konsistent ist. Die Behauptung, dass F§4546§ konsistent ist, wird formal ausgedrückt als „für alle Zahlen n besitzt n die entscheidbare Eigenschaft, kein Code für einen Widerspruchsbeweis in F§5556§ zu sein.“ Wenn F§6162§ tatsächlich inkonsistent wäre, dann würde F§6768§ für ein bestimmtes n belegen, dass n den Code eines Widerspruchs innerhalb von F§7778§ darstellt. Wenn jedoch F§8384§ auch die Konsistenz von F§8990§ beweisen würde (d. h. die Nichtexistenz eines solchen n), dann wäre F§8384§ von Natur aus inkonsistent. Diese Argumentation kann in F§9798§ formal formuliert werden, um zu zeigen, dass, wenn F§103104§ konsistent ist, auch F§109110§ konsistent ist. Da F§115116§ nach dem zweiten Unvollständigkeitssatz seine eigene Konsistenz nicht beweist, ist es auch nicht in der Lage, die Konsistenz von F§121122§ zu beweisen.

Diese Folgerung des zweiten Unvollständigkeitssatzes zeigt die Unmöglichkeit, die Konsistenz der Peano-Arithmetik zu beweisen, zum Beispiel: durch alle finitistischen Methoden, die innerhalb eines Systems formalisierbar sind, dessen Konsistenz in der Peano-Arithmetik (PA) nachweisbar ist. Beispielsweise kann das System der primitiven rekursiven Arithmetik (PRA), das weithin als präzise Formalisierung der finitistischen Mathematik anerkannt wird, nachweislich innerhalb von PA konsistent sein. Folglich ist PRA nicht in der Lage, die Konsistenz von PA festzustellen. Diese Beobachtung wird weithin dahingehend interpretiert, dass Hilberts Programm, das die Anwendung „idealer“ (infinitistischer) mathematischer Prinzipien bei der Ableitung „realer“ (finitistischer) mathematischer Aussagen validieren wollte, indem es einen finitistischen Beweis für die Konsistenz dieser idealen Prinzipien lieferte, letztendlich unerreichbar ist.

Die Folgerung unterstreicht auch die erkenntnistheoretische Bedeutung des zweiten Unvollständigkeitssatzes. Eine solche Demonstration würde keine substanziellen Erkenntnisse liefern, wenn ein System F seine eigene Konsistenz beweisen würde. Dies ist darauf zurückzuführen, dass inkonsistente Theorien in der Lage sind, alle Aussagen, einschließlich ihrer eigenen Konsistenz, zu beweisen. Somit würde ein Konsistenznachweis von F innerhalb von F keinen Hinweis auf die Konsistenz von F liefern; Durch einen solchen Konsistenzbeweis würden keine Unsicherheiten über die Konsistenz von F beseitigt. Der Hauptwert von Konsistenzbeweisen liegt in der Möglichkeit, die Konsistenz eines Systems F innerhalb eines Systems F' festzustellen, das in gewisser Hinsicht weniger fragwürdig ist als F selbst, beispielsweise ein System, das nachweislich schwächer als F ist. Für viele häufig vorkommende Theorien F und F', wie z. B. F = Zermelo-Fraenkel-Mengentheorie und F' = primitive rekursive Arithmetik, ist die Konsistenz von F' innerhalb von F nachweisbar. Folglich kann F' die Konsistenz von F nicht beweisen, wie es die oben erwähnte Folgerung des zweiten Unvollständigkeitssatzes vorschreibt.

Der zweite Unvollständigkeitssatz schließt die Möglichkeit, die Konsistenz eines anderen Systems mit alternativen Axiomen zu beweisen, nicht vollständig aus. Beispielsweise stellte Gerhard Gentzen die Konsistenz der Peano-Arithmetik innerhalb eines alternativen Systems unter Einbeziehung eines Axioms fest, das die Begründetheit der als ε§34§ bezeichneten Ordnungszahl postuliert. Der Satz von Gentzen katalysierte die Weiterentwicklung der Ordinalanalysis in der Beweistheorie.

Beispiele für unentscheidbare Aussagen

Der Begriff „unentscheidbar“ hat in den Bereichen Mathematik und Informatik zwei unterschiedliche Interpretationen. Der erste, ein beweistheoretischer Sinn, wird im Zusammenhang mit Gödels Theoremen verwendet und bezeichnet eine Aussage, die innerhalb eines bestimmten deduktiven Systems weder beweisbar noch widerlegbar ist. Die zweite Interpretation, auf die hier nicht näher eingegangen wird, bezieht sich auf die Berechenbarkeitstheorie. Diese letztere Bedeutung gilt nicht für Aussagen, sondern für Entscheidungsprobleme, die als abzählbar unendliche Sammlungen von Fragen definiert sind, die jeweils eine binäre Antwort (Ja oder Nein) erfordern. Ein Problem wird als unentscheidbar klassifiziert, wenn keine berechenbare Funktion jede Frage innerhalb der dafür vorgesehenen Menge korrekt lösen kann.

Angesichts der doppelten Interpretation des Begriffs „unentscheidbar“ wird gelegentlich der Deskriptor „unabhängig“ als Alternative verwendet, insbesondere um die Bedeutung „weder beweisbar noch widerlegbar“ zu bezeichnen.

Die Unentscheidbarkeit einer Aussage innerhalb eines bestimmten deduktiven Systems befasst sich nicht unbedingt mit der Frage, ob der Wahrheitswert der Aussage wohldefiniert ist oder nicht mit alternativen Mitteln ermittelbar. Unentscheidbarkeit bedeutet vielmehr lediglich, dass das jeweils betrachtete deduktive System die Wahrheit oder Falschheit der Aussage nicht feststellen kann. Die Existenz sogenannter „absolut unentscheidbarer“ Aussagen, deren Wahrheitswert nie ermittelt werden kann oder schlecht spezifiziert ist, bleibt ein umstrittenes Thema in der Philosophie der Mathematik.

Die gemeinsame Forschung von Gödel und Paul Cohen hat zwei konkrete Beispiele für unentscheidbare Aussagen hervorgebracht, interpretiert im ersten Sinne des Begriffs. Insbesondere ist die Kontinuumshypothese innerhalb von ZFC, der Standardaxiomatisierung der Mengenlehre, weder beweisbar noch widerlegbar. Gleichzeitig ist das Auswahlaxiom innerhalb von ZF, das alle ZFC-Axiome außer umfasst, weder beweisbar noch widerlegbar. Diese speziellen Ergebnisse beruhen nicht auf dem Unvollständigkeitssatz. Gödel zeigte 1940, dass keine dieser Aussagen innerhalb der ZF- oder ZFC-Mengenlehre widerlegt werden konnte. Anschließend bewies Cohen in den 1960er Jahren, dass keine der beiden Aussagen mit ZF beweisbar ist, und darüber hinaus kann die Kontinuumshypothese nicht mit ZFC bewiesen werden.

Shelah (1974) stellte fest, dass das Whitehead-Problem, ein Konzept innerhalb der Gruppentheorie, im Rahmen der Standardmengentheorie im ersten Sinne des Wortes unentscheidbar ist.

Gregory Chaitin formulierte unentscheidbare Aussagen innerhalb der algorithmischen Informationstheorie und in Dieser Bereich bewies einen zusätzlichen Unvollständigkeitssatz. Der Unvollständigkeitssatz von Chaitin besagt, dass für jedes System, das in der Lage ist, eine ausreichende Menge an Arithmetik darzustellen, eine Obergrenze c existiert, so dass keine bestimmte Zahl innerhalb dieses Systems eine Kolmogorov-Komplexität von mehr als c besitzen kann. Während Gödels Theorem mit dem Lügnerparadoxon verbunden ist, ist Chaitins Ergebnis mit Berrys Paradoxon verbunden.

Unentscheidbare Aussagen in umfassenderen Systemen beweisbar

Diese Aussagen dienen als natürliche mathematische Äquivalente zu Gödels „wahrem, aber unentscheidbarem“ Satz. Während sie in einem umfassenderen System bewiesen werden können, das allgemein als gültige Form des Denkens gilt, bleiben sie in einem begrenzteren System wie der Peano-Arithmetik unentscheidbar.

1977 zeigten Paris und Harrington, dass das Paris-Harrington-Prinzip, eine Variante des unendlichen Ramsey-Theorems, in der Peano-Arithmetik (erster Ordnung) unentscheidbar ist, jedoch im robusteren System der Arithmetik zweiter Ordnung beweisbar ist. Anschließend zeigten Kirby und Paris, dass der Satz von Goodstein, eine Aussage über Folgen natürlicher Zahlen, die etwas einfacher ist als das Paris-Harrington-Prinzip, auch in der Peano-Arithmetik unentscheidbar ist.

Kruskals Baumsatz, der in der Informatik Anwendung findet, ist in der Peano-Arithmetik ebenfalls unentscheidbar, aber innerhalb der Mengenlehre beweisbar. Tatsächlich ist Kruskals Baumsatz (oder seine endliche Form) selbst im wesentlich stärkeren System ATR₀, das Prinzipien kodifiziert, die in der Philosophie der Mathematik als akzeptabel gelten und als Prädikativismus bezeichnet werden, unentscheidbar. Das verwandte, aber allgemeinere Graph-Minor-Theorem (2003) hat erhebliche Konsequenzen für die rechnerische Komplexitätstheorie.

Beziehung zur Berechenbarkeit

Der Unvollständigkeitssatz ist eng mit mehreren Erkenntnissen zu unentscheidbaren Mengen innerhalb der Rekursionstheorie verbunden.

Kleene (1943) demonstrierte einen Beweis für Gödels Unvollständigkeitssatz und nutzte dabei Grundprinzipien der Berechenbarkeitstheorie. Eine wichtige Erkenntnis in diesem Bereich ist die Unentscheidbarkeit des Stoppproblems, was bedeutet, dass kein Rechenalgorithmus genau feststellen kann, ob ein bestimmtes Programm P letztendlich beendet wird, wenn es mit einer bestimmten Eingabe ausgeführt wird. Kleenes Argument ging davon aus, dass, wenn ein vollständiges und effektives arithmetisches System mit spezifischen Konsistenzattributen existieren würde, das Halteproblem entscheidbar sein müsste, was eine logische Inkonsistenz darstellt. Diese besondere Beweismethode wurde auch von Shoenfield (1967), Charlesworth (1981) und Hopcroft & Ullman (1979).

Franzén (2005) erläutert, wie Matiyasevichs Lösung von Hilberts 10. Problem verwendet werden kann, um einen Beweis für Gödels ersten Unvollständigkeitssatz zu konstruieren. Matiyasevich stellte fest, dass es keinen Algorithmus gibt, der, wenn er mit einem multivariaten Polynom p(x§56§, x§910§,...,x_k) mit ganzzahligen Koeffizienten versehen wird, die Existenz einer ganzzahligen Lösung der Gleichung p = 0 feststellen kann. Gegeben sei dieser ganzzahlige Koeffizient Polynome und ganze Zahlen sind in der Sprache der Arithmetik direkt darstellbar. Jedes ausreichend robuste arithmetische System T würde die Existenz einer Lösung beweisen, wenn eine multivariate ganzzahlige Polynomgleichung p = 0 tatsächlich eine in den ganzen Zahlen besitzt. Unter der Annahme, dass das System T ω-Konsistenz aufweist, würde es außerdem niemals behaupten, dass eine bestimmte Polynomgleichung eine Lösung hat, wenn keine ganzzahlige Lösung existiert. Wenn also T sowohl vollständig als auch ω-konsistent wäre, könnte man algorithmisch bestimmen, ob eine Polynomgleichung eine Lösung hat, indem man einfach die Beweise innerhalb von T aufzählt, bis entweder „p hat eine Lösung“ oder „p hat keine Lösung“ entdeckt wird, was dem Satz von Matiyasevich direkt widerspricht. Daraus wird gefolgert, dass T nicht gleichzeitig ω-konsistent und vollständig sein kann. Darüber hinaus ist es für jedes konsistente, effektiv generierte System T möglich, effektiv ein multivariates Polynom p über den ganzen Zahlen zu konstruieren, so dass die Gleichung p = 0 keine ganzzahligen Lösungen hat, dieses Fehlen von Lösungen kann jedoch innerhalb von T nicht nachgewiesen werden.

Smoryński (1977) zeigt, wie das Vorhandensein rekursiv untrennbarer Mengen zur Feststellung der Gleichung genutzt werden kann erster Unvollständigkeitssatz. Diese Demonstration wird häufig erweitert, um zu zeigen, dass Systeme wie die Peano-Arithmetik grundsätzlich unentscheidbar sind.

Chaitins Unvollständigkeitssatz bietet einen alternativen Ansatz zur Generierung unabhängiger Aussagen, der auf der Kolmogorov-Komplexität basiert. Ähnlich wie Kleenes zuvor diskutierter Beweis ist Chaitins Theorem ausschließlich für Theorien relevant, die durch die zusätzliche Bedingung gekennzeichnet sind, dass alle ihre Axiome innerhalb des Standardmodells der natürlichen Zahlen wahr sind. Gödels Unvollständigkeitssatz zeichnet sich jedoch durch seine Anwendbarkeit auf konsistente Theorien aus, die im Standardmodell möglicherweise noch falsche Behauptungen enthalten; solche Theorien werden als ω-inkonsistent bezeichnet.

Übersicht über den Beweis des ersten Satzes

Der als reductio ad absurdum strukturierte Beweis besteht aus drei grundlegenden Komponenten. Zunächst muss ein formales System ausgewählt werden, das die festgelegten Kriterien erfüllt:

Aussagen sind innerhalb des Systems durch natürliche Zahlen, sogenannte Gödel-Zahlen, darstellbar. Diese Darstellung ist von entscheidender Bedeutung, da die Eigenschaften von Aussagen, einschließlich ihrer Richtigkeit oder Falschheit, der Feststellung spezifischer Eigenschaften ihrer entsprechenden Gödel-Zahlen gleichkommen. Folglich können Aussageeigenschaften durch eine Analyse ihrer Gödel-Zahlen aufgeklärt werden. Diese Phase gipfelt in der Formulierung eines Ausdrucks, der das Konzept vermittelt, dass „Aussage S innerhalb des Systems beweisbar ist“, ein Konzept, das auf jede Aussage „S“ innerhalb dieses Systems anwendbar ist.
Innerhalb des formalen Systems ist es möglich, eine Zahl zu konstruieren, deren entsprechende Aussage bei Interpretation Selbstreferenzialität aufweist und grundsätzlich ihre eigene Unbeweisbarkeit behauptet. Dies wird durch eine Methode erreicht, die als „Diagonalisierung“ bekannt ist, ein Begriff, der von seinen konzeptionellen Wurzeln in Cantors Diagonalargument abgeleitet ist.
Wenn sich diese Aussage innerhalb des formalen Systems befindet, ermöglicht sie den Nachweis, dass sie innerhalb dieses Systems weder beweisbar noch widerlegbar ist, was darauf hinweist, dass das System in Wirklichkeit nicht ω-konsistent sein kann. Folglich wird die ursprüngliche Prämisse, dass das vorgeschlagene System die angegebenen Kriterien erfüllt, ungültig.

Arithmetisierung der Syntax

Die größte Herausforderung bei der Ausarbeitung des oben genannten Beweises liegt im ersten Anschein, dass die Konstruktion einer Aussage p, die besagt, dass „p nicht bewiesen werden kann“, die Einbeziehung von p in eine Selbstreferenz auf p erfordern würde, was möglicherweise zu einem unendlichen Regress führen würde. Gödels Methodik löst dieses Problem, indem sie zeigt, dass Aussagen mit Zahlen korreliert werden können – ein Prozess, der als Arithmetisierung der Syntax bezeichnet wird – und so die Ersetzung von „Beweisen einer Aussage“ durch „Testen, ob eine Zahl eine bestimmte Eigenschaft besitzt“ ermöglicht. Dieser Ansatz erleichtert die Konstruktion einer selbstreferenziellen Formel, ohne dass es zu einem unendlichen Definitionsregress kommt. Alan Turing verwendete diese identische Technik anschließend in seiner Forschung zum Entscheidungsproblem.

Es kann ein Mechanismus etabliert werden, bei dem jeder im System ausdrückbaren Formel oder Aussage eine eindeutige Gödel-Zahl zugewiesen wird, was eine mechanische bidirektionale Konvertierung zwischen Formeln und ihren entsprechenden Gödel-Zahlen ermöglicht. Obwohl diese Zahlen eine beträchtliche Ziffernlänge aufweisen können, behindert diese Eigenschaft den Prozess nicht; Der entscheidende Aspekt ist ihre Konstruierbarkeit. Ein anschauliches Beispiel ist die Darstellung von englischem Text als Zahlenfolge für jeden Buchstaben, die anschließend zu einer einzelnen, größeren Zahl zusammengefasst wird:

Der Begriff

„Hallo“ wird mithilfe von ASCII als 104-101-108-108-111 codiert und kann dann in die zusammengesetzte Zahl 104101108108111 umgewandelt werden.
Der logische Satz x=y => y=x wird in ASCII als 120-061-121-032-061-062-032-121-061-120 dargestellt, der anschließend in den numerischen Wert 120061121032061062032121061120 umgewandelt werden kann.

Grundsätzlich kann gezeigt werden, dass der Nachweis der Wahrheit oder Falschheit einer Aussage analog zum Nachweis ist, ob die entsprechende Gödel-Zahl eine bestimmte Eigenschaft besitzt oder nicht. Da das formale System robust genug ist, um Überlegungen zu Zahlen im Allgemeinen zu erleichtern, ist es auch in der Lage, Überlegungen zu Zahlen anzustellen, die Formeln und Aussagen symbolisieren. Da das System Argumente über Eigenschaften von Zahlen berücksichtigen kann, ist es von entscheidender Bedeutung, dass die abgeleiteten Schlussfolgerungen äquivalent zu Schlussfolgerungen hinsichtlich der Beweisbarkeit der entsprechenden Aussagen sind.

Entwicklung einer Aussage zum Thema „Provability“

Nachdem gezeigt wurde, dass das System im Wesentlichen indirekt Aussagen zur Beweisbarkeit formulieren kann, ermöglicht eine Analyse der Eigenschaften von Zahlen, die diese Aussagen darstellen, die Konstruktion einer Aussage, die diese Funktion direkt erfüllt.

Eine Formel F(x), die durch das Vorhandensein genau einer freien Variablen x gekennzeichnet ist, wird als Anweisungsform oder Klassenzeichen bezeichnet. Bei der Ersetzung von x durch einen bestimmten numerischen Wert wandelt sich die Aussageform in eine gutgläubige Aussage um, die dann innerhalb des Systems entweder beweisbar oder nicht beweisbar ist. Für bestimmte Formeln kann gezeigt werden, dass für jede natürliche Zahl n der Ausdruck ⁠ $F(n)$ ⁠ gilt genau dann, wenn es beweisbar ist (die genaue Bedingung im Originalbeweis ist weniger streng, aber diese Vereinfachung ist für eine Beweisskizze ausreichend). Dieses Prinzip gilt insbesondere für jede arithmetische Operation, die eine endliche Menge natürlicher Zahlen betrifft, wie zum Beispiel „2 × 3 = 6“.

Aussageformen sind ihrer Natur nach keine Aussagen und können daher weder bewiesen noch widerlegt werden. Dennoch kann jeder Aussageform F(x) eine Gödel-Zahl zugeordnet werden, symbolisiert als G(F). Die spezifische Auswahl der freien Variablen innerhalb der Form F(x) hat keinen Einfluss auf die Zuweisung ihrer Gödel-Zahl G(F).

Das Konzept der Beweisbarkeit selbst kann ebenfalls mithilfe von Gödel-Zahlen durch den folgenden Mechanismus kodiert werden: Vorausgesetzt, dass ein Beweis eine geordnete Folge von Aussagen darstellt, die bestimmten Regeln entsprechen, kann eine Gödel-Zahl für einen Beweis erstellt werden. Anschließend kann man für jede gegebene Aussage p fragen, ob eine Zahl x die Gödel-Zahl ihres Beweises darstellt. Die Beziehung zwischen der Gödel-Zahl von p und x (der potentiellen Gödel-Zahl seines Beweises) stellt eine arithmetische Beziehung zwischen diesen beiden numerischen Werten dar. Folglich existiert eine Aussageform Bew(y), die diese arithmetische Beziehung nutzt, um die Existenz einer Gödel-Zahl entsprechend einem Beweis von y.

zu behaupten

Die Formel Bew(y) ist als existierendes x definiert, sodass y die Gödel-Zahl einer Formel und x die Gödel-Zahl eines Beweises für die durch y kodierte Formel darstellt.

Die Bezeichnung Bew ist eine Abkürzung für beweisbar, den deutschen Begriff für „beweisbar“, den Gödel ursprünglich zur Bezeichnung der oben genannten Beweisbarkeitsformel verwendete. Es ist wichtig zu beachten, dass „Bew(y)“ lediglich als Abkürzung für eine bestimmte, umfangreiche Formel in der Originalsprache von T fungiert; Es wird nicht behauptet, dass die Literalzeichenfolge „Bew“ ein Element dieser Sprache ist.

Ein wesentliches Merkmal der Formel Bew(y) ist, dass die Beweisbarkeit einer Aussage p innerhalb des Systems die Beweisbarkeit von Bew(G(p)) impliziert. Diese Implikation entsteht, weil jeder Beweis von p eine eindeutige Gödel-Zahl besitzt und die Existenz dieser Zahl die Bedingung für Bew(G(p)).

erfüllt

Diagonalisierung

Die anschließende Phase des Beweises beinhaltet die Ableitung einer Aussage, die implizit ihre eigene Unbeweisbarkeit erklärt. Während Gödel diese Aussage direkt formulierte, ist die Existenz mindestens einer solchen Behauptung eine Folge des Diagonallemmas. Dieses Lemma geht davon aus, dass es für jedes ausreichend robuste formale System und jede Aussageform F eine Aussage p gibt, für die das System beweist

p ↔ F(G(p)).

Durch die Definition von F als Negation von Bew(x) wird der folgende Satz abgeleitet:

p ↔ ~Bew(G(p))

Die Aussage p, wie sie durch diese Äquivalenz definiert wird, besagt näherungsweise, dass ihre eigene Gödel-Zahl der Gödel-Zahl einer unbeweisbaren Formel entspricht.

Die Aussage p ist nicht direkt äquivalent zu ~Bew(G(p)). Stattdessen geht p davon aus, dass die Ausführung einer bestimmten Berechnung eine Gödel-Zahl ergibt, die einer unbeweisbaren Aussage entspricht. Bei der Durchführung dieser Berechnung stellt sich jedoch heraus, dass die resultierende Gödel-Zahl die von p selbst ist. Dieses Phänomen entspricht dem folgenden englischen Satz:

“, wenn es sich selbst in Anführungszeichen voranstellt, ist nicht beweisbar. „, wenn es sich selbst in Anführungszeichen voranstellt, ist nicht beweisbar.

Dieser Satz bezieht sich nicht explizit auf sich selbst; Wenn jedoch die angegebene Transformation angewendet wird, wird der ursprüngliche Satz erzeugt, wodurch dieser indirekt seine eigene Unbeweisbarkeit behauptet. Die Demonstration des diagonalen Lemmas verwendet eine analoge Methodik.

Unter der Annahme, dass das axiomatische System ω-konsistent ist, stelle anschließend p die im vorherigen Abschnitt abgeleitete Aussage dar.

Wenn p beweisbar wäre, dann wäre Bew(G(p)) auch beweisbar nachweisbar, wie bereits festgestellt. p behauptet jedoch die Negation von Bew(G(p)). Folglich würde das System Inkonsistenz aufweisen, wenn es sowohl eine Aussage als auch ihre Negation beweist. Dieser inhärente Widerspruch zeigt, dass p nicht beweisbar sein kann.

Wenn die Negation von p beweisbar wäre, dann wäre auch Bew(G(p)) beweisbar, vorausgesetzt, dass p so konstruiert wurde, dass es der Negation von entspricht Bew(G(p)). Dennoch kann x für eine bestimmte Zahl x nicht die Gödel-Zahl des Beweises für p darstellen, da p nicht beweisbar ist, wie im vorherigen Absatz festgestellt. Folglich würde das System gleichzeitig die Existenz einer Zahl beweisen, die eine bestimmte Eigenschaft besitzt (die Gödel-Zahl des Beweises von p), und gleichzeitig für jede bestimmte Zahl x beweisen, dass ihr diese Eigenschaft fehlt. Ein solcher Widerspruch ist innerhalb eines ω-konsistenten Systems unmöglich. Daher ist die Negation von p nicht beweisbar.

Folglich ist die Aussage p innerhalb des Axiomatiksystems unentscheidbar, was bedeutet, dass sie intern weder formal bewiesen noch widerlegt werden kann.

Der Nachweis, dass p nicht beweisbar ist, erfordert lediglich die Annahme der Systemkonsistenz. Die strengere Annahme der ω-Konsistenz ist wesentlich, um die Unbeweisbarkeit der Negation von p zu beweisen. Wenn also p für ein bestimmtes System formuliert wird:

Sollte das System ω-konsistent sein, ist es nicht in der Lage, entweder p oder seine Negation zu beweisen, was p unentscheidbar macht.
Wenn das System lediglich konsistent ist, könnte es das gleiche Szenario aufweisen oder möglicherweise die Negation von p beweisen. Im letzteren Fall wäre eine Aussage („nicht p“) sowohl falsch als auch beweisbar, was darauf hinweist, dass das System nicht ω-konsistent ist.

Wenn versucht wird, ein System durch „fehlende Axiome“ zu ergänzen, um seine Unvollständigkeit zu beheben, müssen entweder p oder „nicht p“ als Axiome eingebaut werden. Diese Änderung ändert jedoch die Definition von „eine Gödel-Zahl eines Beweises sein“ für eine gegebene Aussage und ändert folglich die Formel Bew(x). Die Anwendung des diagonalen Lemmas auf dieses überarbeitete „Bew“ ergibt dann eine neue Aussage, p, die sich von ihrem Vorgänger unterscheidet und im erweiterten System unentscheidbar bleibt, sofern sie die ω-Konsistenz beibehält.

Demonstration unter Verwendung von Berrys Paradoxon

Boolos (1989) skizzierte eine alternative Demonstration des ersten Unvollständigkeitssatzes, indem er Berrys Paradoxon anstelle des Lügnerparadoxons verwendete, um eine Aussage zu formulieren, die zwar wahr, aber nicht beweisbar ist. Saul Kripke entwickelte unabhängig eine vergleichbare Beweismethodik. Boolos‘ Ansatz besteht darin, für jede berechenbar aufzählbare Menge S wahrer arithmetischer Sätze einen zusätzlichen Satz zu konstruieren, der wahr ist, aber kein Mitglied von S. Diese Konstruktion liefert als direkte Konsequenz den ersten Unvollständigkeitssatz. Boolos postulierte, dass dieser Beweis von Bedeutung sei, weil er eine „andere Art von Grund“ für die inhärente Unvollständigkeit darstelle, die in effektiven, konsistenten Theorien der Arithmetik beobachtet werde.

Computerisch verifizierte Beweise

Die Unvollständigkeitssätze stellen eine ausgewählte Gruppe nicht trivialer mathematischer Sätze dar, die erfolgreich formalisiert wurden und ihre vollständige Überprüfung durch Beweisassistentensoftware ermöglichen. Gödels erste Demonstrationen dieser Theoreme, die mit den meisten mathematischen Beweisen übereinstimmten, wurden für das menschliche Verständnis in natürlicher Sprache formuliert.

Rechnerisch verifizierte Beweise für verschiedene Iterationen des ersten Unvollständigkeitssatzes wurden berichtet: Natarajan Shankar im Jahr 1986 unter Verwendung von Nqthm (Shankar 1994), Russell O'Connor im Jahr 2003 unter Verwendung von Rocq (früher bezeichnet als Coq) (O'Connor 2005) und John Harrison im Jahr 2009 mit HOL Light (Harrison 2009). Darüber hinaus kündigte Lawrence Paulson 2013 unter Verwendung von Isabelle (Paulson 2014) einen computerverifizierten Beweis an, der beide Unvollständigkeitssätze umfasst.

Überblick über den Beweis des zweiten Satzes

Die größte Herausforderung beim Nachweis des zweiten Unvollständigkeitssatzes besteht darin, nachzuweisen, dass die verschiedenen Prinzipien der Beweisbarkeit, die integraler Bestandteil des Beweises des ersten Unvollständigkeitssatzes sind, innerhalb eines Systems S durch ein formales Prädikat P, das die Beweisbarkeit darstellt, formal ausgedrückt werden können. Nach Erreichen dieser Formalisierung wird der zweite Unvollständigkeitssatz abgeleitet, indem der gesamte Beweis des ersten Unvollständigkeitssatzes innerhalb des Systems S selbst formalisiert wird.

Es sei p der zuvor konstruierte unentscheidbare Satz. Um einen Widerspruch abzuleiten, nehmen wir an, dass die Konsistenz des Systems S innerhalb des Systems S selbst nachweisbar ist. Diese Annahme ist gleichbedeutend mit dem Beweis der Behauptung „System S ist konsistent.“ Betrachten Sie anschließend die Aussage c, definiert als c = „Wenn System S konsistent ist, dann ist p nicht beweisbar.“ Die Demonstration des Satzes c kann innerhalb des Systems S formalisiert werden, wodurch die Aussage c, „p ist nicht beweisbar“ (oder äquivalent: „nicht P(p)), innerhalb des Systems S bewiesen werden kann.

Daraus folgt, dass die Konsistenz des Systems S festgestellt werden kann (d. h. die Aussage innerhalb der Hypothese von c), dann ist p als unbeweisbar erwiesen. Dies führt jedoch zu einem Widerspruch, da der Erste Unvollständigkeitssatz vorschreibt, dass genau dieser Satz (insbesondere das, was mit c impliziert wird, „p“ ist nicht beweisbar“) genau das ist, was als unbeweisbar konstruiert wird. Diese Notwendigkeit unterstreicht die Notwendigkeit, den Ersten Unvollständigkeitssatz innerhalb von S zu formalisieren: Um den Zweiten Unvollständigkeitssatz zu beweisen, ist ein Widerspruch zum Ersten Unvollständigkeitssatz erforderlich, der nur durch den Nachweis seiner Gültigkeit innerhalb von S erreichbar ist. Folglich kann die Konsistenz des Systems S nicht bewiesen werden, woraus sich direkt die Behauptung des Zweiten Unvollständigkeitssatzes ergibt.

Analyse und Auswirkungen

Die Erkenntnisse zur Unvollständigkeit haben erheblichen Einfluss auf die Philosophie der Mathematik, insbesondere auf formalistische Perspektiven, die sich auf ein singuläres System formaler Logik stützen, um ihre Grundprinzipien abzugrenzen.

Implikationen für den Logismus und Hilberts zweites Problem

Gödels Unvollständigkeitssätze werden gelegentlich als erhebliche Herausforderung für das von Gottlob Frege und Bertrand Russell entwickelte logistische Programm angesehen, das natürliche Zahlen durch logische Prinzipien begründen wollte. Bob Hale und Crispin Wright behaupten jedoch, dass diese Theoreme die Logik nicht untergraben, da sie sowohl auf die Logik erster Ordnung als auch auf die Arithmetik anwendbar sind. Sie behaupten, dass dieses Problem in erster Linie Personen betrifft, die postulieren, dass natürliche Zahlen ausschließlich innerhalb der Logik erster Ordnung definiert werden müssen.

Zahlreiche Logiker behaupten, dass Gödels Unvollständigkeitssätze einen entscheidenden Rückschlag für David Hilberts zweites Problem darstellten, das einen endlichen Konsistenzbeweis für die Mathematik suchte. Insbesondere der zweite Unvollständigkeitssatz wird häufig so interpretiert, dass er dieses Problem unlösbar macht. Dennoch wird diese Interpretation unter Mathematikern nicht allgemein akzeptiert und der endgültige Status von Hilberts zweitem Problem bleibt ungeklärt.

Geister und Maschinen

Wissenschaftler, darunter der Philosoph J. R. Lucas und der Physiker Roger Penrose, haben ausführlich die möglichen Auswirkungen von Gödels Unvollständigkeitstheoremen auf die menschliche Intelligenz diskutiert. Ein zentraler Aspekt dieses Diskurses dreht sich um die Frage, ob der menschliche Geist als gleichwertig mit einer Turing-Maschine oder, in Erweiterung der Church-Turing-These, mit jedem endlichen Rechengerät betrachtet werden kann. Sollte diese Äquivalenz zutreffen und die Konsistenz der Maschine vorausgesetzt, wären dann Gödels Unvollständigkeitstheoreme anwendbar.

Putnam (1960) schlug vor, dass Gödels Theoreme zwar aufgrund ihrer Fehlbarkeit und inhärenten Inkonsistenz nicht auf einzelne Menschen anwendbar seien, sie aber für die breitere menschliche Fähigkeit zu Naturwissenschaften oder Mathematik relevant sein könnten. Unter der Annahme ihrer Konsistenz bleibt ihre Konsistenz entweder unbeweisbar, oder sie kann nicht angemessen durch eine Turing-Maschine dargestellt werden.

Wigderson (2010) vertritt die These, dass der Begriff der mathematischen „Erkennbarkeit“ auf rechnerischer Komplexität und nicht nur auf logischer Entscheidbarkeit beruhen sollte. Er behauptet, dass „wenn Erkennbarkeit nach modernen Standards interpretiert wird, nämlich durch rechnerische Komplexität, die Gödel-Phänomene uns sehr nahe stehen.“

In seinen Werken Gödel, Escher, Bach und I Am a Strange Loop verweist Douglas Hofstadter auf Gödels Theoreme als Veranschaulichung dessen, was er als seltsame Schleife bezeichnet – eine hierarchische, selbstreferenzielles Konstrukt, das einem axiomatischen formalen System innewohnt. Er geht davon aus, dass dieses strukturelle Merkmal dem entspricht, was Bewusstsein erzeugt, insbesondere das subjektive Ich-Gefühl in der menschlichen Psyche. Während die Selbstreferenz in Gödels Theorem aus dem Gödel-Satz stammt, der seine eigene Unbeweisbarkeit innerhalb des formalen Systems der Principia Mathematica behauptet, entsteht die Selbstreferenz im menschlichen Geist aus dem Prozess des Gehirns, Reize in „Symbole“ – oder auf Konzepte reagierende neuronale Gruppen – zu abstrahieren und zu kategorisieren, innerhalb dessen, was als formales System fungiert und letztendlich Symbole erzeugt, die die wahrnehmende Entität selbst modellieren. Hofstadter behauptet weiter, dass eine seltsame Schleife innerhalb eines ausreichend komplizierten formalen Systems eine „nach unten gerichtete“ oder „auf den Kopf gestellte“ Kausalität erzeugen kann, ein Szenario, in dem die herkömmliche Hierarchie von Ursache und Wirkung umgekehrt wird. In Bezug auf Gödels Theorem wird dieses Phänomen wie folgt prägnant veranschaulicht:

Allein aus der Kenntnis der Bedeutung der Formel kann man auf ihre Wahrheit oder Falschheit schließen, ohne sich die Mühe machen zu müssen, sie auf die altmodische Art und Weise abzuleiten, die erfordert, dass man von den Axiomen aus methodisch „nach oben“ stapft. Das ist nicht nur eigenartig; es ist erstaunlich. Normalerweise kann man sich nicht einfach nur ansehen, was eine mathematische Vermutung aussagt, und sich einfach auf den Inhalt dieser Aussage allein berufen, um daraus abzuleiten, ob die Aussage wahr oder falsch ist.

Für den Geist, der ein deutlich komplexeres formales System darstellt, wird diese „Abwärtskausalität“ von Hofstadter als die unbeschreibliche menschliche Intuition wahrgenommen, dass mentale Kausalität auf der höheren Ebene von Wünschen, Konzepten, Persönlichkeiten, Gedanken und Ideen liegt und nicht auf der niedrigeren Ebene neuronaler Interaktionen oder sogar fundamentaler Teilchen, obwohl die Physik letzteren kausale Kraft zuschreibt.

Es gibt also eine merkwürdige Umkehrung unserer normalen menschlichen Art, die Welt wahrzunehmen: Wir sind darauf ausgelegt, „große Dinge“ und nicht „kleine Dinge“ wahrzunehmen, auch wenn die Domäne des Kleinen dort zu liegen scheint, wo die eigentlichen Motoren, die die Realität antreiben, angesiedelt sind.

Paraconsistent Logic

Während Gödels Theoreme typischerweise im Rahmen der klassischen Logik untersucht werden, tragen sie auch zur Untersuchung parakonsistenter Logik und intrinsisch widersprüchlicher Sätze bei, die als Dialetheia bekannt sind. Priest (1984, 2006) behauptet, dass die Ersetzung des Konzepts des formalen Beweises in Gödels Theorem durch das konventionelle Verständnis des informellen Beweises die Inkonsistenz der naiven Mathematik aufzeigen und damit den Dialetheismus unterstützen kann. Diese Inkonsistenz entsteht dadurch, dass ein Wahrheitsprädikat für ein System direkt in die eigene Sprache des Systems integriert wird. Shapiro (2002) bietet eine differenziertere Bewertung der Relevanz von Gödels Theoremen für den Dialetheismus.

Extramathematische Anwendungen der Unvollständigkeitssätze

Die Unvollständigkeitssätze werden gelegentlich durch Appelle und Analogien herangezogen, um Argumente zu untermauern, die über die Bereiche der Mathematik und Logik hinausgehen. Zahlreiche Wissenschaftler, darunter Franzén (2005), Raatikainen (2005), Sokal & Bricmont (1999) und Stangroom & Benson (2006) hat solch weitreichende Anwendungen und Interpretationen kritisch beurteilt. Sokal & Bricmont (1999) und Stangroom & Benson (2006) zitiert Rebecca Goldsteins Beobachtungen zur Diskrepanz zwischen Gödels explizitem Platonismus und den antirealistischen Aneignungen seiner Konzepte. Sokal & Bricmont (1999) kritisiert insbesondere Régis Debrays Anwendung des Theorems in einem soziologischen Rahmen, eine Verwendung, die Debray später als metaphorisch verteidigt hat (ebd.).

Historischer Kontext

Nach der Veröffentlichung seiner Doktorarbeit im Jahr 1929, in der er den Beweis des Vollständigkeitssatzes vorstellte, befasste sich Gödel anschließend mit einem besonderen Problem für seine Habilitation. Sein ursprüngliches Ziel war es, eine positive Lösung für Hilberts zweites Problem zu erreichen. Zu dieser Zeit wurden theoretische Rahmenwerke, die natürliche und reelle Zahlen umfassten, ähnlich der Arithmetik zweiter Ordnung, als „Analyse“ bezeichnet, während Theorien, die ausschließlich natürliche Zahlen betrafen, als „Arithmetik“ bezeichnet wurden.

Gödel war nicht der einzige Forscher, der sich mit dem Konsistenzproblem beschäftigte. Im Jahr 1925 hatte Ackermann einen fehlerhaften Konsistenzbeweis zur Analyse vorgelegt und dabei versucht, Hilberts ursprüngliche Methode der ε-Substitution anzuwenden. Später im selben Jahr korrigierte von Neumann diesen Beweis erfolgreich für ein arithmetisches System ohne Induktionsaxiome. Bis 1928 hatte Ackermann Bernays einen überarbeiteten Beweis übermittelt, was Hilbert dazu veranlasste, 1929 seine Überzeugung zu äußern, dass die Konsistenz der Arithmetik nachgewiesen sei und dass bald ein konsistenter Beweis für die Analyse entstehen würde. Nach der Veröffentlichung der Unvollständigkeitssätze, die den inhärenten Fehler in Ackermanns überarbeitetem Beweis aufdeckten, lieferte von Neumann jedoch ein konkretes Beispiel, das die grundsätzliche Unzulänglichkeit seiner primären Technik demonstrierte.

Während seiner Untersuchungen stellte Gödel fest, dass eine Aussage, die ihre eigene Falschheit behauptet, zwar zu einem Paradoxon führt, eine Aussage, die ihre Unbeweisbarkeit bestätigt, jedoch nicht. Insbesondere war sich Gödel des Ergebnisses bewusst, das später als Tarskis Undefinierbarkeitssatz bezeichnet wurde, obwohl er es nie offiziell veröffentlichte. Am 26. August 1930 gab Gödel Carnap, Feigel und Waismann seinen ersten Unvollständigkeitssatz bekannt; Alle vier Personen sollten an der zweiten Konferenz zur Erkenntnistheorie der exakten Wissenschaften teilnehmen, einer bedeutenden Versammlung, die in der darauffolgenden Woche in Königsberg stattfand.

Formelle Präsentation

Die Königsberger Konferenz von 1930 war eine gemeinsame Versammlung dreier akademischer Gesellschaften, die viele prominente Logiker dieser Zeit anzog. Carnap, Heyting und von Neumann hielten jeweils einstündige Vorlesungen über die mathematischen Philosophien des Logikismus, des Intuitionismus und des Formalismus. Auf dem Konferenzprogramm stand auch Hilberts Abschiedsrede, die er anlässlich seines Abschieds von der Universität Göttingen hielt. In seiner Rede brachte Hilbert seine Überzeugung zum Ausdruck, dass alle mathematischen Probleme lösbar sind, und schloss seine Ansprache mit der Aussage:

Für den Mathematiker gibt es kein Ignorabimus, und meiner Meinung nach auch überhaupt nicht für die Naturwissenschaften. ... Der wahre Grund, warum es [niemandem] gelungen ist, ein unlösbares Problem zu finden, liegt meiner Meinung nach darin, dass es kein unlösbares Problem gibt. Im Gegensatz zum törichten Ignorabimus lautet unser Credo: Wir müssen es wissen. Wir werden es wissen!

Diese Ansprache erlangte schnell Anerkennung als prägnante Zusammenfassung von Hilberts philosophischer Haltung zur Mathematik; Die abschließenden sechs Worte „Wir müssen wissen. Wir werden wissen!“ wurden später 1943 als sein Epitaph eingraviert. Trotz Gödels wahrscheinlicher Anwesenheit bei Hilberts Adresse hatten die beiden Gelehrten nie eine persönliche Begegnung.

Gödel präsentierte seinen ersten Unvollständigkeitssatz während einer Diskussionsrunde am dritten Tag der Konferenz. Diese Enthüllung erregte nur minimale Aufmerksamkeit, außer von Neumann, der Gödel in eine private Diskussion verwickelte. Anschließend, im selben Jahr, leitete von Neumann unabhängig einen Beweis für den zweiten Unvollständigkeitssatz ab und baute dabei auf seinem Verständnis des ersten auf. Diese Entdeckung teilte er Gödel mit einem Brief vom 20. November 1930 mit. Gleichzeitig hatte Gödel unabhängig den zweiten Unvollständigkeitssatz aufgestellt und in sein Manuskript aufgenommen, das am 17. November 1930 bei den Monatsheften für Mathematik eingereicht wurde.

Gödels bahnbrechende Arbeit mit dem Titel „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I“ (übersetzt als „Über formal unentscheidbare Sätze in Principia Mathematica und verwandten Systemen I“) wurde 1931 in den Monatsheften veröffentlicht. Der Titel deutet auf Gödels ursprüngliche Absicht hin, einen zweiten Teil des Aufsatzes in einem späteren Band der Monatshefte zu veröffentlichen; Die schnelle Akzeptanz der ersten Veröffentlichung führte jedoch zu einer Überarbeitung seiner ursprünglichen Pläne.

Generalisierung und Akzeptanz

Zwischen 1933 und 1934 hielt Gödel in Princeton eine Reihe von Vorlesungen über seine Theoreme, an denen namhafte Persönlichkeiten wie Church, Kleene und Rosser teilnahmen. In dieser Zeit erkannte Gödel, dass eine entscheidende Voraussetzung für seine Theoreme die Wirksamkeit des Systems war, das damals als „allgemein rekursiv“ bezeichnet wurde. Im Jahr 1936 zeigte Rosser, dass die ω-Konsistenzhypothese, ein grundlegender Bestandteil von Gödels erstem Beweis, durch einfache Konsistenz ersetzt werden kann, vorausgesetzt, der Gödel-Satz wurde entsprechend modifiziert. Diese Fortschritte verfeinerten die Unvollständigkeitssätze in ihrer zeitgenössischen Formulierung.

Gentzen legte 1936 seinen Konsistenzbeweis für die Arithmetik erster Ordnung vor. Hilbert hielt diesen Beweis für „endlich“, obwohl er, wie Gödels Satz zuvor festgestellt hatte, nicht formal innerhalb des arithmetischen Systems ausgedrückt werden kann, dessen Konsistenz er beweisen soll.

Die tiefgreifenden Auswirkungen der Unvollständigkeitssätze auf Hilberts Programm wurden schnell anerkannt. Im Jahr 1939 nahm Bernays einen umfassenden Beweis der Unvollständigkeitssätze in den zweiten Band der Grundlagen der Mathematik auf. Dieser Band enthielt auch Ackermanns ergänzende Erkenntnisse zur ε-Substitutionsmethode und Gentzens Konsistenzbeweis für die Arithmetik und markierte damit die erste vollständige veröffentlichte Demonstration des zweiten Unvollständigkeitssatzes.

Kritiken

Finsler

Im Jahr 1926 verwendete Finsler eine Variante von Richards Paradoxon, um einen Ausdruck zu formulieren, der nachweislich falsch, aber innerhalb eines von ihm entwickelten spezifischen, informellen Rahmens nicht beweisbar war. Gödel war sich dieser Veröffentlichung nicht bewusst, als er seine Unvollständigkeitssätze aufstellte (Collected Works Bd. IV., S. 9). Im Jahr 1931 korrespondierte Finsler mit Gödel, um ihn über dieses Papier zu informieren und seine Priorität in Bezug auf einen Unvollständigkeitssatz zu bekräftigen. Finslers Methodik beruhte jedoch nicht auf formalisierter Beweisbarkeit und hatte nur oberflächliche Ähnlichkeit mit Gödels Beiträgen. Gödel überprüfte das Papier, stellte jedoch erhebliche Mängel fest und äußerte in seiner Antwort an Finsler seine Bedenken hinsichtlich der fehlenden Formalisierung. Im Laufe seiner weiteren Karriere setzte sich Finsler beharrlich für seine Philosophie der Mathematik ein, die bewusst eine Formalisierung vermied.

Zermelo

Im September 1931 kommunizierte Ernst Zermelo mit Gödel und stellte fest, was er als „wesentliche Lücke“ in Gödels Argumentation bezeichnete. Gödel antwortete im Oktober mit einem zehnseitigen Brief und stellte klar, dass Zermelos Prämisse – dass der Begriff der Wahrheit innerhalb eines Systems durch dasselbe System definierbar sei – falsch sei, ein Punkt, der im Allgemeinen durch Tarskis Undefinierbarkeitssatz widerlegt wird. Dennoch blieb Zermelo hartnäckig und veröffentlichte seine Kritiken, darunter „einen ziemlich vernichtenden Absatz über seinen jungen Konkurrenten“. Gödel kam mit Carnaps Zustimmung zu dem Schluss, dass ein weiteres Engagement in dieser Angelegenheit unproduktiv wäre. Ein wesentlicher Teil von Zermelos späterer Forschung konzentrierte sich auf Logiken, die robuster sind als die Logik erster Ordnung, mit denen er sowohl die Konsistenz als auch die Kategorizität mathematischer Theorien demonstrieren wollte.

Wittgenstein

Ludwig Wittgensteins posthum veröffentlichtes Werk Bemerkungen zu den Grundlagen der Mathematik aus dem Jahr 1953 enthält mehrere Passagen, in denen die Unvollständigkeitssätze erörtert werden. Ein bestimmter Abschnitt, der oft als „berüchtigter Absatz“ bezeichnet wird, deutet auf eine mögliche Verschmelzung von „wahr“ und „beweisbar“ innerhalb von Russells System hin. Gödel war mit dem Wiener Kreis verbunden, als Wittgensteins frühe Philosophie, insbesondere *Tractatus Logico-Philosophicus*, den intellektuellen Diskurs der Gruppe maßgeblich beeinflusste. Es ist eine Debatte darüber entstanden, ob Wittgenstein den Unvollständigkeitssatz wirklich missverstanden oder seine Gedanken lediglich mehrdeutig artikuliert hat. Gödels posthume Papiere zeigen seine Überzeugung, dass Wittgenstein seine Konzepte falsch interpretiert hat.

Zahlreiche Kommentatoren haben Wittgenstein so interpretiert, als hätte er Gödels Werk missverstanden. Alternative Lesarten von Floyd & Putnam (2000) und Priest (2004) behaupten, dass ein Großteil dieses Kommentars Wittgensteins tatsächliche Position falsch interpretiert. Bei ihrer Erstveröffentlichung verfassten Bernays, Dummett und Kreisel jeweils äußerst kritische Rezensionen zu Wittgensteins Äußerungen. Die einhellige negative Aufnahme sorgte dafür, dass Wittgensteins Beobachtungen zu den Unvollständigkeitssätzen nur minimale Auswirkungen innerhalb der Logikgemeinschaft hatten. Im Jahr 1972 stellte Gödel ausdrücklich fest: „Hat Wittgenstein den Verstand verloren? Meint er es ernst? Er äußert absichtlich trivial unsinnige Aussagen“ und teilte Karl Menger mit, dass Wittgensteins Kommentare ein grundlegendes Missverständnis der Unvollständigkeitssätze zeigten.

Aus den von Ihnen zitierten Passagen geht klar hervor, dass Wittgenstein [den ersten Unvollständigkeitssatz] nicht verstanden hat (oder vorgab, ihn nicht zu verstehen). Er interpretierte es als eine Art logisches Paradoxon, während es in Wirklichkeit genau das Gegenteil ist, nämlich ein mathematischer Satz innerhalb eines absolut unumstrittenen Teilgebiets der Mathematik (finitäre Zahlentheorie oder Kombinatorik).

Die Veröffentlichung von Wittgensteins „Nachlass“ im Jahr 2000 löste eine Reihe philosophischer Aufsätze aus, in denen die Berechtigung der anfänglichen Kritik an seinen Äußerungen beurteilt wurde. Floyd & Putnam (2000) argumentiert, dass Wittgenstein über ein umfassenderes Verständnis des Unvollständigkeitssatzes verfügte als bisher angenommen. Ihre Analyse konzentriert sich insbesondere auf die Interpretation eines Gödel-Satzes für ein ω-inkonsistentes System mit der Aussage „Ich bin nicht beweisbar“, da es in einem solchen System an Modellen mangelt, bei denen das Beweisbarkeitsprädikat die tatsächliche Beweisbarkeit genau widerspiegelt. Umgekehrt behauptet Rodych (2003), dass es ihrer Interpretation von Wittgenstein an historischer Untermauerung mangele. Berto (2009) untersucht die Zusammenhänge zwischen Wittgensteins Schriften und Theorien der parakonsistenten Logik.

Referenzen

Artikel von Gödel

Kurt Gödel, 1931, „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I“, *Monatshefte für Mathematik und Physik*, V. 38 n. 1, S. 173–198. doi:10.1007/BF01700692
–, 1931, „On Formally Undecidable Propositions of Principia Mathematica and Related Systems, I“, in Solomon Feferman, Hrsg., 1986. Kurt Gödel Collected Works, Bd. Ich. Oxford University Press, S. 144–195. ISBN 978-0195147209. Dieser Band präsentiert den deutschen Originaltext mit einer gegenüberliegenden englischen Übersetzung, vorangestellt durch eine einleitende Anmerkung von Stephen Cole Kleene.
–, 1951, „Some Basic Theorems on the Foundations of Mathematics and Their Implications“, in Solomon Feferman, Hrsg., 1995. Kurt Gödel Collected Works, Bd. III, Oxford University Press, S. 304–323. ISBN 978-0195147223.

Übersetzungen von Gödels Aufsatz ins Englische zu seinen Lebzeiten

Die nachfolgenden Übersetzungen weisen Unstimmigkeiten sowohl im Wortlaut als auch in der typografischen Darstellung auf. Typografische Genauigkeit ist von entscheidender Bedeutung, da Gödel ausdrücklich beabsichtigte, „jene metamathematischen Begriffe hervorzuheben, die zuvor in ihrem üblichen Sinne definiert wurden ...“. (van Heijenoort 1967, S. 595). Es stehen drei verschiedene Übersetzungen zur Verfügung. In Bezug auf die ursprüngliche Übersetzung wies John Dawson auf die erheblichen Mängel und die „vernichtende Bewertung“ hin, die sie im Journal of Symbolic Logic erhielt. Darüber hinaus äußerte Gödel selbst seine Unzufriedenheit mit Braithwaites Begleitkommentar (Dawson 1997, S. 216). Diese Meltzer-Übersetzung wurde später durch eine verbesserte Version ersetzt, die Elliott Mendelson für Martin Davis‘ Anthologie The Undecidable erstellt hatte. Obwohl Mendelson diese Übersetzung für „nicht ganz so gut“ hielt wie erwartet, stimmte er ihrer Veröffentlichung aus Zeitgründen zu (ebd.). Aus Dawsons Fußnote geht hervor, dass Mendelson diese Entscheidung später bereute, da der veröffentlichte Band durch schlechte Typografie und zahlreiche Fehler beeinträchtigt war (ebd.). Dawson bestätigt weiterhin, dass Gödel die Übersetzung von Jean van Heijenoort (ebd.) bevorzugte. Eine zusätzliche Version, die für fortgeschrittene Studierende wertvoll ist, enthält Vorlesungsunterlagen, transkribiert von Stephen Kleene und J. B. Rosser. Diese Notizen dokumentieren Vorträge, die Gödel im Frühjahr 1934 am Institute for Advanced Study hielt (vgl. Kommentar von Davis 1965, S. 39 und ab S. 41). Diese besondere Wiedergabe trägt den Titel „Über unentscheidbare Sätze formaler mathematischer Systeme“. Folgendes ist in chronologischer Reihenfolge der Veröffentlichung aufgeführt:

Meltzer, B. (Übersetzer) und Braithwaite, R. B. (Einleitung). (1962). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Dover Publications, New York (Dover-Ausgabe, 1992). ISBN 0-486-66980-7 (Taschenbuch). Diese Ausgabe enthält eine hilfreiche Übersetzung von Gödels deutschen Abkürzungen auf den Seiten 33–34. Allerdings gelten, wie bereits erwähnt, die Typografie, Übersetzung und Kommentare in diesem Band als unzuverlässig. Bedauerlicherweise wurde diese Übersetzung, einschließlich ihres fragwürdigen Inhalts, anschließend nachgedruckt von:

Hawking, S. (Herausgeber). (2005). Gott erschuf die ganzen Zahlen: Die mathematischen Durchbrüche, die die Geschichte veränderten. Running Press, Philadelphia. ISBN 0-7624-1922-9. Gödels Aufsatz beginnt auf Seite 1097, gefolgt von Hawkings Kommentar ab Seite 1089.

Davis, M. (Herausgeber). (1965). Das Unentscheidbare: Grundlegende Arbeiten zu unentscheidbaren Sätzen, unlösbaren Problemen und berechenbaren Funktionen. Raven Press, New York. (Keine ISBN). Gödels Artikel beginnt auf Seite 5, gefolgt von einer einzigen Seite mit redaktionellen Kommentaren.
van Heijenoort, J. (Herausgeber). (1967). (3. Auflage). Von Frege bis Gödel: Ein Quellenbuch zur mathematischen Logik, 1879-1931. Harvard University Press, Cambridge, Massachusetts. ISBN 0-674-32449-8 (Taschenbuch). Van Heijenoort war für die Übersetzung verantwortlich. Er bemerkte, dass „Professor Gödel die Übersetzung genehmigte, die an vielen Stellen seinen Wünschen entsprach“ (S. 595). Gödels Aufsatz beginnt auf Seite 595, van Heijenoorts Kommentar geht ihm auf Seite 592 voran.
Davis, M. (Herausgeber). (1965). (Ebenda). „Über unentscheidbare Sätze formaler mathematischer Systeme.“ Diese Ausgabe präsentiert eine Version, die Gödels Errata-Korrekturen und zusätzliche Anmerkungen enthält, beginnend auf Seite 41, gefolgt von zwei Seiten Kommentar von Davis. Vor seiner Aufnahme in Davis‘ Band war dieser Vortrag nur als vervielfältigte Notiz verfügbar.

Wissenschaftliche Artikel anderer Autoren

Boolos, G. (1989). „Ein neuer Beweis des Gödel-Unvollständigkeitssatzes.“ Notices of the American Mathematical Society, 36, 388–390, 676. Nachdruck in Boolos (1998, S. 383–388).
Buldt, B. (2014). „Der Umfang von Gödels erstem Unvollständigkeitssatz.“ Logica Universalis, 8, 499–552. doi:10.1007/s11787-014-0107-3.
Charlesworth, A. (1981). „Ein Beweis des Gödelschen Theorems in Bezug auf Computerprogramme.“ Mathematics Magazine, 54(3), 109–121. doi:10.2307/2689794. JSTOR 2689794..
Davis, M. (2006). „Der Unvollständigkeitssatz.“ (PDF). Mitteilungen des AMS, 53(4), 414.Finsler, Paul (1926). "Formale Beweise und die Entscheidbarkeit". Mathematische Zeitschrift, 25, 676–682. doi:10.1007/bf01283861. S2CID 121054124.Grattan-Guinness, Ivor, Hrsg. (2005). Wegweisende Schriften der westlichen Mathematik 1640-1940. Sonst. ISBN 9780444508713.van Heijenoort, Jean (1967). „Gödel's Theorem". In Edwards, Paul (Hrsg.), Encyclopedia of Philosophy, Bd. 3, Macmillan, S. 348–357.Hellman, Geoffrey (1981). „Wie man einen Frege-Russell Gödel macht: Gödels Unvollständigkeitssätze und Logik“. Noûs, 15 (4 – Sonderausgabe zur Philosophie der Mathematik), 451–468. doi:10.2307/2214847. ISSN 0029-4624. JSTOR 2214847. title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=No%C3%BBs&rft.atitle=H ow+to+G%C3%B6del+a+Frege-Russell%3A+G%C3%B6del%27s+Incompleteness+Theorems+and+Logicism&rft.volume=15&rft.issue=4+-+Special+Issue+on+Philo sophy+of+Mathematics&rft.pages=451-468&rft.date=1981&rft.issn=0029-4624&rft_id=https%3A%2F%2Forg%2Fstable%2F2214847%23id-name%3DJ STOR&rft_id=info%3Adoi%2F10.2307%2F2214847&rft.aulast=Hellman&rft.aufirst=Geoffrey&rfr_id=info%3Asid%2Fen.</span></li>
Hilbert, David (1900). " to="" translation="" which="">
Hirzel, Martin (2000). „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.“ Diese Veröffentlichung enthält eine englische Übersetzung von Gödels Originalarbeit, archiviert am 16. September 2004.
Kikuchi, Makoto; Tanaka, Kazuyuki (Juli 1994). „Zur Formalisierung modelltheoretischer Beweise von Gödels Theoremen“. Notre Dame Journal of Formal Logic, 35 (3), 403–412. doi:10.1305/ndjfl/1040511346. MR 1326122.Kleene, S. C. (1943). „Rekursive Prädikate und Quantoren". Transaktionen der American Mathematical Society, 53 (1), 41–73. doi:10.1090/S0002-9947-1943-0007371-8.Raatikainen, Panu (2020). „Gödels Unvollständigkeitssätze“. Stanford Encyclopedia of Philosophy. Abgerufen am 7. November 2022.Raatikainen, Panu (2005). "Zur philosophischen Relevanz von Gödels Unvollständigkeitssätzen". Revue Internationale de Philosophie, 59 (4), 513–534. doi:10.3917/rip.234.0513. S2CID 52083793. title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Revue+Internationale+de+Philosophie&r ft.atitle=Über+die+philosophische+Relevanz+von+G%C3%B6del%27s+Unvollständigkeit+Theoreme&rft.volume=59&rft.issue=4&rft.pages=513-534&rft.date=2005& ;rft_id=info%3Adoi%2F10.3917%2Frip.234.0513&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A52083793%23id-name%3DS2CID&rft.aulast=Raatikainen& amp;rft.aufirst=Panu&rft_id=https%3A%2F%2Finfo%2Frevue-internationale-de-philosophie-2005-4-page-513.htm&rfr_id=info%3Asid%2Fen.</span></li>
Rosser, John Barkley (1936). ">Journal of Symbolic Logic, Bd. 1 (1936), S. 87–91. Nachdruck in Martin Davis (1965), The Undecidable (loc. cit.), S. 230–235.
Rosser, John Barkley (1939). „Eine informelle Darstellung der Beweise des Satzes von Gödel und des Satzes der Kirche“. Ursprünglich veröffentlicht im Journal of Symbolic Logic, Bd. 4 (1939), S. 53–60. Nachdruck in Martin Davis (1965), The Undecidable (loc. cit.), S. 223–230.
Smoryński, C. (1977). „Die Unvollständigkeitssätze“. In Jon Barwise (Hrsg.), Handbook of Mathematical Logic. Amsterdam: North-Holland Publishing Co., S. 821–866. ISBN 978-0-444-86388-1.
Willard, Dan E. (2001). „Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles". Journal of Symbolic Logic, 66 (2), 536–596. doi:10.2307/2695030. JSTOR 2695030.
Zach, Richard (2003). „Die Praxis des Finitismus: Epsilon-Kalkül und Konsistenzbeweise in Hilberts Programm“ (PDF). Synthese, 137 (1), Springer Science and Business Media LLC, 211–259. arXiv:math/0102189. doi:10.1023/a:1026247421383. ISSN 0039-7857. S2CID 16657040.
Zach, Richard (2005). „Kurt Gödel, Aufsatz über die Unvollständigkeitssätze (1931)". In Grattan-Guinness, Ivor (Hrsg.), Landmark Writings in Western Mathematics 1640-1940. Elsevier, S. 917–925. doi:10.1016/b978-044450871-3/50152-2. ISBN 9780444508713.
Bücher zu den Theoremen
Berto, Francesco (2010). Da ist etwas an Gödel: Der vollständige Leitfaden zum Unvollständigkeitssatz. John Wiley und Söhne.

Domeisen, Norbert (1990). Logik der Antinomien. Bern: Peter Lang. 142 Seiten. ISBN 3-261-04214-1. Zbl 0724.03003.
Franzén, Torkel (2005). Gödels Theorem: Ein unvollständiger Leitfaden zu seiner Verwendung und seinem Missbrauch. Wellesley, MA: A. K. Peters. ISBN 1-56881-238-8. MR 2146326.Smith, Peter (2007). An Introduction to Gödel's Theorems. Cambridge, Großbritannien: Cambridge University Press. ISBN 978-0-521-67453-9. MR 2384958.

Shankar, N. (1994). Metamathematik, Maschinen und Gödels Beweis. Cambridge Tracts in Theoretical Computer Science, Bd. 38. Cambridge: Cambridge University Press. ISBN 0-521-58533-3.

Smullyan, Raymond. 1987. Für immer unentschlossen. ISBN 0192801414. Diese Arbeit präsentiert Rätsel, die auf der Unentscheidbarkeit in formalen Systemen basieren.

Smullyan, Raymond. 1992. Gödels Unvollständigkeitssätze. Oxford University Press. ISBN 0195046722.

Smullyan, Raymond. 1994. Diagonalisierung und Selbstreferenz. Oxford University Press. MR 1318913. ISBN 0198534507.

Smullyan, Raymond. 2013. Das Gödelsche Rätselbuch: Rätsel, Paradoxien und Beweise. Kuriergesellschaft. ISBN 978-0-486-49705-1.

Wang, Hao (1996). Eine logische Reise: Von Gödel zur Philosophie. MIT Press. ISBN 0-262-23189-1. HERR 1433803.

Verschiedene Referenzen

Berto, Francesco (2009). „Das Gödel-Paradoxon und Wittgensteins Gründe.“ Philosophia Mathematica, Serie III, Nr. 17.

Dawson, John W. Jr. (1996). Logische Dilemmata: Das Leben und Werk von Kurt Gödel. Taylor & Franziskus. ISBN 978-1-56881-025-6.

Dawson, John W. Jr. (1997). Logische Dilemmata: Das Leben und Werk von Kurt Gödel. Wellesley, Massachusetts: A. K. Peters. ISBN 978-1-56881-256-4. OCLC 36104240.

Goldstein, Rebecca. 2005. Unvollständigkeit: Der Beweis und das Paradoxon von Kurt Gödel. W. W. Norton & Unternehmen. ISBN 0-393-05169-2.
Floyd, Juliet und Hilary Putnam (2000). „Eine Anmerkung zu Wittgensteins ‚berüchtigtem Absatz‘ über das Gödel-Theorem.“ The Journal of Philosophy, 97 (11): 624–632. doi:10.2307/2678455. ISSN 0022-362X. JSTOR 2678455.

Harrison, J. (2009). Handbuch für praktische Logik und automatisiertes Denken. Cambridge: Cambridge University Press. ISBN 978-0521899574.

Hilbert, David und Paul Bernays. Grundlagen der Mathematik. Springer-Verlag.

Hopcroft, John E. und Jeffrey Ullman (1979). Einführung in die Automatentheorie, Sprachen und Berechnung. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-02988-X.

Hofstadter, Douglas R. (2007) [ursprünglich 2003]. „Kapitel 12. Über die Abwärtskausalität.“ In I Am a Strange Loop. Grundlegende Bücher. ISBN 978-0-465-03078-1.

Jones, James P. (1980). „Unentscheidbare diophantische Gleichungen.“ Bulletin der American Mathematical Society, §56§ (2): 859–862. doi:10.1090/S0273-0979-1980-14832-6.

Kleene, Stephen Cole (1967). „Mathematische Logik.“ Natur, 216 (5111): 201. Bibcode:1967Natur.216..201G. doi:10.1038/216201b0. Nachdruck von Dover, 2002. ISBN 0-486-42533-9.

O'Connor, Russell (2005). „Wesentliche Unvollständigkeit der von Coq verifizierten Arithmetik.“ In Theorem Proving in Higher Order Logics, Lecture Notes in Computer Science, Bd. 3603, S. 245–260. arXiv:cs/0505034. doi:10.1007/11541868_16. ISBN 978-3-540-28372-0. S2CID 15610367.

Paulson, Lawrence (2014). „Ein maschinengestützter Beweis von Gödels Unvollständigkeitssätzen für die Theorie erblich endlicher Mengen.“ Review of Symbolic Logic, 7 (3): 484–498. arXiv:2104.14260. doi:10.1017/S1755020314000112. S2CID 13913592.

Priest, Graham (1984). „Logik des Paradoxons revisited.“ Journal of Philosophical Logic, 13 (2): 153–179. doi:10.1007/BF00453020.

Priester, Graham. (2004). „Wittgensteins Bemerkungen zum Gödelschen Theorem.“ In M. Kölbel (Hrsg.), Wittgenstein's Lasting Significance (S. 207–227). Psychologiepresse. ISBN 978-1-134-40617-3.
Putnam, Hilary. (1960). „Geister und Maschinen.“ In S. Hook (Hrsg.), Dimensions of Mind: A Symposium. New York University Press.Dialectica, 57(3), 279–313. doi:10.1111/j.1746-8361.2003.tb00272.x.Israel Journal of Mathematics, 18(3), 243–256. doi:10.1007/BF02757281. MR 0357114.Geist, 111(444), 817–32. doi:10.1093/mind/111.444.817.
Shoenfield, Joseph R. (1967). Mathematische Logik. Association for Symbolic Logic (veröffentlicht 2001), Natick, MA. ISBN 978-1-56881-135-2.

Tourlakis, George. (2003). Vorlesungen in Logik und Mengenlehre, Band 1, Mathematische Logik. Cambridge University Press. ISBN 978-0-521-75373-9.

Wigderson, Avi. (2010). „Die Gödel-Phänomene in der Mathematik: Eine moderne Sichtweise“ (PDF). In Kurt Gödel und die Grundlagen der Mathematik: Horizonte der Wahrheit. Cambridge University Press.Philosophy of Logic (Band 5 des Handbook of the Philosophy of Science, S. 411–447). Elsevier, Amsterdam. arXiv:math/0508572. doi:10.1016/b978-044451541-4/50014-2. ISBN 978-0-444-51541-4 OCLC 162131413. S2CID 291599.
Godels Unvollständigkeitssätze zu In Our Time bei der BBC

Parakonsistente Logik § Arithmetik und Gödels TheoremEintrag in der Stanford Encyclopedia of Philosophy.

Weltweit kürzeste Erklärung des Satzes von Gödel am Beispiel einer Druckmaschine.

"Gödel-Unvollständigkeitssatz", Encyclopedia of Mathematics, EMS Press, 2001 [1994]Quelle: TORIma Akademie Archive

Gödels Unvollständigkeitssätze (Gödel's incompleteness theorems)