Gödels Unvollständigkeitssätze – Panu Raatikainen

Quelle: Gödel’s Incompleteness Theorems (Stanford Encyclopedia of Philosophy)

Gödels zwei Unvollständigkeitssätze gehören zu den wichtigsten Ergebnissen der modernen Logik und haben tiefgreifende Auswirkungen auf verschiedene Themenbereiche. Sie befassen sich mit den Grenzen der Beweisbarkeit in formalen axiomatischen Theorien. Der erste Unvollständigkeitssatz besagt, dass es in jedem konsistenten formalen System F, in dem eine bestimmte Menge an Arithmetik durchgeführt werden kann, Aussagen der Sprache von F gibt, die in F weder bewiesen noch widerlegt werden können. Nach dem zweiten Unvollständigkeitssatz kann ein solches formales System nicht beweisen, dass das System selbst konsistent ist (vorausgesetzt, es ist tatsächlich konsistent). Diese Ergebnisse hatten einen großen Einfluss auf die Philosophie der Mathematik und der Logik. Es gab Versuche, die Ergebnisse auch in anderen Bereichen der Philosophie, wie beispielsweise der Philosophie des Geistes, anzuwenden, aber diese Anwendungsversuche sind umstrittener. Der vorliegende Eintrag gibt einen Überblick über die beiden Unvollständigkeitssätze und verschiedene damit zusammenhängende Fragen. (Siehe auch den Eintrag zu Kurt Gödel für eine Diskussion der Unvollständigkeitssätze, die sie in einen breiteren Kontext seiner mathematischen und philosophischen Arbeit stellt.)

1. Einführung

1.1 Überblick

Gödels Unvollständigkeitssätze gehören zu den wichtigsten Ergebnissen der modernen Logik. Diese Entdeckungen revolutionierten das Verständnis von Mathematik und Logik und hatten dramatische Auswirkungen auf die Philosophie der Mathematik. Es gab auch Versuche, sie in anderen Bereichen der Philosophie anzuwenden, aber die Legitimität vieler solcher Anwendungen ist viel umstrittener.

Um Gödels Sätze zu verstehen, muss man zunächst die dafür wesentlichen Schlüsselbegriffe wie „formales System”, „Konsistenz” und „Vollständigkeit” erklären. Grob gesagt ist ein formales System ein System von Axiomen, das mit Inferenzregeln ausgestattet ist, die es ermöglichen, neue Sätze zu generieren. Die Menge der Axiome muss endlich oder zumindest entscheidbar sein, d. h., es muss einen Algorithmus (eine effektive Methode) geben, mit dem man mechanisch entscheiden kann, ob eine bestimmte Aussage ein Axiom ist oder nicht. Wenn diese Bedingung erfüllt ist, wird die Theorie als „rekursiv axiomatisierbar” oder einfach als „axiomatisierbar” bezeichnet. Die Schlussregeln (eines formalen Systems) sind ebenfalls effektive Operationen, sodass immer mechanisch entschieden werden kann, ob eine legitime Anwendung einer Schlussregel vorliegt. Folglich ist es auch möglich, für jede gegebene endliche Folge von Formeln zu entscheiden, ob sie eine echte Ableitung oder einen Beweis im System darstellt – unter Berücksichtigung der Axiome und Schlussregeln des Systems.

Ein formales System ist vollständig, wenn für jede Aussage der Sprache des Systems entweder die Aussage selbst oder ihre Negation im System abgeleitet (d. h. bewiesen) werden kann. Ein formales System ist konsistent, wenn es keine Aussage gibt, die sowohl in ihrer Form als auch in ihrer Negation im System abgeleitet werden kann. In diesem Zusammenhang sind nur konsistente Systeme von Interesse, denn es ist eine elementare Tatsache der Logik, dass in einem inkonsistenten formalen System jede Aussage ableitbar ist und ein solches System folglich trivial vollständig ist.

Gödel stellte zwei verschiedene, aber miteinander verbundene Unvollständigkeitssätze auf, die üblicherweise als erster Unvollständigkeitssatz und zweiter Unvollständigkeitssatz bezeichnet werden. Der Begriff „Gödels Theorem” wird manchmal verwendet, um die Verbindung dieser beiden Sätze zu bezeichnen, kann sich aber auch auf jeden einzelnen Satz beziehen – in der Regel auf den ersten. Unter Berücksichtigung einer Verbesserung durch J. Barkley Rosser aus dem Jahr 1936 lässt sich der erste Satz grob wie folgt formulieren:

Erster Unvollständigkeitssatz Jedes konsistente formale System F, innerhalb dessen eine bestimmte Menge elementarer Arithmetik durchgeführt werden kann, ist unvollständig, d. h., es gibt Aussagen in der Sprache von F, die in F weder bewiesen noch widerlegt werden können.

Gödels Theorem behauptet nicht nur, dass solche Aussagen existieren: Die Methode von Gödels Beweis erzeugt explizit einen bestimmten Satz, der in F weder beweisbar noch widerlegbar ist; die „unentscheidbare” Aussage lässt sich mechanisch aus einer Spezifikation von F ableiten. Der betreffende Satz ist eine relativ einfache Aussage der Zahlentheorie, ein rein universeller arithmetischer Satz.

Ein häufiges Missverständnis besteht darin, Gödels erstes Theorem so zu interpretieren, dass es zeigt, dass es Wahrheiten gibt, die nicht bewiesen werden können. Dies ist jedoch falsch, da sich der Unvollständigkeitssatz nicht mit Beweisbarkeit im absoluten Sinne befasst, sondern nur mit Ableitbarkeit in dem einen oder anderen bestimmten formalen System. Für jede Aussage A, die in einem bestimmten formalen System F nicht beweisbar ist, gibt es trivialerweise andere formale Systeme, in denen A beweisbar ist (man nehme A als Axiom). Andererseits gibt es das äußerst leistungsfähige Standard-Axiomensystem der Zermelo-Fraenkel-Mengenlehre (bezeichnet als ZF oder, mit dem Auswahlaxiom, als ZFC; siehe den Abschnitt über die Axiome von ZFC im Eintrag zur Mengenlehre), das für die Ableitung aller gewöhnlichen Mathematik mehr als ausreichend ist. Nun gibt es nach Gödels erstem Satz arithmetische Wahrheiten, die selbst in ZFC nicht beweisbar sind. Um sie zu beweisen, wäre daher ein formales System erforderlich, das über ZFC hinausgehende Methoden beinhaltet. In diesem Sinne sind solche Wahrheiten also weder mit den heutigen „gewöhnlichen” mathematischen Methoden und Axiomen beweisbar, noch können sie auf eine Weise bewiesen werden, die Mathematiker heute als unproblematisch und schlüssig ansehen würden.

Gödels zweiter Unvollständigkeitssatz betrifft die Grenzen von Konsistenzbeweisen. Eine grobe Aussage lautet:

Zweiter Unvollständigkeitssatz Für jedes konsistente System F, innerhalb dessen eine bestimmte Menge elementarer Arithmetik durchgeführt werden kann, kann die Konsistenz von F nicht in F selbst bewiesen werden.

Im Falle des zweiten Satzes muss F etwas mehr Arithmetik enthalten als im Falle des ersten Satzes, der unter sehr schwachen Bedingungen gilt. Es ist wichtig zu beachten, dass dieses Ergebnis, wie der erste Unvollständigkeitssatz, ein Satz über formale Beweisbarkeit oder Ableitbarkeit ist (die immer relativ zu einem formalen System ist; in diesem Fall zu F selbst). Es sagt nichts darüber aus, ob für eine bestimmte Theorie T, die die Bedingungen des Satzes erfüllt, die Aussage „T ist konsistent” in dem Sinne bewiesen werden kann, dass sie durch ein schlüssiges Argument oder durch einen für Mathematiker allgemein akzeptablen Beweis als wahr erwiesen werden kann. Für viele Theorien ist dies durchaus möglich.

1.2 Einige formalisierte Theorien

Die Existenz unvollständiger Theorien ist kaum überraschend. Nehmen Sie eine beliebige Theorie, selbst eine vollständige (Beispiele siehe unten), und lassen Sie ein Axiom weg; sofern das Axiom nicht redundant ist, ist das resultierende System unvollständig. Die Unvollständigkeitssätze befassen sich jedoch mit einer viel radikaleren Art von Unvollständigkeitsphänomen. Im Gegensatz zu den oben genannten trivial unvollständigen Theorien, die leicht vervollständigt werden können, gibt es keine Möglichkeit, die relevanten Theorien zu vervollständigen; alle ihre Erweiterungen sind, soweit sie noch formale Systeme und damit axiomatisierbar sind, ebenfalls unvollständig. Sie bleiben sozusagen ewig unvollständig und können niemals vervollständigt werden. Sie sind „wesentlich unvollständig”.

In den ersten und losen Aussagen der oben genannten Unvollständigkeitssätze tauchte die vage Anforderung auf, dass „eine bestimmte Menge elementarer Arithmetik durchgeführt werden kann”. Es ist an der Zeit, dies zu präzisieren.

1.2.1 Arithmetische Theorien

Das schwächste Standardsystem der Arithmetik, das üblicherweise im Zusammenhang mit Unvollständigkeit und Unentscheidbarkeit betrachtet wird, ist die sogenannte Robinson-Arithmetik (benannt nach Raphael M. Robinson; siehe Tarski, Mostowski und Robinson 1953), die standardmäßig als Q bezeichnet wird. Als Axiome hat sie die folgenden sieben Annahmen:

(A1)	¬ (0 = x′)
(A2)	x′ = y′→ x = y
(A3)	¬ (x = 0) → ∃y(x = y′)
(A4)	x + 0 = x
(A5)	x + y′ = (x + y)′
(A6)	x × 0 = 0
(A7)	x × y′ = (x × y) + x

Die beabsichtigte Interpretation von „x′“ ist die Nachfolgefunktion, und offensichtlich sind „+“ und „ד die Additions- bzw. Multiplikationsfunktionen. „0“ ist die einzige Konstante und bezeichnet die Zahl Null.

Zu diesen elementaren Axiomen kommt das Axiomenschema der Induktion hinzu:

(IND)

ϕ(0) ∧ ∀x[ϕ(x) → ϕ(x′)] → ∀xϕ(x)

führt zu Peano-Arithmetik (PA) (erster Ordnung). Beachten Sie, dass PA im Gegensatz zu Q unendlich viele Axiome enthält, da alle (unendlich vielen) Instanzen des Induktionsschemas, von denen jede einer Formel ϕ(x) (mit mindestens einer freien Variablen) der Sprache entspricht, als Axiome genommen werden. Es ist jedoch eine routinemäßige mechanische Aufgabe, zu überprüfen, ob ein gegebener Satz eine Instanz dieses Schemas ist. PA wird im Allgemeinen als das Standard-System erster Ordnung der Arithmetik angesehen.

Ein weiteres natürliches und viel untersuchtes arithmetisches System, das in seiner Stärke zwischen Q und PA liegt, ist die primitive rekursive Arithmetik (PRA). Es enthält nicht nur die oben genannten Axiome von Q, die Nachfolger, Addition und Multiplikation regeln, sondern auch definierende Axiome für alle primitiven rekursiven Funktionen (siehe den Eintrag zu rekursiven Funktionen), und die Anwendung des Induktionsschemas ist auf quantorenfreie Formeln beschränkt (d. h. ϕ(x) darf keine (unbegrenzten) Quantoren enthalten).

Im Wesentlichen erhält man jedoch dasselbe System, wenn man nur die Axiome von Q und das Induktionsschema verwendet, das grob gesagt auf rein existenzielle Formeln beschränkt ist (in der Fachsprache \( \sum_{1}^{0} \)-Formeln; siehe unten) (dies wurde erstmals von Parsons 1970 gezeigt). Darüber hinaus kann gezeigt werden (Paris und Kirby 1978), dass die \( \sum_{1}^{0} \)-Induktion äquivalent zum Induktionsschema ist, das auf (grob gesagt) rein universelle Formeln (\( \Pi_{1}^{0} \)-Formeln) beschränkt ist. PRA kann auch als „logikfreier” Gleichungsausdruck formuliert werden. PRA oder etwas Äquivalentes reicht aus, um die Syntaxtheorie für formalisierte Theorien zu entwickeln. Es wird oft als unproblematische Hintergrundtheorie angesehen, in der verschiedene andere Systeme, deren Legitimität möglicherweise umstrittener ist, untersucht werden.

Ein viel stärkeres System als PA, das für die Grundlagen der Mathematik wichtig ist und im Folgenden immer wieder erwähnt wird, ist die Arithmetik zweiter Ordnung PA² (oft auch mit Z₂ bezeichnet). Es ist mehr als ausreichend für die Entwicklung der gesamten gewöhnlichen Analysis und Algebra. Seine Sprache ist eine zweisortige Sprache erster Ordnung (siehe den Eintrag zu Logik zweiter Ordnung und höherer Ordnung), d. h. sie enthält zwei Arten von Variablen, Zahlenvariablen x₁,x₂,… (oder x,y,z,…) und Eigenschaftsvariablen X₁,X₂,… (oder X,Y,Z,…), wobei Eigenschaften extensional verstanden werden. Als Axiome enthält sie zusätzlich zu den Grundaxiomen von PA alle Instanzen des Verstehensschemas zweiter Ordnung:

∃X∀x[Xx ↔ ϕ(x)],

wobei ϕ(x) eine beliebige Formel der Sprache von PA² sein kann, in der X nicht frei vorkommt. (Es sei erwähnt, dass PA² auch formuliert werden kann, indem man der Sprache den primitiven Begriff der Mengenmitgliedschaft (∈) hinzufügt, wobei die Variablen X, Y, Z, … explizit über Mengen laufen, und die Komprehension zweiter Ordnung als ∃X∀x[x∈X ↔ ϕ(x)] umformuliert.)

PA² ist eine sehr starke Theorie. Mit Hilfe der Interpretationsmethode (siehe unten) lässt sich zeigen, dass sie beweistheoretisch genauso stark ist wie die Zermelo-Fraenkel-Mengenlehre ZFC ohne das Potenzmengenaxiom, genannt ZFC–Pow (während die standardmäßige PA erster Ordnung beweis-theoretisch ähnlich stark ist wie ZFC ohne das Unendlichkeitsaxiom, ZFC–Inf). (Vgl. den Abschnitt über die Axiome von ZFC im Eintrag zur Mengenlehre.)

Es wird natürlich davon ausgegangen, dass unsere formalen Systeme auch mit einem System von Inferenzregeln (und möglicherweise einigen logischen Axiomen) ausgestattet sind, in der Regel einem Standardsystem der klassischen Logik (obwohl die Unvollständigkeitssätze nicht unbedingt klassische Logik voraussetzen, sondern auch für Systeme mit z. B. intuitionistischer Logik gelten). Die oben genannten Standardsysteme basieren alle auf klassischer Logik. Die Standardnotation F⊢A wird verwendet, um (auf der Metaebene) auszudrücken, dass A in F ableitbar ist, d. h., dass es einen Beweis für A in F gibt, oder, mit anderen Worten, dass A ein Theorem von F ist. Dementsprechend bedeutet F⊬A, dass A in F nicht ableitbar ist.

Zusammenfassend lässt sich sagen: Wenn im Zusammenhang mit den Unvollständigkeitssätzen gesagt wird, dass in einem System „eine bestimmte Menge elementarer Arithmetik durchgeführt werden kann”, bedeutet dies in der Regel, dass es PRA oder zumindest Q enthält. Für den ersten Unvollständigkeitssatz ist Q ausreichend; für die Standardbeweise des zweiten Satzes ist mindestens etwas wie PRA erforderlich. Es gibt eine Version des zweiten Unvollständigkeitssatzes für Q (siehe Bezboruah & Shepherdson 1976), aber es gab einige Diskussionen darüber, ob die relevante Aussage in Q wirklich als Ausdruck der Konsistenz angesehen werden kann, da Q so schwach ist (siehe Kreisel 1958; Bezboruah & Shepherdson 1976; Pudlák 1996; Franks 2009).

1.2.2 Theorien, die nicht in der Sprache der Arithmetik formuliert sind

Natürlich gibt es viele wichtige und interessante Theorien in der Mathematik, die nicht einmal in der Sprache der Arithmetik formuliert sind. Die Anwendbarkeit der Unvollständigkeitssätze kann jedoch außerhalb der Sprache der Arithmetik erster Ordnung und ihrer Erweiterungen dramatisch erweitert werden, wenn man bedenkt, dass lediglich erforderlich ist, dass schwache Theorien wie Q oder PRA in dem betreffenden System interpretiert werden können. Dies betrifft vor allem verschiedene Systeme der Mengenlehre. Beispielsweise gelten die Unvollständigkeitssätze für ZFC–Inf (d. h. ZFC ohne das Unendlichkeitsaxiom) und alle seine Erweiterungen, egal wie stark sie sind (solange sie axiomatisierbar sind).

Grob gesagt ist eine Theorie T₁ in einer anderen Theorie T₂ interpretierbar, wenn die primitiven Konzepte und der Bereich der Variablen von T₁ in T₂ definierbar sind, sodass es möglich ist, jeden Satz von T₁ in einen Satz von T₂ zu übersetzen. Man sollte solche Interpretationen nicht als etwas wie intuitive Synonymität missverstehen. Zwei Theorien können radikal unterschiedliche Themenbereiche haben und dennoch als formale Systeme ineinander interpretierbar sein. (Zur Veranschaulichung: Eine einfache Theorie der Vorfahren kann als formales System in der Arithmetik interpretiert werden; dies bedeutet natürlich nicht, dass Großmütter und dergleichen tatsächlich Zahlen sind.) Wichtig ist, dass die Interpretierbarkeit bestimmte elementare formale Eigenschaften von Theorien bewahrt, vor allem die Konsistenz: Wenn T₁ in T₂ interpretierbar ist und T₂ konsistent ist, ist T₁ ebenfalls konsistent. Und jedes System, in dem Q interpretiert werden kann, ist garantiert im Wesentlichen unvollständig. Für jede solche Theorie, in der Q interpretierbar ist, könnte die Unvollständigkeit auch direkt bewiesen werden; beispielsweise kann man in verschiedenen Theorien der Mengenlehre Formeln und Ableitungen (anstelle von Zahlen) durch Mengen, „Gödel-Mengen”, codieren und dann wie gewohnt fortfahren (siehe z. B. Fitting 2007). Für die meisten Zwecke ist es jedoch viel einfacher, die Interpretierbarkeit von Q in der betreffenden Theorie nachzuweisen.

Zusammenfassend lässt sich sagen, dass die Aussage „eine bestimmte Menge elementarer Arithmetik kann innerhalb eines Systems durchgeführt werden” entweder bedeutet, dass das System eine axiomatisierbare Erweiterung von Q ist oder dass Q darin interpretiert werden kann. (Im Fall des zweiten Unvollständigkeitssatzes (der Standardbeweise) ersetzen Sie Q durch PRA.)

1.2.3 Einige Ausnahmen: Vollständige Theorien

Andererseits sind nicht alle Theorien der Arithmetik unvollständig. Die Theorie der Addition natürlicher Zahlen ohne Multiplikation (oft als „Presburger-Arithmetik“ bezeichnet) ist beispielsweise vollständig (und entscheidbar) (Presburger 1929), ebenso wie die Theorie der Multiplikation positiver ganzer Zahlen (Skolem 1930). Diese Theorien sind jedoch sehr schwach. In jedem Fall wird jedoch mindestens eine Theorie benötigt, die sich sowohl mit Addition als auch mit Multiplikation befasst. Interessanterweise ist die natürliche Theorie erster Ordnung der Arithmetik der reellen Zahlen (mit Addition und Multiplikation), die sogenannte Theorie der reellen geschlossenen Körper (RCF), sowohl vollständig als auch entscheidbar, wie Tarski (1948) gezeigt hat; Er zeigte auch, dass die Theorie erster Ordnung der euklidischen Geometrie vollständig und entscheidbar ist. Man sollte also bedenken, dass es einige nicht triviale und interessante Theorien gibt, auf die Gödels Theoreme nicht zutreffen.

1.3 Die Relevanz der Church-Turing-These

Gödel bewies ursprünglich nur die Unvollständigkeit einer bestimmten, wenn auch sehr umfassenden formalisierten Theorie P, einer Variante von Russells typentheoretischem System PM (zu Principia Mathematica siehe die Abschnitte über Paradoxien und Russells Typentheorien in den Einträgen zu Typentheorie und Principia Mathematica), sowie aller Erweiterungen von P mit derselben Sprache, deren Axiomensatz primitiv rekursiv ist. Er schlug auch vor, ohne dies jedoch zu beweisen, dass der Beweis so angepasst werden könnte, dass er auch auf die Standard-Axiomensysteme der Mengenlehre wie ZFC anwendbar wäre. Obwohl sich herausstellte, dass Gödel tatsächlich bereits ein sehr allgemeines Ergebnis erzielt hatte, war zu diesem Zeitpunkt noch unklar, wie allgemein dieses Ergebnis tatsächlich war (siehe auch Abschnitt 5).

Was noch fehlte, war eine Analyse des intuitiven Begriffs der Entscheidbarkeit, der für die Charakterisierung des Begriffs eines beliebigen formalen Systems erforderlich ist. Es sei daran erinnert, dass die Menge der Axiome und die Beweisrelation eines formalisierten Systems entscheidbar sein müssen. Mathematiker und Logiker haben seit der Antike implizit den intuitiven Begriff einer Entscheidungsmethode verwendet, und solange man nach einer positiven Lösung fragte, reichte es aus, eine konkrete Methode vorzustellen, die allen intuitiv als mechanische Methode erschien. Für allgemeine limitierende Ergebnisse, wie die allgemeinen Unvollständigkeitssätze oder die Unentscheidbarkeitsergebnisse (siehe 4.2), wäre jedoch eine präzise mathematische Erklärung des Begriffs erforderlich. Anstelle von entscheidbaren Mengen oder Eigenschaften betrachtet man oft effektive oder berechenbare Funktionen oder Operationen, aber tatsächlich sind dies nur zwei Seiten derselben Medaille – die Aussage über die eine lässt sich leicht in eine Aussage über die andere umschreiben.

Gödel (1934), Alonzo Church (1936a, b) und Alan Turing (1936–7) kamen unabhängig voneinander zu unterschiedlichen Vorschlägen für eine exakte mathematische Definition berechenbarer Funktionen und folglich auch entscheidbarer Mengen (von Zahlen). Diese Vorschläge erwiesen sich jedoch alle als gleichwertig. Turings sorgfältige konzeptionelle Analyse, bei der er fiktive und abstrakte Rechenmaschinen verwendete (heute üblicherweise als „Turing-Maschinen” bezeichnet; siehe den Eintrag zu Turing-Maschinen), war besonders wichtig, wie Gödel selbst betonte (siehe z. B. Gödel 1963). Die Gleichsetzung des intuitiven Begriffs mit einigen dieser mathematischen Erklärungen wird oft als „Church-Turing-These” bezeichnet. Der Begriff „rekursive Funktion” hat aus historischen Gründen in der logischen Literatur Vorrang. Folglich werden entscheidbare Mengen oft als „rekursive Mengen” bezeichnet. (Siehe die Einträge zu Berechenbarkeit, rekursiven Funktionen und der Church-Turing-These.)

Für ein richtiges Verständnis der Ergebnisse zur Unvollständigkeit und Unentscheidbarkeit ist es wichtig, den Unterschied zwischen den beiden Schlüsselbegriffen in Bezug auf Mengen zu verstehen. Erstens kann es eine mechanische Methode geben, die entscheidet, ob eine bestimmte Zahl zu der betreffenden Menge gehört oder nicht (in diesem Fall wird die Menge als „entscheidbar” oder „rekursiv” bezeichnet), und zweitens kann es eine mechanische Methode geben, die die Elemente der Menge Nummer für Nummer generiert oder auflistet. Im letzteren Fall wird die Menge als „rekursiv aufzählbar” (r.e.) bezeichnet, d. h. sie kann effektiv generiert werden oder ist „halbentscheidbar”. Es ist ein grundlegendes Ergebnis der Theorie der Berechenbarkeit (oder „Theorie der rekursiven Funktionen”), dass es halbentscheidbare Mengen gibt, also Mengen, die effektiv erzeugt werden können (d. h. rekursiv aufzählbar sind), aber nicht entscheidbar sind (d. h. nicht rekursiv sind). Tatsächlich ist dies auf einer sehr abstrakten Ebene der Kern des ersten Unvollständigkeitssatzes. Wenn jedoch sowohl eine Menge als auch ihre Komplementärmenge rekursiv aufzählbar sind, ist die Menge rekursiv, d. h. entscheidbar.

2. Der erste Unvollständigkeitssatz

In diesem Abschnitt werden die Grundzüge des Beweises des ersten Unvollständigkeitssatzes skizziert. Leser, die an weiteren Details interessiert sind, können die Ergänzungen (Gödel-Nummerierung und Das Diagonalisierungslemma) konsultieren.

2.1 Vorbemerkungen

Der formale Begriff („Ziffer“), der kanonisch die natürliche Zahl \( {n} \) bezeichnet, wird mit \( \overline{n} \) abgekürzt. In der hier verwendeten Standardsprache der Arithmetik wird die Zahl \( {n} \) durch den Begriff 0′⋯′ bezeichnet, wobei das Nachfolgersymbol „′“ n-mal wiederholt wird. Das heißt, die Ziffern, die 1, 2, 3, … bezeichnen, sind 0′,0′′,0′′′,… und werden mit \( \overline{1}, \overline{2}, \overline{3} \) … abgekürzt.

In seinem ursprünglichen Beweis verwendete Gödel seinen spezifischen Begriff der ω-Konsistenz, und für bestimmte Zwecke ist es nach wie vor zweckmäßig, Gödels ursprünglichem Ansatz zu folgen. Eine formalisierte Theorie F ist ω-konsistent, wenn es nicht der Fall ist, dass für eine bestimmte Formel A(x) sowohl F⊢¬A(\( \overline{n} \)) für alle n als auch F ⊢ ∃xA(x) gilt. Dies impliziert natürlich normale Konsistenz und folgt aus der Annahme, dass die natürlichen Zahlen die Axiome von F erfüllen.

Tatsächlich reicht hier ein einfacher Sonderfall der ω-Konsistenz aus; nämlich wird die Annahme nur in Bezug auf das benötigt, was Logiker als \( \sum_{1}^{0} \)-Formeln bezeichnen; Dies sind, grob gesagt, die rein existentiellen Formeln; genauer gesagt, Formeln der Form ∃x₁∃x₂…∃x_nA, wobei A keine unbegrenzten Quantoren enthält (A kann begrenzte Universalquantoren ∀x < t und begrenzte Existenzialquantoren ∃x < t enthalten). Diese eingeschränkte ω-Konsistenz wird als 1-Konsistenz bezeichnet.

ω-Konsistenz und 1-Konsistenz sind rein syntaktische Begriffe. Wenn die Verwendung der Begriffe Wahrheit und Falschheit zulässig ist, kann die Annahme der 1-Konsistenz intuitiv einfach als die Anforderung ausgedrückt werden, dass das betreffende formale System keine falschen \( \sum_{1}^{0} \)-Sätze beweist (d. h., das System ist zumindest im Fall solcher Sätze fundiert). Von nun an wird davon ausgegangen, dass die betrachteten formalisierten Systeme Q enthalten und mindestens 1-konsistent sind, sofern nicht anders angegeben.

2.2 Repräsentierbarkeit

Gödels Beweis erfordert auch den Begriff der Darstellbarkeit von Mengen und Relationen in einem formalen System F. Genauer gesagt sind zwei miteinander verbundene Begriffe erforderlich.

Eine Menge S von natürlichen Zahlen ist in F stark darstellbar, wenn es eine Formel A(x) der Sprache von F mit einer freien Variablen x gibt, sodass für jede natürliche Zahl n gilt:

n ∈ S ⇒ F⊢A(\( \overline{n} \));
n ∉ S ⇒ F⊢¬A(\( \overline{n} \)),

Eine Menge S natürlicher Zahlen ist in F schwach darstellbar, wenn es eine Formel A(x) der Sprache von F gibt, sodass für jede natürliche Zahl n gilt:

n ∈ S ⇔ F ⊢ A(\( \overline{n} \)).

Es ist offensichtlich, wie all diese Begriffe auf Mehrplatzrelationen verallgemeinert werden können. Es gibt auch verwandte Begriffe der Darstellbarkeit für Funktionen. Wie uns insbesondere die Unvollständigkeitsergebnisse lehren, gibt es Mengen, die nur schwach, aber nicht stark darstellbar sind (das wichtigste Beispiel hierfür ist die Menge der im System beweisbaren Aussagen).

[Warnung: Hier variiert die Terminologie in der Literatur stark: „stark repräsentieren” wird manchmal auch als „repräsentieren”, „numerisch ausdrücken”, „bi-numerieren”, „definieren” oder „stark definieren” bezeichnet; „schwach repräsentieren“ wird wiederum auch ausgedrückt durch z. B. „repräsentieren“, „definieren“, „schwach definieren“ oder „numerieren“. Man sollte hier vorsichtig sein und sich auf die relevanten Definitionen konzentrieren und sich nicht von den Begriffen irreführen lassen.]

Bei beiden Arten der Darstellbarkeit (schwach und stark) gibt es immer eine einfache existenzielle \( \sum_{1}^{0} \)-Formel, die (schwach oder stark) die betreffende Menge darstellt, und normalerweise wird eine solche Formel verwendet, um S darzustellen.

Obwohl diese Begriffe relativ zum formalen System sind, hat sich herausgestellt, dass starke und schwache Darstellbarkeit äußerst stabil sind. Ganz unabhängig vom gewählten formalen System sind genau die entscheidbaren oder rekursiven Mengen (Relationen) stark darstellbar, und genau die halbentscheidbaren oder rekursiv aufzählbaren Mengen (Relationen) sind schwach darstellbar. Dies gilt für alle formalisierten Systeme, die die Robinson-Arithmetik Q enthalten, von der Robinson-Arithmetik selbst bis hin zu den stärksten Axiomensystemen der Mengenlehre wie ZFC und darüber hinaus (sofern sie (rekursiv) axiomatisierbar sind). Anstelle des Begriffs der „Darstellbarkeit” verfolgte Gödel einen anderen Ansatz, indem er von Mengen sprach, die „in einem formalen System F entscheidbar” („entscheidungsdefinit”) sind. Wenn die Beweise von F systematisch generiert werden, wird für jede gegebene Zahl n schließlich bestimmt, ob sie zu S gehört oder nicht – vorausgesetzt, dass S in F stark darstellbar ist.

Zusammenfassend haben wir:

Das Repräsentabilitätstheorem
In jedem konsistenten formalen System, das Q enthält:

1. Eine Menge (oder Relation) ist genau dann stark darstellbar, wenn sie rekursiv ist.
2. Eine Menge (oder Relation) ist genau dann schwach darstellbar, wenn sie rekursiv abzählbar ist.

2.3 Arithmetisierung der formalen Sprache

Der nächste wesentliche Schritt in Gödels Beweis besteht darin, die Sprache eines formalen Systems, die immer genau definiert ist (das gehört zum Wesen eines formalen Systems), zu nehmen und eine bestimmte Entsprechung zwischen den Ausdrücken dieser Sprache und dem System der natürlichen Zahlen festzulegen – eine Kodierung, „Arithmetisierung“ oder „Gödel-Nummerierung“ der Sprache. Es gibt viele Möglichkeiten, dies zu erreichen, und die Details spielen keine Rolle (weitere Einzelheiten zu einem gängigen Ansatz finden Sie im ergänzenden Dokument „Gödel-Nummerierung“). Der wesentliche Punkt ist, dass die gewählte Zuordnung effektiv ist: Es ist immer möglich, rein mechanisch von einem Ausdruck zu seiner Codenummer und von einer Nummer zum entsprechenden Ausdruck zu gelangen. Heute, wo die meisten von uns mit Computern vertraut sind und wissen, dass so viele Dinge durch Nullen und Einsen codiert werden können, ist die Möglichkeit einer solchen Arithmetisierung kaum überraschend.

Grob gesagt geht man wie folgt vor: Zunächst werden die primitiven Symbole der Sprache mit eindeutigen natürlichen Zahlen, „Symbolnummern“, gepaart. Dann genügt ein wenig Zahlentheorie, um Folgen von Zahlen durch einzelne Zahlen zu codieren. Folglich wird jeder wohlgeformten Formel als Folge primitiver Symbole eine eindeutige Zahl zugewiesen. Schließlich werden Ableitungen oder Beweise des Systems, die Folgen von Formeln sind, arithmetisiert und ebenfalls bestimmten Zahlen zugewiesen. Ein solcher Code, die „Gödel-Zahl” einer Formel A, wird als ┌A┐ bezeichnet, ebenso wie Ableitungen.

Auf diese Weise spiegeln sich syntaktische Eigenschaften, Relationen und Operationen in der Arithmetik wider: So ist beispielsweise neg(x) die arithmetische Funktion, die die Gödel-Zahl einer Formel auf die Gödel-Zahl ihrer Negation abbildet; mit anderen Worten: neg(┌A┐) = (┌¬A┐); Ebenso ist impl(x,y) die Funktion, die die Gödel-Zahlen eines Formelpaares auf die Gödel-Zahl der Implikation der Formeln abbildet: impl(┌A┐,┌B┐) =┌A → B┐; und so weiter. Es gibt eine arithmetische Formel, nennen wir sie Fmla(x), die für n genau dann wahr ist, wenn n eine Gödel-Zahl einer wohlgeformten Formel des Systems ist. Es gibt auch eine arithmetische Formel M(x,y,z), die genau dann wahr ist, wenn man eine gültige Anwendung der Inferenzregel modus ponens für einige Formeln A und B mit x =┌A┐, y =┌A → B┐ und z =┌B┐ hat; usw. Auf diese Weise können alle syntaktischen Eigenschaften und Operationen auf der Ebene der Zahlen simuliert werden, und darüber hinaus sind sie in allen Theorien, die Q enthalten, stark repräsentierbar.

Da es (gemäß der Definition formaler Systeme) entscheidbar ist, ob eine bestimmte Folge von Formeln einen Beweis für einen bestimmten Satz gemäß den Regeln des gewählten formalen Systems F darstellt, kann die binäre Relation „x ist (die Gödel-Zahl) eines Beweises für die Formel (mit der Gödel-Zahl) y“ in allen Systemen, die Q enthalten, und somit insbesondere in F, stark repräsentiert werden. Bezeichnen wir die Formel, die diese Relation in F selbst stark repräsentiert, mit Prf_F(x,y). Die Eigenschaft, in F beweisbar zu sein, kann dann als ∃xPrf_F(x,y) definiert werden. Wir kürzen dieses formalisierte Beweisbarkeitsprädikat mit Prov_F(x) ab. Daraus folgt, dass die letztere Eigenschaft schwach repräsentierbar ist (wenn auch, wie sich herausstellt, nicht stark):

F ⊢ A ⇒ F ⊢ Prov_F(┌A┐).

Es ist immer möglich, das Beweisbarkeitsprädikat Prov_F(x) als \( \sum_{1}^{0} \)-Formel zu wählen.

2.4 Diagonalisierung oder „Selbstreferenz“

Der nächste und vielleicht etwas überraschende Bestandteil von Gödels Beweis ist das folgende wichtige Lemma (wir nehmen weiterhin an, dass F ein formales System ist, das Q enthält):

Das Diagonalisierungslemma:
Sei A(x) eine beliebige Formel der Sprache von F mit nur einer freien Variablen. Dann kann ein Satz D mechanisch so konstruiert werden, dass

F ⊢ D ↔ A(┌D┐).

(Für eine Skizze des Beweises siehe Ergänzung: Das Diagonalisierungslemma)

In der Literatur wird dieses Lemma manchmal auch als „selbstreferentielles Lemma” oder „Fixpunkt-Lemma” bezeichnet. Es hat viele wichtige Anwendungen, die über die Unvollständigkeitssätze hinausgehen.

Es wird oft gesagt, dass bei einer durch A(x) bezeichneten Eigenschaft der Satz D ein selbstreferenzieller Satz ist, der „über sich selbst aussagt”, dass er die Eigenschaft A hat. Solche Redewendungen mögen heuristisch nützlich sein, aber sie sind auch leicht irreführend und suggerieren zu viel. Beachten Sie beispielsweise, dass das Lemma nur eine (beweisbare) materielle Äquivalenz zwischen D und A(┌D┐) liefert (die besagt, dass beide Seiten denselben Wahrheitswert haben müssen) und keine Gleichheit der Bedeutung behauptet. Insbesondere sind D und A(┌D┐) keineswegs identisch – ebenso wenig wie ┌D┐ und ┌A(┌D┐)┐.

2.5 Der erste Unvollständigkeitssatz – Beweis abgeschlossen

Um den Beweis zu vervollständigen, wird das Diagonalisierungslemma auf das negierte Beweisbarkeitsprädikat ¬Prov_F(x) angewendet: Dies ergibt einen Satz G_F, sodass

(G) F ⊢ GF ↔ ¬Prov_F(┌GF┐).

Somit lässt sich auch innerhalb von F zeigen, dass G_F genau dann wahr ist, wenn es in F nicht beweisbar ist.

Es ist nicht schwer zu zeigen, dass G_F in F weder beweisbar noch widerlegbar ist, wenn F nur 1-konsistent ist.

Für die erste Hälfte nehmen wir an, dass G_F beweisbar wäre. Dann würde F aufgrund der schwachen Darstellbarkeit von Beweisbarkeit in F durch Prov_F(x) auch Prov_F(┌G_F┐) beweisen. Da F jedoch tatsächlich auch die Äquivalenz (G) beweist, d. h. F ⊢ G_F ↔ ¬ Prov_F(┌G_F┐), würde F dann auch ¬G_F beweisen. Dies würde jedoch bedeuten, dass F inkonsistent ist. Zusammenfassend lässt sich sagen: Wenn F konsistent ist, dann ist G_F in F nicht beweisbar. Für diese erste Hälfte reicht die Annahme der einfachen Konsistenz von F aus.

Für die zweite Hälfte muss angenommen werden, dass F 1-konsistent ist (wenn Prov_F(┌G_F┐) so gewählt wurde, dass es ein \( \sum_{1}^{0} \)-Satz ist; andernfalls ist die allgemeinere Annahme der ω-Konsistenz erforderlich).

Angenommen, F ⊢¬ G_F. Dann kann F G_F nicht beweisen, da F sonst einfach inkonsistent wäre. Daher ist keine natürliche Zahl n die Gödel-Zahl eines Beweises von G_F, und da die Beweisrelation stark darstellbar ist, gilt für alle n: F ⊢¬ Prf_F(\( \overline{n} \),┌G_F┐). Wenn auch F ⊢ ∃xPrf_F(x,┌GF┐) gilt, ist F entgegen der Annahme nicht 1-konsistent. Daher beweist F nicht ∃xPrf_F(x,┌G_F┐), mit anderen Worten, gemäß der Definition von Prov_F(x) beweist F nicht Prov_F(┌G_F┐). Aufgrund der Schlüsseläquivalenz (G) beweist F auch nicht ¬G_F.

Gödels erster Unvollständigkeitssatz
Angenommen, F ist ein formalisiertes System, das die Robinson-Arithmetik Q enthält. Dann kann ein Satz G_F der Sprache von F mechanisch aus F so konstruiert werden, dass:

i. Wenn F konsistent ist, dann gilt F ⊬ G_F
ii . Wenn F 1-konsistent ist, dann gilt F ⊬¬ G_F.

Eine solche unabhängige oder „unentscheidbare“ (d. h. in F weder beweisbare noch widerlegbare) Aussage G_F in F wird oft als „Gödel-Satz“ von F bezeichnet.

Tatsächlich lässt sich unter günstigen Umständen zeigen, dass G_F wahr ist, vorausgesetzt, dass F tatsächlich konsistent ist. Dies ist beispielsweise der Fall, wenn das Beweisbarkeitsprädikat Prov_F(x) als \( \sum_{1}^{0} \)-Formel gewählt wurde: Der Gödel-Satz ist dann nachweisbar äquivalent zur universellen Formel ∀x ¬ Prf_F(x,┌GF┐). Solche Formeln können immer dann als falsch bewiesen werden, wenn sie tatsächlich falsch sind: Wenn sie falsch wären, gäbe es eine Zahl n, sodass F ⊢ Prf_F(\( \overline{n} \),┌G_F┐) (dies gilt bereits in Q). Dies würde jedoch dem Unvollständigkeitssatz widersprechen. Daher kann G_F nicht falsch sein und muss wahr sein. Aus diesem Grund wird der Gödel-Satz oft als „wahr, aber unbeweisbar” bezeichnet.

Man sollte hier nicht verwechseln: „Gödels Theorem“ ist das allgemeine Unvollständigkeitsergebnis von Gödel, das eine große Klasse formaler Systeme betrifft, während der „Gödel-Satz“ der konstruierte, formal unentscheidbare Satz ist, der von einem formalen System zum anderen variiert. Deshalb ist es wichtig, den Index F in G_F einzufügen. Außerdem sollte man die beiden unterschiedlichen Bedeutungen von „unentscheidbar“ in diesem Zusammenhang nicht verwechseln. Einerseits kann ein bestimmter Satz, wie der Gödel-Satz, in dem Sinne unentscheidbar sein, dass er unabhängig ist, d. h. in einem gewählten System weder beweisbar noch widerlegbar ist. Andererseits kann eine Theorie in dem Sinne unentscheidbar sein (siehe unten), dass es keine Entscheidungsmethode gibt, um für einen beliebigen gegebenen Satz der Sprache zu bestimmen, ob er in der Theorie ableitbar ist oder nicht (diese letztere Bedeutung von „unentscheidbar” betrifft also sozusagen eine unendliche Klasse von Aussagen).

In informellen Erklärungen des ersten Unvollständigkeitssatzes wird oft gesagt, dass der Gödel-Satz G_F „über sich selbst aussagt, dass er nicht beweisbar ist”. Solche ungenauen Aussagen sollten jedoch zumindest mit Vorsicht genossen werden. Es gibt eine Reihe von Gründen für die Schlussfolgerung, dass Gödel-Sätze zumindest im Allgemeinen nichts Wesentliches über sich selbst aussagen (Milne 2007 enthält eine sorgfältige Analyse solcher Fragen); wie bereits im Fall des Diagonalisierungslemmas erwähnt, handelt es sich hier in der Regel um reine materielle Äquivalenzen.

Rossers Verbesserung – Von ω-Konsistenz zu Konsistenz

Im Jahr 1936 gelang J. Barkley Rosser eine wichtige Verbesserung, die es ermöglicht, die etwas umständliche Annahme der ω-Konsistenz im Beweis von Gödels erstem Theorem zu umgehen. Zu diesem Zweck führte Rosser ein neues, etwas künstliches „Beweisbarkeitsprädikat” Prov^∗(x) ein, das informell wie folgt konstruiert wurde:

Es gibt y, sodass y die Gödel-Zahl eines Beweises der Formel mit der Gödel-Zahl x ist, UND es gibt kein z kleiner als y, sodass z die Gödel-Zahl eines Beweises der Negation der Formel mit der Gödel-Zahl x ist.

Etwas formeller:

Prov^∗(x) = _def∃y[PrfF(y,x) ∧ ∀z < y(¬Prf_F(z,neg(x)))],

wobei Prf_F(y,x) die zuvor beschriebene, eher standardmäßige Beweisrelation ist.

Wenn das betrachtete formale System F tatsächlich konsistent ist, ist Rossers Beweisbarkeitsprädikat koextensiv mit dem gewöhnlichen Beweisbarkeitsprädikat. Die Anwendung des Diagonalisierungslemmas auf die Negation von Rossers Beweisbarkeitsprädikat Prov^∗(x) ergibt:

Rossers Modifikation des ersten Satzes (Rosser 1936)
Sei F ein konsistentes formalisiertes System, das Q enthält. Dann gibt es einen Satz R_F der Sprache von F, sodass weder R_F noch ¬R_F in F beweisbar ist.

2.6 Unvollständigkeit und nicht standardisierte Modelle

Es ist aufschlussreich, das erste Unvollständigkeitstheorem auch aus modelltheoretischer Perspektive zu betrachten – obwohl das Theorem selbst dies in keiner Weise erfordert. Man kann nämlich zu dem Schluss kommen, dass jede Theorie F, die die Bedingungen des Satzes erfüllt, zusätzlich zu der beabsichtigten Interpretation oder dem „Standardmodell” (im Falle arithmetischer Theorien die Struktur der natürlichen Zahlen) auch nicht beabsichtigte Interpretationen oder „Nicht-Standardmodelle” besitzen muss – dass keine solche Theorie Letztere ausschließen und die beabsichtigte Interpretation eindeutig festlegen kann. Das heißt, wenn es unabhängige Aussagen wie G_F gibt, muss F sowohl Modelle haben, die G_F erfüllen, als auch Modelle, die eher ¬G_F erfüllen. Da ¬G_F äquivalent zu ∃xPrf_F(x,┌G_F┐) ist, müssen die letzteren Modelle Entitäten besitzen, die die Formel Prf_F(x,┌G_F┐) erfüllen. Und doch wissen wir (da Prf_F(x,y) die Beweisrelation stark repräsentiert), dass für jede Zahl \( \overline{n} \),F ¬Prf_F(\( \overline{n} \),┌G_F┐) beweisen kann. Daher kann keine natürliche Zahl n die Formel bezeugen. Daraus folgt, dass jedes solche nicht-standardisierte Modell zusätzlich zu den natürlichen Zahlen (Bezeichnungen der Zahlen \( \overline{n} \)) „unendliche” nicht-natürliche Zahlen nach den natürlichen Zahlen enthalten muss.

Die Untersuchung nichtstandardisierter Modelle begann nicht erst mit Gödels Ergebnissen – insbesondere Skolem war sich dieser bereits zuvor in einem anderen Zusammenhang bewusst (er hatte entdeckt, dass Theorien erster Ordnung der Mengenlehre unnatürlich kleine, nämlich abzählbare Modelle haben, in Skolem 1922; vgl. den Eintrag zu Skolems Paradoxon) –, aber der erste Unvollständigkeitssatz verdeutlicht die Existenz nichtstandardisierter Modelle im Kontext der Arithmetik, während die nichtstandardisierten Modelle den ersten Unvollständigkeitssatz verdeutlichen. Nichtstandardmodelle sind seitdem zu einem reichhaltigen Forschungsgebiet in der mathematischen Logik geworden (siehe z. B. Boolos & Jeffrey 1989: Kap. 17; Kaye 1991).

3. Der zweite Unvollständigkeitssatz

3.1 Vorbereitungen

Informell betrachtet ist die Argumentation, die zum zweiten Unvollständigkeitssatz führt, relativ einfach. Angesichts des arithmetisierten Beweisbarkeitsprädikats ist es auch einfach, eine arithmetisierte Konsistenzaussage zu formulieren: Man wählt eine offensichtlich inkonsistente Formel (in arithmetischen Theorien ist eine Standardwahl (\( \overline{0} \) = \( \overline{1} \))); bezeichnen wir sie mit ⊥; die Konsistenz des Systems (als arithmetisiertes Gegenstück) kann dann als ¬Prov_F(┌⊥┐) definiert werden. Wir kürzen diese Formel mit Cons(F) ab. Der Beweis des ersten Teils des ersten Unvollständigkeitssatzes (d. h. des oben genannten Falls (i)) kann dann vermutlich innerhalb von F formalisiert werden (in der Praxis wäre dies sicherlich kompliziert). Daraus ergibt sich:

F ⊢ Cons(F) → G_F,

wobei G_F der Gödel-Satz für F ist, der durch den ersten Satz bereitgestellt wird. Wenn Cons(F) in F beweisbar wäre, wäre dies aufgrund einfacher Logik auch für G_F der Fall. Dies würde im Widerspruch zum ersten Satz von Gödel stehen. Folglich kann Cons(F) auch nicht in F beweisbar sein.

Gödels zweiter Unvollständigkeitssatz
Angenommen, F ist ein konsistentes formalisiertes System, das elementare Arithmetik enthält. Dann gilt F ⊬ Cons(F).

An dieser Stelle sollte eine Frage von philosophischer Bedeutung erwähnt werden: In seiner jetzigen Form belegt Gödels zweiter Unvollständigkeitssatz lediglich die Unbeweisbarkeit eines einzigen Satzes, nämlich Cons(F). Aber drückt dieser Satz wirklich aus, dass F konsistent ist? (Vergleichen Sie dies mit der obigen Bemerkung, dass G_F streng genommen nicht seine eigene Unbeweisbarkeit ausdrückt.) Könnte es darüber hinaus nicht andere Sätze geben, die beweisbar sind und ebenfalls die Konsistenz von F ausdrücken?

Eine strenge Beweisführung für den zweiten Satz in einer allgemeineren Form, die alle derartigen Sätze abdeckt, hat sich jedoch als sehr kompliziert erwiesen. Der Hauptgrund dafür ist, dass im Gegensatz zum ersten Satz nicht jedes beliebige, lediglich extensional adäquate Beweisbarkeitsprädikat für die Formalisierung der Konsistenzbehauptung geeignet ist. Die Art der Darstellung macht den Unterschied. Das oben erwähnte Beweisbarkeitsprädikat von Rosser wäre beispielsweise nicht geeignet; man kann die „Konsistenz” von F in F beweisen, wenn Konsistenz in Form des Beweisbarkeitsprädikats von Rosser ausgedrückt wird. Man muss also einige weitere Bedingungen für das Beweisbarkeitsprädikat hinzufügen, damit der Beweis des zweiten Unvollständigkeitssatzes gelingen kann. In Anlehnung an Feferman (1960) ist es üblich zu sagen, dass der erste Satz und seine Verwandten extensionale Ergebnisse sind, während der zweite Satz intensional ist: Es muss möglich sein, zu denken, dass Cons(F) in gewisser Weise die Konsistenz von F ausdrückt – dass es wirklich bedeutet, dass F konsistent ist.

3.2 Ableitbarkeitsbedingungen

Der Beweis des zweiten Unvollständigkeitssatzes erfordert, dass das Prädikat der Beweisbarkeit in F eine Reihe von Bedingungen erfüllt, die in den Details des Beweises verwendet werden. Es gibt mehrere verschiedene Sätze von Bedingungen, die dafür geeignet sind.

Der erste detaillierte Beweis des zweiten Unvollständigkeitssatzes erschien in (Hilbert & Bernays 1939) (hauptsächlich verfasst von Bernays), allerdings nur für eine bestimmte Theorie, PA. Er verwendet eine eher umständliche Reihe von Bedingungen für das Prädikat der Beweisbarkeit. Dabei handelte es sich eher um technische Lemmas für die Anforderungen eines bestimmten Beweises und nicht um eine Analyse „natürlicher” Prädikate der Beweisbarkeit. Eine viel elegantere, heute als Standard geltende Liste von „Ableitungsbedingungen” wurde von Löb (1955) vorgestellt – allerdings war deren Verwendungszweck etwas anders (siehe unten).

Löbs Ableitbarkeitsbedingungen

(D1)	F⊢A ⇒ F⊢ProvF(┌A┐).
(D2)	F⊢ProvF(┌A┐) → ProvF(┌ProvF(┌A┐)┐).
(D3)	F⊢ProvF(┌A┐) ∧ ProvF(┌A→B┐) → ProvF(┌B┐).

(D1) ist lediglich eine Neuformulierung der Anforderung aus dem Beweis des ersten Satzes, dass die Beweisbarkeit schwach repräsentierbar ist. Grob gesagt verlangt (D2), dass die gesamte Beweisführung von (D1) für das Kandidat-Beweisbarkeitsprädikat Prov_F selbst innerhalb von F formalisiert werden kann. Schließlich verlangt (D3), dass das Beweisbarkeitsprädikat unter Modus Ponens abgeschlossen ist.

Wenn das arithmetisierte Beweisbarkeitsprädikat tatsächlich diese Bedingungen erfüllt, kann der zweite Satz bewiesen werden. Sei G_F erneut der Gödel-Satz für F, der durch den ersten Satz gegeben ist. Es ist nicht allzu schwierig, unter Verwendung der Ableitbarkeitsbedingungen zu zeigen, dass:

F⊢G_F ↔ Cons(F).

Dies führt unter Berücksichtigung des ersten Unvollständigkeitssatzes unmittelbar zur Unbeweisbarkeit von Cons(F).

Darüber hinaus hat Jeroslow (1973) mit einem raffinierten Trick gezeigt, dass es tatsächlich möglich ist, den zweiten Satz ohne (D3) zu beweisen. In einigen anderen Fällen (z. B. beim Beweis des Löbschen Satzes; siehe unten) und in der Beweisbarkeitslogik sind jedoch weiterhin alle drei Bedingungen erforderlich.

3.3 Fefermans alternativer Ansatz zum zweiten Theorem

Unter der Annahme, dass ein Beweisbarkeitsprädikat für eine Theorie die Ableitbarkeitsbedingungen erfüllt (oder, nach Jeroslows Trick, zumindest D1 und D2), ist es relativ einfach, den relevanten Fall des zweiten Unvollständigkeitssatzes zu beweisen. In der Praxis muss jedoch von Fall zu Fall geprüft werden, ob ein vorgeschlagenes arithmetisiertes Beweisbarkeitsprädikat die Bedingungen tatsächlich erfüllt, was in der Regel langwierig und mühsam ist.

Dieser Nachteil führte unter anderem (siehe Feferman 1997) dazu, dass Solomon Feferman Ende der 1950er Jahre nach einer alternativen Herangehensweise an den zweiten Satz suchte (siehe Feferman 1960). Feferman geht das Problem in zwei Schritten an: Zunächst isoliert er die Formeln Prov_FOL(x), die einen Standardbegriff der Ableitbarkeit in der Logik erster Ordnung arithmetisieren, um uns zu ermöglichen, eine ausgewählte Formel für die Beweisbarkeit in der Logik festzulegen. Wie die Menge der nicht-logischen Axiome des betreffenden Systems dargestellt wird, bleibt in dieser Phase offen. Zweitens sucht Feferman nach einer geeigneten Einschränkung für die Darstellung der Axiome. Unter den Formeln der Sprache der Arithmetik isoliert er die sogenannten PR- und RE-Formeln; erstere entsprechen den kanonischen primitiv rekursiven (PR) Definitionen in der Arithmetik, letztere den existentiellen Verallgemeinerungen der ersteren. Jede rekursiv aufzählbare (RE) Menge kann durch eine Formel der letzteren Art definiert werden; dies sind einfach die \( \sum_{1}^{0} \)-Formeln. Diese beiden Klassen lassen sich allein anhand ihrer syntaktischen Form leicht unterscheiden. (Tatsächlich könnte man sich gemäß dem MRDP-Theorem (siehe unten) statt auf RE-Formeln auch auf eine noch einfachere Klasse von existentiell quantifizierten diophantischen Gleichungen konzentrieren.)

Wir haben oben die wichtige Tatsache festgestellt, dass in allen arithmetischen Theorien F, die Q enthalten, eine Menge genau dann stark in F darstellbar ist, wenn sie rekursiv ist, und eine Menge genau dann rekursiv abzählbar ist, wenn sie schwach darstellbar ist. Darüber hinaus kann man die Formel, die die Menge schwach oder stark repräsentiert, immer als RE-Formel (d. h. \( \sum_{1}^{0} \)-Formel; und nach dem MRDP-Theorem sogar als existentiell quantifizierte Diophantische Gleichung) betrachten. Es ist dann naheliegend, zu verlangen, dass die Menge der nicht-logischen Axiome des betreffenden Systems durch eine solche Formel repräsentiert wird. Wenn die arithmetisierte Definition der Menge der Gödel-Nummern von Axiomen widerspiegelt, wie die Axiome, sofern sie unendlich sind, induktiv definiert sind, ist die resultierende Formel \( \sum_{1}^{0} \). (Für Theorien, die mit endlich vielen Axiomen axiomatisierbar sind, gibt es eine eindeutige Darstellung der Axiome in Form einer Liste und folglich eine eindeutige Konsistenzaussage in Bezug auf Prov_FOL(x).) Im Gegensatz zur Feststellung, ob die Ableitungsbedingungen erfüllt sind, ist es eine relativ routinemäßige Aufgabe, festzustellen, ob eine bestimmte Formel, die die Axiome formalisiert, tatsächlich die erforderliche Form (\( \sum_{1}^{0} \)) hat.

Die Version des zweiten Unvollständigkeitssatzes, die in Feferman 1960 vorgestellt wurde, lautet nun:

Eine Variante des zweiten Unvollständigkeitssatzes (Feferman 1960)
Sei F eine konsistente Erweiterung von PA, sei Ax_F(x) eine \( \sum_{1}^{0} \)-Formel, die die Axiome von F schwach repräsentiert, und sei Cons(F) eine Konsistenzaussage, die aus Ax_F(x) und Prov_FOL(x) konstruiert wurde. Dann ist Cons(F) in F nicht beweisbar.

Für weitere Ansätze zum zweiten Unvollständigkeitssatz siehe Feferman 1982, 1989a; Visser 2011. Für einige philosophische Komplikationen bezüglich des zweiten Satzes siehe Detlefsen 1979, 1986, 1990, 2001; Auerbach 1985, 1992; Roeper 2003; Franks 2009 (siehe auch Abschnitt über Unvollständigkeit im Eintrag zu Hilberts Programm).

4. Ergebnisse im Zusammenhang mit den Unvollständigkeitssätzen

4.1 Tarskis Theorem über die Undefinierbarkeit der Wahrheit

Gödel gelangte erstmals zu den Unvollständigkeitsergebnissen (siehe Abschnitt 5 unten), indem er feststellte, dass Wahrheit (der Sprache eines Systems) in diesem System nicht definierbar sein muss – ein Ergebnis, das üblicherweise Tarski zugeschrieben wird (Tarskis Art, das Thema darzustellen, hat gewisse Vorzüge; siehe Gómez Torrente 2004). Betrachten wir nun das Ergebnis im Kontext von Tarskis Ansatz zur Wahrheit.

Tarski unterschied klar zwischen der Objekt-Sprache, d. h. der Sprache, um deren Wahrheitsgehalt es geht, und der Metasprache, in der diese diskutiert wird. Er forderte außerdem (siehe den Eintrag zu Tarskis Wahrheitsdefinitionen), dass jede zufriedenstellende Definition der Wahrheit True(x) für die Objektsprache seiner „Konvention T” genügen sollte, d. h. sie sollte alle Äquivalenzen („T-Äquivalenzen”) der Form

(T) True(┌A┐) ↔ B,

als ihre Konsequenz haben, wobei ┌A┐ der Name eines Satzes der Objektsprache und B dessen Übersetzung in der Metasprache ist. Ist die Metasprache identisch mit der Objektsprache oder eine Erweiterung derselben, ist B einfach A selbst, und die T-Äquivalenzen haben die Form:

True(┌A┐) ↔ A.

Das Undefinierbarkeitstheorem zeigt, dass die Objektsprache und die Metasprache nicht übereinstimmen können, sondern unterschiedlich sein müssen.

Tarskis Undefinierbarkeitssatz
Sei F ein konsistentes formalisiertes System, das eine ausreichende Menge an Arithmetik enthält. Dann gibt es keine Formel Tr(x) in der Sprache von F, sodass für jeden Satz A der Sprache von F gilt:

F ⊢ Tr(┌A┐) ↔ A.

Die Idee des Beweises: Gäbe es eine solche Formel der Sprache F, würde eine einfache Anwendung des Diagonalisierungslemmas auf ihre Negation zu dem paradoxen Satz L (für „Lügner”; siehe das Lügner-Paradoxon) führen, sodass:

F ⊢¬ Tr(┌L┐) ↔ L,

was zusammen mit den T-Äquivalenzen, von denen angenommen wurde, dass sie ableitbar sind, schnell zu einem expliziten Widerspruch führen würde, wodurch die Annahme, dass F konsistent ist, widerlegt würde.

Ebenso lässt sich nachweisen, dass die Menge der wahren Sätze von F in der beabsichtigten Interpretation von F nicht definierbar ist – im heute üblichen Sinne von „Definierbarkeit” (siehe oben).

4.2 Die Unentscheidbarkeitsergebnisse

Die Werkzeuge, die zum Beweis der Gödelschen Theoreme verwendet werden, liefern auch verschiedene wichtige Ergebnisse zur Unentscheidbarkeit. Eine Theorie wird als entscheidbar bezeichnet, wenn die Menge ihrer Theoreme (die darin ableitbaren Sätze) entscheidbar, d. h. (gemäß der Church-Turing-These) rekursiv ist. Andernfalls ist die Theorie unentscheidbar. Informell bedeutet Entscheidbarkeit, dass es ein mechanisches Verfahren gibt, mit dem man entscheiden kann, ob ein beliebiger gegebener Satz (der Sprache der Theorie) ein Theorem ist oder nicht.

Wenn eine Theorie vollständig ist, ist sie entscheidbar (Beweisskizze: Gegeben sei ein Satz A, dann werden systematisch die Theoreme der Theorie generiert; aufgrund der Vollständigkeit wird schließlich entweder A oder ¬A in endlicher Zeit erzeugt). Das Umgekehrte gilt jedoch nicht immer: Es gibt unvollständige Theorien, die entscheidbar sind. Dennoch eröffnet Unvollständigkeit zumindest die Möglichkeit der Unentscheidbarkeit. Darüber hinaus sind alle Theorien, die die Robinson-Arithmetik Q enthalten (entweder direkt oder Q kann in ihnen interpretiert werden), sowohl unvollständig als auch unentscheidbar. Somit gehen für eine sehr breite Klasse von Theorien Unvollständigkeit und Unentscheidbarkeit Hand in Hand.

Eine elegante und einfache Möglichkeit, die Unentscheidbarkeit von Erweiterungen von Q zu demonstrieren, lässt sich grob wie folgt beschreiben: Sei F eine beliebige konsistente Theorie, die Q enthält. Nehmen wir nun an, dass die Menge ihrer Theoreme entscheidbar, d. h. (gemäß der Church-Turing-These) rekursiv ist. Daraus würde folgen, dass die Menge (der Gödel-Zahlen) der Theoreme von F in F selbst stark repräsentierbar ist. Erinnern wir uns daran, dass dies bedeutet, dass es eine Formel B(x) der Sprache von F gibt, sodass nicht nur F ⊢ B(┌A┐) gilt, wenn F ⊢ A (was sogar die schwache Darstellbarkeit garantiert), sondern auch F ⊢¬ B(┌A┐), wenn F ⊬ A. Die im Beweis des ersten Unvollständigkeitssatzes verwendete Technik zeigt jedoch auch, dass es immer Sätze gibt, für die Letzteres nicht gilt: Es ist möglich, einen Gödel-Satz G^B relativ zu B(x) für F zu konstruieren, sodass gilt:

(D) F ⊢ G^B ↔ ¬B(┌G^B┐).

Wie zuvor folgt daraus, dass F ⊬ G^B. Es wurde angenommen, dass B(x) stark die Menge der Theoreme repräsentiert, daher folgt daraus F ⊢¬ B(┌G^B┐) und somit gemäß (D) F ⊢ G^B, was einen Widerspruch darstellt. Daher muss F unentscheidbar sein.

Eine Theorie F wird als im Wesentlichen unentscheidbar bezeichnet, wenn jede konsistente Erweiterung dieser Theorie in der Sprache von F unentscheidbar ist. Der obige Beweisskizze belegt tatsächlich, dass Q im Wesentlichen unentscheidbar ist. (Es gibt einige sehr schwache Theorien, die unentscheidbar, aber nicht im Wesentlichen unentscheidbar sind.)

Erinnern wir uns daran, dass Q nur endlich viele Axiome hat, und bezeichnen wir mit A_Q den einzigen Satz, der aus der Konjunktion der Axiome von Q besteht. Dann gilt für jeden Satz B der Sprache der Arithmetik

Q ⊢ B genau dann, wenn es ein Theorem der Logik erster Ordnung ist, dass A_Q → B.

Ein Entscheidungsverfahren für die Logik erster Ordnung würde jedoch eine Entscheidungsmethode für Q liefern. Letzteres ist jedoch, wie bereits gezeigt wurde, unmöglich. Daher kann man folgern:

Churchs Theorem
Die Prädikatenlogik erster Ordnung ist unentscheidbar.

(Dieses Unentscheidbarkeitsergebnis wurde erstmals von Church 1936a, b aufgestellt; die Methode, es über die Unentscheidbarkeit von Q abzuleiten, geht auf Tarski, Mostowski und Robinson 1953 zurück.)

In der Folge wurde gezeigt, dass eine Reihe von Theorien und Problemen aus verschiedenen Bereichen der Mathematik unentscheidbar sind (siehe z. B. Davis 1977; Murawski 1999: Kap. 3).

4.3 Reflexionsprinzipien und Löbs Theorem

Heuristisch betrachtet kann man den Gödel-Satz G_F als Ausdruck seiner eigenen Unbeweisbarkeit betrachten – als Aussage „Ich bin nicht beweisbar“ –, obwohl solche Behauptungen, wie bereits betont wurde, mit Vorsicht zu genießen sind. Leon Henkin warf die Frage auf, ob der Satz, der seine eigene Beweisbarkeit ausdrückt („Ich bin beweisbar“), wahr oder falsch und beweisbar oder nicht beweisbar ist (Henkin 1952). Georg Kreisel wies bald darauf hin, dass dies entscheidend davon abhängt, wie die Beweisbarkeit ausgedrückt wird; bei unterschiedlichen Wahlmöglichkeiten erhält man gegensätzliche Antworten (Kreisel 1953).

Die Arbeit von Martin Hugo Löb (1955), ergänzt durch Kommentare eines Gutachters, brachte in verschiedener Hinsicht wesentliche Fortschritte. Erstens führt sie die heute standardmäßigen Löb-Ableitbarkeitsbedingungen ein, die zuvor im Zusammenhang mit dem zweiten Unvollständigkeitssatz diskutiert wurden. Zweitens enthält sie Löbs Lösung für Henkin’s Problem bezüglich Sätzen, die „ihre eigene Beweisbarkeit ausdrücken”. Drittens enthält sie eine Verallgemeinerung, die heute als „Löbscher Satz” bezeichnet wird, die Löb jedoch eigentlich dem anonymen Gutachter zuschreibt (bei dem es sich zufällig um Henkin selbst handelte; die ganze Geschichte wird in Smoryński 1991 erzählt).

Um den Löbschen Satz richtig zu verstehen, ist es hilfreich, zunächst die sogenannten „Reflexionsprinzipien” zu betrachten. Bisher lag der Schwerpunkt darauf, innerhalb eines formalen Systems auszudrücken, dass das System konsistent ist, d. h. auf Cons(F). Aber natürlich sollte die Theorie nicht nur konsistent, sondern auch fundiert sein, d. h. nur wahre Sätze beweisen. Wie sollte die Fundiertheit eines Systems, d. h. die Behauptung, dass alles, was in dem System abgeleitet werden kann, wahr ist, ausgedrückt werden? Wenn man dies in der Sprache des Systems selbst ausdrücken möchte, kann dies nicht durch eine einzige Aussage geschehen, da es aufgrund der Undefinierbarkeit der Wahrheit kein geeignetes Wahrheitsprädikat in dieser Sprache gibt. Verschiedene eingeschränkte und uneingeschränkte Aussagen zur Korrektheit können jedoch in Form eines Schemas, den sogenannten Reflexionsprinzipien, ausgedrückt werden:

(Ref) Prov_F(┌A┐) → A.

Wenn man A als ⊥ ansetzt und berücksichtigt, dass ⊥ in F widerlegbar ist, lässt sich leicht erkennen, dass das Reflexionsprinzip die Konsistenzaussage Cons(F) impliziert, d. h. ¬Prov_F(┌⊥┐); daher kann es im System nicht allgemein beweisbar sein.

Das Schema kann auch eingeschränkt werden. Entsprechend der Annahme der 1-Konsistenz oder der \( \sum_{1}^{0} \)-Korrektheit ist beispielsweise das Reflexionsprinzip auf \( \sum_{1}^{0} \)-Sätze beschränkt (d. h., der Satz A im Schema muss ein \( \sum_{1}^{0} \)-Satz sein). Oder es kann auf die universellen \( \Pi_{1}^{0} \)-Sätze beschränkt werden usw.

Welche Fälle des Reflexionsschemas sind in diesem System tatsächlich beweisbar? Löbs Theorem gibt eine präzise Antwort auf diese Frage (vorausgesetzt, dass Prov_F(x) die Ableitbarkeitsbedingungen erfüllt):

Löbs Theorem
Sei A ein beliebiger Satz der Sprache von F. Dann gilt: F ⊢ Prov_F(┌A┐) → A genau dann, wenn F ⊢ A.

Daher sind die in einem System beweisbaren Fälle von Korrektheit (Reflexionsprinzip) genau diejenigen, die Sätze betreffen, die selbst in dem System beweisbar sind. Damit ist auch Henkins ursprüngliches Problem gelöst: Unter der Annahme, dass das arithmetisierte Beweisbarkeitsprädikat wieder „normal” ist (d. h. Löbs Ableitbarkeitsbedingungen erfüllt), sind alle Sätze, die „ihre eigene Beweisbarkeit behaupten”, beweisbar.

Tatsächlich lässt sich Löbs Theorem recht schnell als Folge des zweiten Unvollständigkeitssatzes beweisen. Kreisel hat auch festgestellt, dass sich umgekehrt der zweite Unvollständigkeitssatz leicht als Folge von Löbs Theorem ableiten lässt.

4.4 Hilberts zehntes Problem und das MRDP-Theorem

Der zehnte Punkt auf Hilberts berühmter Liste wichtiger offener Probleme der Mathematik aus dem Jahr 1900 fordert eine Entscheidungsmethode für die sogenannten diophantischen Gleichungen. Trotz des unfamiliären Begriffs „diophantisch” handelt es sich hier um etwas wirklich Elementares. Betrachten Sie eine beliebige Gleichung mit einer oder mehreren Variablen und ganzzahligen Koeffizienten, die nur Addition und Multiplikation beinhaltet, wie z. B. x² + y² = 2 oder 3x² + 5y² + 2xy = 0. Wenn nach reellen Lösungen gesucht wird, spricht man in der Regel einfach von einer „Gleichung”. In der Zahlentheorie wird jedoch typischerweise nach einer Lösung gesucht, die nur aus ganzen Zahlen besteht. Das macht einen großen Unterschied. Die erste der oben genannten Gleichungen hat unendlich viele Lösungen unter den reellen Zahlen, aber nur vier unter den ganzen Zahlen. Die Gleichung x² + y² = 3 hat ebenfalls unendlich viele reelle Lösungen, aber keine ganzzahligen Lösungen. Wenn der Fokus auf den ganzzahligen Lösungen liegt, spricht man von „Diophantischen Gleichungen“ (nach dem antiken Zahlentheoretiker Diophantus von Alexandria).

Für eine positive Lösung von Hilberts zehntem Problem hätte es ausgereicht, eine bestimmte konkrete Methode vorzustellen, die intuitiv eine „mechanische“ Entscheidungsmethode gewesen wäre. Turings bahnbrechende Analyse des Begriffs der Entscheidungsmethode rückte jedoch die Möglichkeit einer negativen Lösung in den Fokus. Seit Anfang der 1950er Jahre arbeiteten Julia Robinson und Martin Davis an diesem Problem, später kam Hilary Putnam hinzu. Als Ergebnis ihrer Zusammenarbeit wurde das erste wichtige Ergebnis in dieser Richtung erzielt. Eine Gleichung wird als „exponentielle Diophantische Gleichung” bezeichnet, wenn sie neben Addition und Multiplikation auch Potenzierung beinhaltet (d. h. sowohl Konstanten als auch Variablen können als Exponenten vorkommen); natürlich liegt der Schwerpunkt weiterhin auf den ganzzahligen Lösungen. Davis, Putnam und Robinson (1961) zeigten, dass das Problem der Lösbarkeit exponentieller Diophantischer Gleichungen unentscheidbar ist. Im Jahr 1970 fügte Yuri Matiyasevich das letzte fehlende Teil hinzu und zeigte, dass das Problem der Lösbarkeit diophantischer Gleichungen unentscheidbar ist. Daher wird das Gesamtergebnis oft als MRDP-Theorem bezeichnet (für eine Darstellung siehe z. B. Davis 1973; Matiyasevich 1993).

Die wesentliche technische Errungenschaft bestand darin, dass alle halbentscheidbaren (rekursiv aufzählbaren) Mengen eine diophantische Darstellung erhalten können, d. h. sie können durch eine einfache Formel der Form ∃x₁ … ∃x_n(s=t) dargestellt werden, wobei (s=t) eine diophantische Gleichung ist. Genauer gesagt, für jede gegebene rekursiv aufzählbare Menge S gibt es eine diophantische Gleichung (s(y,x₁,…,x_n) = t(y,x₁,…,x_n)), sodass n ∈ S genau dann gilt, wenn ∃x₁ … ∃x_n(s(\( \overline{n} \),x₁,…,x_n) = t(\( \overline{n} \),x₁,…,x_n)).

Da es halbentscheidbare (rekursiv aufzählbare) Mengen gibt, die nicht entscheidbar (rekursiv) sind, folgt unmittelbar die allgemeine Schlussfolgerung:

MRDP-Theorem
Es gibt keine allgemeine Methode, um zu entscheiden, ob eine bestimmte diophantische Gleichung eine Lösung hat oder nicht.

Dies liefert auch eine elegante Variante der Unvollständigkeitssätze, die sich mit diophantischen Gleichungen befassen:

Folgerung
Für jedes 1-konsistente axiomatisierbare formale System F gibt es diophantische Gleichungen, die keine Lösungen haben, aber in F nicht als lösungslos bewiesen werden können.

(Die Frage, wie man die Anforderung der 1-Konsistenz hier umgehen kann, ist knifflig; siehe Dyson, Jones und Shepherson 1982.)

4.5 Konkrete Fälle von nicht beweisbaren Aussagen

Die durch Gödels Beweise gelieferten unentscheidbaren Sätze sind (wenn man sie ausschreibt) äußerst komplizierte Formeln ohne intuitive Bedeutung, die nur zum Zweck der Unvollständigkeitsbeweise konstruiert wurden. Es stellt sich nun die Frage, ob es einfache und natürliche mathematische Aussagen gibt, die in ausgewählten Basistheorien, z. B. in PA, ebenfalls unentscheidbar sind. Es gibt nun verschiedene spezifische Aussagen mit klarem mathematischem Inhalt, von denen bekannt ist, dass sie in einigen Standardtheorien unentscheidbar sind (obwohl umstritten ist, wie natürlich diese überhaupt sind; siehe Feferman 1989b). Einige bekannte, natürliche Beispiele sind unten aufgeführt, beginnend mit einigen ganz natürlichen mathematischen Aussagen, die unabhängig von PA sind, bis hin zu immer mächtigeren Theorien. Manchmal werden solche Ergebnisse als Varianten des Gödelschen Theorems oder ihre Unabhängigkeitsbeweise als alternative Beweise des Gödelschen Theorems bezeichnet, aber das ist irreführend: So interessant sie auch sein mögen, sie haben nicht die Allgemeingültigkeit der eigentlichen Gödelschen Theoreme, sondern liefern nur Aussagen, die von einer bestimmten Theorie unabhängig sind.

Es wird oft behauptet, dass vor dem berühmten Paris-Harrington-Theorem (siehe unten) keine solchen natürlichen unabhängigen mathematischen Aussagen bekannt waren. Dies ist jedoch streng genommen nicht korrekt. Bereits viel früher, um 1935, hatte Gerhard Gentzen (siehe den Eintrag zur Entwicklung der Beweistheorie) eine solche Aussage geliefert. Es ist sehr naheliegend, den Begriff der Induktion vom Bereich der natürlichen Zahlen auf den Bereich der Ordnungszahlen zu verallgemeinern. In der Mengenlehre werden solche Verallgemeinerungen als Prinzipien der transfiniten Induktion bezeichnet. Auch wenn einige Konstruktivisten die Legitimität der vollständigen Mengenlehre anzweifeln, gibt es begrenzte und konkretere Fälle der transfiniten Induktion (die sich nur mit einigen genau definierten Klassen von zählbaren Ordnungszahlen befassen), die selbst aus konstruktivistischer oder intuitionistischer Sicht vollkommen akzeptabel sind. Ein wichtiger Fall ist das Prinzip der transfiniten Induktion bis zur Ordnungszahl ε₀. Gentzen zeigte, dass die Konsistenz von PA bewiesen werden kann, wenn dieses Prinzip der transfiniten Induktion angenommen wird. Aufgrund des zweiten Unvollständigkeitssatzes kann das Prinzip selbst daher in PA nicht bewiesen werden (Gentzen 1936).

Ramseys Theorem ist ein Ergebnis der infinitären Kombinatorik, das von Frank Ramsey (1930) aufgestellt wurde und sich mit den Möglichkeiten der „Einfärbung” bestimmter Graphen befasst. Jeff Paris und Leo Harrington formulierten eine finitäre Variante von Ramseys Theorem und zeigten, dass es in PA nicht beweisbar ist (Paris & Harrington 1977). Dies liefert eine ganz natürliche Aussage der endlichen Kombinatorik, die unabhängig von PA ist. Ein vielleicht noch klareres Beispiel ist Goodsteins Theorem von Reuben Goodstein (1944), das rein zahlentheoretischer Natur ist. Zunächst definiert man eine bestimmte natürliche Klasse von Folgen natürlicher Zahlen, die heute als „Goodstein-Folgen” bezeichnet werden. Der Satz besagt, dass jede Goodstein-Folge schließlich bei 0 endet. Goodsteins Theorem ist zweifellos eine natürliche mathematische Aussage, denn es wurde von Goodstein lange bevor (nämlich 1944) 1982 gezeigt wurde, dass das Theorem in PA nicht beweisbar ist (Kirby & Paris 1982), formuliert und bewiesen (natürlich mit Beweismethoden, die über PA hinausgehen).

Wenn man nun zu stärkeren Theorien jenseits von PA übergeht, kann man beispielsweise Kruskals Theorem erwähnen. Dabei handelt es sich um ein Theorem, das bestimmte Ordnungen endlicher Bäume betrifft (Kruskal 1960). Harvey Friedman hat gezeigt, dass dieses Theorem selbst in Subsystemen der Arithmetik zweiter Ordnung, die viel stärker sind als PA, nicht beweisbar ist (siehe Simpson 1985). Insbesondere ist es in keiner Theorie beweisbar, die prädikativ gerechtfertigt ist (unter einer weithin akzeptierten Erklärung von „prädikativ”, vgl. den Abschnitt über Prädikativismus im Eintrag zur Philosophie der Mathematik).

Es gibt einige konkrete Beispiele für mathematische Aussagen, die selbst in stärkeren Theorien unentschieden sind und aus der sogenannten deskriptiven Mengenlehre stammen. Dieses Gebiet der Mathematik ist mit der Topologie verwandt und wurde von den französischen Semi-Intuitionisten (Lebesgue, Baire, Borel; siehe den Abschnitt über deskriptive Mengenlehre usw. im Eintrag über Intuitionismus in der Philosophie der Mathematik) begründet. Es untersucht Mengen, die relativ einfache Definitionen besitzen (im Gegensatz zu den Ideen willkürlicher Mengen und verschiedener höherer Potenzmengen, die die Semi-Intuitionisten als bedeutungslos ablehnten), die als projektive oder analytische Mengen bezeichnet werden. Klassisch wurden diese als Mengen definiert, die aus einer abzählbaren Schnittmenge offener Mengen durch endliches Malen von kontinuierlichen Abbildungen und Komplementen aufgebaut werden können; sie stimmen mit den Mengen überein, die in der Sprache von P2 definierbar sind. Insbesondere können die sogenannten Borel-Mengen sowohl durch eine Formel der Form ∃XA(x) als auch durch eine Formel der Form ∀XB(x) einfach definiert werden, wobei A und B keine Mengenvariablen enthalten (in der Terminologie der Logiker sind Borel-Mengen die \( \Delta_{1}^{1} \)-Mengen). Eine Borel-Funktion wird analog definiert (siehe z. B. Martin 1977).

Harvey Friedman hat den folgenden Satz aufgestellt: Grob gesagt, wenn S eine Borel-Menge ist, dann gibt es eine Borel-Funktion f, sodass der Graph von f entweder in S enthalten oder von S disjunkt ist. Friedman zeigte, dass dieser einfach klingende Satz selbst in der vollständigen Arithmetik zweiter Ordnung P2 nicht beweisbar ist, sondern dass zu seinem Beweis zwangsläufig die volle Kraft von ZFC erforderlich ist (siehe Simpson 1999: 23).

Darüber hinaus war es eine traditionelle Frage der deskriptiven Mengenlehre (eine Frage, die in der Sprache der Arithmetik zweiter Ordnung formuliert werden kann), ob alle projektiven Mengen (siehe oben) Lebesque-messbar sind. Dies blieb viele Jahrzehnte lang ein offenes Problem, und das aus gutem Grund: Es stellte sich heraus, dass die Aussage sogar von der vollständigen ZFC-Mengenlehre unabhängig ist (siehe Solovay 1970). Nur durch die Postulierung der Existenz einiger extrem großer Kardinalzahlen (sogenannter Woodin-Kardinalzahlen) kann die Hypothese, dass alle projektiven Mengen Lebesque-messbar sind, bewiesen werden (dies wurde als Folge ihrer Arbeit zur sogenannten projektiven Determiniertheit von Woodin, Martin und Steel erreicht; siehe Woodin 1988; Martin & Steel 1988, 1989).

Manchmal wird Paul Cohens berühmtes Ergebnis, dass die Kontinuumshypothese (CH) unabhängig von ZFC ist (Cohen 1963, 1964; siehe den Eintrag zu Unabhängigkeit und großen Kardinalzahlen), angeführt. Dieser Fall ist jedoch ganz anders gelagert. In allen oben genannten Unabhängigkeitsergebnissen sind die relevanten Aussagen immer noch Theoreme der Mathematik, die als wahr angesehen werden (der letzte Fall, der große Kardinalaxiome erfordert, die über ZFC hinausgehen, ist umstrittener; dennoch finden zumindest viele Mengen-Theoretiker solche Axiome plausibel). Und beim ersten Unvollständigkeitssatz selbst folgt die Wahrheit der unbeweisbaren Aussage leicht, vorausgesetzt, dass die Annahme der Konsistenz des Systems tatsächlich korrekt ist. Im Fall von Cohens Ergebnis gibt es jedoch absolut keinen Hinweis darauf, ob CH als wahr, falsch oder vielleicht ohne Wahrheitswert anzusehen ist.

5. Die Geschichte und frühe Rezeption der Unvollständigkeitssätze

Gödels Ergebnisse waren sicherlich überraschend, aber eine Art Unvollständigkeitsphänomen war nicht völlig unerwartet. Die Möglichkeit der Unvollständigkeit im Zusammenhang mit der Mengenlehre wurde bereits 1928 von Bernays und Tarski diskutiert, und von Neumann hatte im Gegensatz zum vorherrschenden Geist in Hilberts Programm die Möglichkeit in Betracht gezogen, dass Logik und Mathematik nicht entscheidbar seien. Gödel selbst hatte in seiner Dissertation von 1929 die Möglichkeit eines unentscheidbaren Problems in Bezug auf reelle Zahlen erwähnt (siehe Dawson 1985). Hilbert (1928) hingegen war davon ausgegangen, dass die Peano-Arithmetik und andere Standardtheorien vollständig seien. Anscheinend war Gödel auch von Brouwer beeindruckt, der in seinem Vortrag in Wien 1928 angedeutet hatte, dass Mathematik unerschöpflich ist und nicht vollständig formalisiert werden kann (siehe Wang 1987, 84; und den Abschnitt über Brouwers Sichtweise des formalistischen Programms im Eintrag über die Entwicklung der intuitionistischen Logik).

Wie dem auch sei, es scheint, dass Gödel tatsächlich auf einem anderen Weg zu den ersten genauen Beobachtungen über Unvollständigkeit gelangte, nämlich während seiner Versuche, zu Hilberts Programm beizutragen und es nicht zu untergraben (siehe Dawson 1997: Kap. IV). 1930 unternahm Gödel nämlich den Versuch, Hilberts Programm voranzubringen, indem er versuchte, die Konsistenz der Analysis (oder der Arithmetik zweiter Ordnung) mit den Mitteln der Arithmetik zu beweisen und so die Konsistenz der ersteren auf die Konsistenz der letzteren zu reduzieren. In seinem Beweisversuch benötigte er den Begriff der Wahrheit. Gödel stieß bald auf verschiedene Paradoxien (wie das Lügner-Paradoxon) und musste zu dem Schluss kommen, dass arithmetische Wahrheit nicht in der Arithmetik definiert werden kann. Daher gelangte Gödel zunächst zu einer Version des Unbestimmbarkeitssatzes, der normalerweise mit Tarski in Verbindung gebracht wird (vgl. Murawski 1998). Dies führt auch leicht zu einer schwachen Version des Unvollständigkeitsergebnisses: Die Menge der in der Arithmetik beweisbaren Sätze kann in der Sprache der Arithmetik definiert werden, die Menge der wahren arithmetischen Sätze jedoch nicht; daher können beide nicht übereinstimmen. Unter der Annahme, dass alle beweisbaren Sätze wahr sind, folgt daraus außerdem, dass es wahre Sätze geben muss, die nicht beweisbar sind. Dieser Ansatz zeigt jedoch keinen bestimmten solchen Satz auf.

Das intellektuelle Umfeld Gödels war jedoch das des Wiener Kreises mit seiner radikal antimetaphysischen Haltung. Insbesondere wurde damals sogar der Begriff der Wahrheit als verdächtig oder sogar unsinnig angesehen, zumindest von einigen logischen Positivisten (z. B. Neurath, Hempel). Daher bemühte sich Gödel intensiv, jeglichen Bezug zum Begriff der Wahrheit zu eliminieren und versuchte, ohne ihn auszukommen. Er führte daher den Begriff der ω-Konsistenz ein, der streng und rein syntaktisch definiert werden kann. Dies führte zu den Unvollständigkeitssätzen in der Form, wie sie heute bekannt sind.

Was das Diagonalisierungslemma betrifft, so hat Gödel selbst ursprünglich nur einen Sonderfall davon nachgewiesen, nämlich nur für das Prädikat der Beweisbarkeit. Das allgemeine Lemma wurde offenbar erstmals 1934 von Carnap entdeckt (siehe Gödel 1934, 1935). Noch allgemeinere Versionen für Formeln mit freien Variablen wurden 1960 von Ehrenfeucht & Feferman und 1962 von Montague vorgestellt (siehe Smoryński 1981).

Die Reaktionen auf Gödels Ergebnisse waren gemischt. Einige wichtige Persönlichkeiten auf dem Gebiet der Logik und der Grundlagen der Mathematik nahmen die Ergebnisse recht schnell auf und erkannten ihre Bedeutung, aber es gab auch zahlreiche Missverständnisse und Widerstände (ausführliche Berichte über die Reaktionen finden sich bei Dawson 1985; Mancosu 1999).

Gödel offenbarte Carnap seine Ergebnisse am 26. August 1930 in Wien und verkündete sein Ergebnis (den ersten Satz) in einer beiläufigen Bemerkung während der berühmten Königsberger Konferenz am 7. September 1930. John von Neumann, der im Publikum saß und zu dieser Zeit im Rahmen von Hilberts Programm arbeitete, erkannte sofort die große Bedeutung des Ergebnisses. Am 20. November schrieb er einen Brief an Gödel über eine „bemerkenswerte” Folge von Gödels Ergebnis, die er entdeckt hatte: die Unbeweisbarkeit der Konsistenz (der zweite Satz). In der Zwischenzeit war Gödel jedoch selbst auf dieselbe Idee gekommen und hatte bereits die endgültige Fassung seines Artikels, der nun auch eine Aussage zum zweiten Unvollständigkeitssatz enthielt, zur Veröffentlichung eingereicht. Der Artikel wurde im Januar 1931 veröffentlicht (Gödel 1931; hilfreiche Einführungen zu Gödels Originalarbeit finden sich bei Kleene 1986 und Zach 2005). Die Nachricht von diesen Ergebnissen, die offenbar von großer Bedeutung für die Grundlagen der Mathematik waren, verbreitete sich schnell – auch wenn die Meinungen darüber, was wirklich die Moral war, auseinander gingen. Paul Bernays, der vielleicht wichtigste Mitarbeiter Hilberts, zeigte großes Interesse an den Ergebnissen, obwohl er zunächst Schwierigkeiten hatte, sie richtig zu verstehen. Seine rege Korrespondenz mit Gödel zeigt auch, dass Gödel sich bereits damals der Undefinierbarkeit der Wahrheit voll bewusst war.

Da sich Gödels ursprünglicher Ansatz auf sein spezifisches, wenn auch sehr umfassendes System P und dessen (primitiv rekursive) Erweiterungen konzentrierte, zweifelten einige an der Allgemeingültigkeit von Gödels Ergebnissen. Alonzo Church beispielsweise äußerte in einem Brief an Gödel im Juli 1932 die Vermutung, dass Gödels Ergebnisse nicht auf sein System der λ-Konversion anwendbar seien (das System wurde später von Kleene und Rosser als inkonsistent bewiesen). Gödel war bestrebt, seine Entdeckungen zu verallgemeinern, und erweiterte die Ergebnisse in Arbeiten aus den Jahren 1932 und 1934 auf eine breitere Klasse von Systemen. Er schlug auch vor, dass seine Methoden auf Standardsysteme der Mengenlehre anwendbar seien (allerdings war es erst nach der zufriedenstellenden Charakterisierung der Entscheidbarkeit und der Church-Turing-These einige Jahre später möglich, eine vollständig allgemeine Formulierung der Unvollständigkeitssätze zu geben (siehe oben); dies gelang erstmals Kleene 1936). Der bedeutende Mengenlehrer Ernst Zermelo übte ziemlich harte Kritik an Gödels Arbeit, aber die beiden korrespondierten auch über dieses Thema. Zermelo scheint ernsthafte Schwierigkeiten gehabt zu haben, die relevanten Konzepte und Ergebnisse zu verstehen.

Im März 1933 erhielt Gödel einen Brief von Paul Finsler aus Zürich, der behauptete, bereits früher (in Finsler 1926) eng verwandte Arbeiten mit allgemeinerer Relevanz durchgeführt zu haben. Gödel antwortete, dass Finslers System überhaupt nicht wirklich definiert sei. In seiner hitzigen Antwort behauptete Finsler, dass es nicht notwendig sei, ein System studieren zu können, damit es klar definiert sei, und dass es keinen grundsätzlichen Unterschied zwischen seinen Ideen und denen Gödels gebe. Rückblickend ist es ganz klar, dass die Ansätze von Finsler und Gödel sehr unterschiedlich waren: Für Gödels Arbeit war der Begriff des formalisierten Systems wesentlich, während Finsler diesen Begriff als künstlich einschränkend ablehnte. Tatsächlich ist es alles andere als klar, dass Finslers Ideen überhaupt Sinn ergeben – unabhängig davon, welche vagen Analogien zwischen ihnen und Gödels Beweis bestehen mögen.

Andererseits kann man mit Fug und Recht sagen, dass Emil Post in gewisser Hinsicht Gödels Entdeckungen vorweggenommen hatte. Offenbar gelangte er bereits 1922 zu abstrakten Versionen von Unvollständigkeitsergebnissen. Insbesondere stellte er fest, dass seine Methoden eine in Principia Mathematica unentscheidbare Aussage liefern würden. Diese Ergebnisse basierten jedoch auf Posts eigener Version der „Church-Turing-These”, mit der er unzufrieden war, und seine Arbeit blieb unveröffentlicht. Sie wurde erst viel später in (Post 1941) veröffentlicht.

Die Richtigkeit von Gödels Theoremen blieb während der gesamten 1930er Jahre Gegenstand lebhafter Debatten (siehe Dawson 1985). 1939 erschien der zweite Band von Hilberts und Bernays‘ „Die Grundlagen der Mathematik”, der einen detaillierten Beweis des zweiten Unvollständigkeitssatzes enthielt. Danach verschwand der ernsthafte Widerstand gegen Gödels Schlussfolgerungen zumindest unter denjenigen, die sich aktiv mit mathematischer Logik und den Grundlagen der Mathematik befassten. In eher philosophischen Kreisen blieb jedoch ein gewisser Widerstand bestehen. Am bekanntesten sind Wittgensteins kritische Bemerkungen zu Gödels Theorem in seinem posthum veröffentlichten Werk „Remarks on the Foundations of Mathematics”. Die vorherrschende erste Reaktion war, dass Wittgenstein das Ergebnis einfach nicht verstanden habe. Es sind jedoch auch wohlwollendere Interpretationen aufgetaucht, und die Debatte ist nach wie vor sehr lebendig (siehe den Abschnitt über Gödel und unentscheidbare Aussagen im Eintrag zu Wittgensteins Philosophie der Mathematik).

6. Philosophische Implikationen – reale und vermeintliche

6.1 Philosophie der Mathematik

Von den verschiedenen Bereichen der Philosophie sind Gödels Theoreme offensichtlich für die Philosophie der Mathematik am unmittelbarsten relevant. Zunächst einmal stellen sie, zumindest auf den ersten Blick, ernsthafte Probleme für Hilberts Programm dar (dieses Thema wird im Abschnitt über die Auswirkungen der Unvollständigkeit im Eintrag zu Hilberts Programm ausführlich behandelt). Außerdem haben sie wichtige Konsequenzen für den Intuitionismus (siehe den Eintrag zum Intuitionismus in der Philosophie der Mathematik) (siehe auch Gödel 1933, 1941; Raatikainen 2005).

Es gibt einige Kontroversen darüber, ob Gödels Theoreme den Logizismus endgültig widerlegen (siehe den Eintrag zum Logizismus). Henkin (1962) und Musgrave (1977) argumentieren beispielsweise, dass dies der Fall ist; Sternfeld (1976) und Rodríguez-Consuegra (1993) sind anderer Meinung (siehe auch Hellman 1981; Raatikainen 2005).

Gödel selbst entwickelte ein Argument gegen die konventionalistische Philosophie der Mathematik des logischen Positivismus, insbesondere gegen die von Carnap, basierend auf den Unvollständigkeitsergebnissen (Gödel 1953/9). Dies wird diskutiert in Goldfarb und Ricketts 1992; Ricketts 1995; Goldfarb 1995; Crocco 2003; Awodey & Carus 2003, 2004; Tennant 2008.

6.2 Selbstverständliche und analytische Wahrheiten

Man kann auch allgemeinere erkenntnistheoretische Interpretationen von Gödels Theoremen geben. Quine und Ullian (1978) betrachten beispielsweise das traditionelle philosophische Bild, dass alle Wahrheiten durch selbstverständliche Schritte aus selbstverständlichen Wahrheiten und Beobachtungen bewiesen werden könnten. Sie weisen dann darauf hin, dass selbst die Wahrheiten der elementaren Zahlentheorie vermutlich nicht allgemein durch selbstverständliche Schritte aus selbstverständlichen Wahrheiten ableitbar sind (Quine & Ullian 1978: 64–65). Hilary Putnam (1975) wiederum vertritt die Auffassung, dass es nach einem bestimmten natürlichen Verständnis von „analytisch” gemäß Gödels Theoremen synthetische Wahrheiten in der Mathematik geben muss. Tatsächlich äußerte sich Gödel selbst in einem sehr ähnlichen Sinne, dass sogar die Theorie der ganzen Zahlen nachweislich nicht-analytisch ist (Gödel 1944).

6.3 „Gödelische” Argumente gegen den Mechanismus

Es gab wiederholte Versuche, mit Hilfe von Gödels Theoremen zu zeigen, dass die Fähigkeiten des menschlichen Geistes jeden Mechanismus und jedes formale System übertreffen. Ein solches Gödelsches Argument gegen den Mechanismus wurde bereits Ende der 1940er Jahre von Turing in Betracht gezogen, wenn auch nur, um es zu widerlegen (siehe Piccinini 2003). Eine uneingeschränkte anti-mechanistische Schlussfolgerung wurde aus den Unvollständigkeitssätzen in einer viel gelesenen populären Abhandlung, Gödel’s Theorem, von Nagel und Newman (1958) gezogen. Kurz darauf verkündete J.R. Lucas (1961) seine berühmte These, dass Gödels Unvollständigkeitssatz

beweist, dass Mechanismus falsch ist, das heißt, dass der Geist nicht als Maschine erklärt werden kann.

Er erklärte, dass

[es] bei jeder Maschine, die konsistent ist und einfache arithmetische Operationen ausführen kann, eine Formel [gibt], die sie nicht als wahr erzeugen kann … die wir aber als wahr erkennen können.

In jüngerer Zeit wurden sehr ähnliche Behauptungen von Roger Penrose (1989, 1994) aufgestellt. John Searle (1997) hat sich der Diskussion angeschlossen und Penrose teilweise gegen seine Kritiker verteidigt. Crispin Wright (1994, 1995) hat verwandte Ideen aus intuitionistischer Sicht befürwortet (Kritik siehe Detlefsen 1995). Sie alle bestehen darauf, dass Gödels Theoreme implizieren, dass der menschliche Geist die Leistungsfähigkeit jeder endlichen Maschine oder jedes formalen Systems unendlich übertrifft.

Diese gödelschen anti-mechanistischen Argumente sind jedoch problematisch, und es besteht weitgehende Einigkeit darüber, dass sie nicht stichhaltig sind. Die Standardantwort auf dieses Argument lautet in etwa wie folgt (dieser Einwand geht auf Putnam 1960 zurück; siehe auch Boolos 1968, Shapiro 1998): Das Argument geht davon aus, dass es für jedes formalisierte System oder jede endliche Maschine einen Gödel-Satz gibt, der in diesem System nicht beweisbar ist, dessen Wahrheit der menschliche Verstand jedoch erkennen kann. In Wirklichkeit hat Gödels Theorem jedoch eine bedingte Form, und die angebliche Wahrheit des Gödel-Satzes eines Systems hängt von der Annahme der Konsistenz des Systems ab. Das Argument der Anti-Mechanisten setzt also auch voraus, dass der menschliche Verstand immer erkennen kann, ob eine bestimmte formalisierte Theorie konsistent ist oder nicht. Dies ist jedoch höchst unwahrscheinlich (vgl. Davis 1990). Lucas, Penrose und andere haben versucht, auf solche Kritik zu antworten (siehe z. B. Lucas 1996; Penrose 1995, 1997). Eine ausführliche Kritik an Penrose findet sich bei Boolos 1990; Davis 1990, 1993; Feferman 1995; Lindström 2001; Pudlák 1999; Shapiro 2003; viele dieser Überlegungen sind auch für die Aussagen von Lucas relevant.

6.4 Gödel und Benacerraf über Mechanismus und Platonismus

Interessanterweise brachte Gödel selbst auch ein anti-mechanistisches Argument vor, obwohl es vorsichtiger war und erst posthum veröffentlicht wurde (in seinen Collected Works, Band III, 1995). Das heißt, in seiner Gibbs-Vorlesung von 1951 zog Gödel aus den Unvollständigkeitssätzen die folgende disjunktive Schlussfolgerung:

Entweder übertrifft der menschliche Verstand (selbst im Bereich der reinen Mathematik) die Leistungsfähigkeit jeder endlichen Maschine unendlich, oder es gibt absolut unlösbare diophantische Probleme.

Gödel spricht von dieser Aussage als einer „mathematisch bewiesenen Tatsache“ (Gödel 1951; für weitere Diskussionen zu Gödels disjunktiver Behauptung siehe z. B. Shapiro 1998). Laut Gödel scheint die zweite Alternative

die Ansicht zu widerlegen, dass Mathematik nur unsere eigene Schöpfung ist … dass mathematische Objekte und Fakten … objektiv und unabhängig von unseren mentalen Handlungen und Entscheidungen existieren.

Gödel neigte dennoch dazu, die Möglichkeit absolut unlösbarer Probleme zu leugnen, und obwohl er an den mathematischen Platonismus glaubte, waren seine Gründe für diese Überzeugung andere, und er behauptete nicht, dass die Unvollständigkeitssätze allein den Platonismus begründen. So glaubte Gödel an die erste Disjunktion, dass der menschliche Geist die Leistungsfähigkeit jeder endlichen Maschine unendlich übertrifft. Diese Schlussfolgerung Gödels folgt jedoch, wie Gödel selbst klar erklärt, nur, wenn man wie Gödel die Möglichkeit menschlich unlösbarer Probleme leugnet. Sie ist keine notwendige Folge der Unvollständigkeitssätze.

Im Gegensatz zu den späteren Befürwortern des sogenannten Gödelschen Anti-Mechanismus-Arguments war Gödel sensibel genug, um zuzugeben, dass sowohl der Mechanismus als auch die Alternative, dass es für den Menschen absolut unlösbare Probleme gibt, mit seinen Unvollständigkeitssätzen vereinbar sind. Seine grundlegenden Gründe für seine Ablehnung der letzteren Alternative sind viel philosophischer. Gödel dachte in einer etwas kantianischen Weise, dass die menschliche Vernunft fatal irrational wäre, wenn sie Fragen stellen würde, die sie nicht beantworten kann (für eine kritische Diskussion siehe Kreisel 1967; Boolos 1995; Raatikainen 2005).

Als Reaktion auf Lucas‘ Argument, aber noch vor der Veröffentlichung von Gödels Gibbs-Vorlesung, stellte Paul Benacerraf (1967) differenziertere Schlussfolgerungen auf, die interessanterweise einigen Ideen Gödels ähneln. Er argumentierte, dass es mit allen Fakten vereinbar ist, dass ich tatsächlich eine Turing-Maschine bin, aber dass ich nicht feststellen kann, welche. Für eine kritische Diskussion siehe Chihara 1972 und Hanson 1971.

6.5 Mystik und die Existenz Gottes?

Manchmal werden aus Gödels Theoremen recht fantastische Schlussfolgerungen gezogen. Es wurde sogar behauptet, dass Gödels Theoreme, wenn sie sie auch nicht gerade beweisen, so doch zumindest eine starke Stütze für Mystik oder die Existenz Gottes darstellen. Diese Interpretationen scheinen auf einem oder mehreren Missverständnissen zu beruhen, die bereits oben diskutiert wurden: Entweder wird angenommen, dass Gödel einen absolut unbeweisbaren Satz geliefert hat, oder dass Gödels Theoreme Platonismus oder Anti-Mechanismus implizieren, oder beides.

Weitere Diskussionen über die philosophischen Aspekte der Unvollständigkeitstheoreme finden sich bei Raatikainen 2005 und Franzén 2005.

Weiterführende Literatur

Eine Standardreferenz für die Unvollständigkeitssätze ist:

• Smoryński, C., 1977, „The incompleteness theorems“ (Die Unvollständigkeitssätze), in: Handbook of Mathematical Logic (Handbuch der mathematischen Logik), J. Barwise (Hrsg.), Amsterdam: North-Holland, S. 821–866 [online verfügbar].

Es gibt mehrere Einführungslehrbücher zur mathematischen Logik, die eine gute Darstellung der Unvollständigkeitssätze und verwandter Themen bieten, zum Beispiel:

• Boolos, G., and R. Jeffrey, 1989, Computability and Logic, 3^rd revised edition, Cambridge: Cambridge University Press.
• Enderton, H., 1972, A Mathematical Introduction to Logic, New York: Academic Press.
• Van Dalen, D., 2004, Logic and Structure, 4^th edition, Berlin: Springer.

Zwei Bücher, die sich mit den Unvollständigkeitssätzen befassen, sind:

• Smullyan, R., 1991, Gödel’s Incompleteness Theorems, Oxford: Oxford University Press.
• Smith, P., 2007, An Introduction to Gödel’s Theorems, Cambridge: Cambridge University Press.

Ein weiteres nützliches Buch über die Unvollständigkeitssätze und verwandte Themen ist:

• Murawski, R., 1999, Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Gödel’s Theorems. Dordrecht: Kluwer.

Ein umfassendes, weiterführendes Buch zu diesen Themen ist:

• Hájek, P. und Pudlák, P., 1993, Metamathematik der Arithmetik erster Ordnung, Berlin: Springer.

Ein weiteres nützliches Buch, das auch einige fortgeschrittenere Themen behandelt, ist:

• Franzén, T., 2004, Inexhaustibility: A Non-Exhaustive Treatment, Lecture Notes in Logic 16, ASL, Wellesley: A.K. Peters.

Die eher philosophischen Aspekte der Unvollständigkeitssätze werden in den folgenden beiden Quellen behandelt (Franzén bietet eine leicht verständliche, informelle und dennoch zuverlässige Erklärung der Unvollständigkeitssätze):

• Raatikainen, P., 2005, „On the Philosophical Relevance of Gödel’s Incompleteness Theorems“, Revue Internationale de Philosophie, 59: 513–534 [online verfügbar].
• Franzén, T., 2005, Gödels Theorem: Ein unvollständiger Leitfaden zu seiner Verwendung und seinem Missbrauch, Wellesley: A.K. Peters.

Die folgenden beiden Artikel befassen sich mit verschiedenen Aspekten des ersten Unvollständigkeitssatzes:

• Beklemishev, L. D., 2010, “Gödel incompleteness theorems and the limits of their applicability. I,” Russian Mathematical Surveys, 65: 857–898.
• Buldt, B., 2014, “The scope of Gödel’s first incompleteness theorem,” Logica Universalis, 8: 499–552.

Schließlich gibt es ein Open-Source-E-Book, das eine Darstellung der Unvollständigkeitssätze enthält:

• Zach, Richard, 2021, Incompleteness and Computability, e-Book published by the Open Logic Project.

Bibliografie

Auerbach, David, 1985, “Intensionality and the Gödel theorems,” Philosophical Studies, 48 (3):337–51.
–––, 1992, “How to say things with formalisms,” in Proof, Logic, and Formalization, M. Detlefsen (ed.), London: Routledge, 77–93 [available online].

Awodey, S. & A.W. Carus, 2003, “Carnap versus Gödel on Syntax and Tolerance,” in Logical Empiricism: Historical and Contemporary Perspectives, P. Parrini et al. (eds.), Pittsburgh: University of Pittsburgh Press, pp. 57–64 [available online].
–––, 2004, “How Carnap Could Have Replied to Gödel,” in S. Awodey and C. Klein (eds.), Carnap Brought Home: The View from Jena, LaSalle, IL: Open Court, pp. 203–223 [available online].

Barzin, M., 1940, “Sur la portée du théorème de M. Gödel,” Académie Royale de Belgique, Bulletin de la Classe des Sciences, Series 5, 26: 230–39.

Benacerraf, P., 1967, “God, the Devil, and Gödel,” The Monist, 51: 9–32 [available online].

Bezboruah, A. and J.C. Shepherdson, 1976, “Gödel’s Second Incompleteness Theorem for Q,” The Journal of Symbolic Logic, 41: 503–512.

Boolos, G., 1968, “Review of ‘Minds, Machines and Gödel’, by J.R. Lucas, and ‘God, the Devil, and Gödel’,” Journal of Symbolic Logic, 33: 613–15.
–––, 1990, “On ‘Seeing’ the Truth of Gödel Sentence,” Behavioral and Brain Sciences, 13: 655–656.
–––, 1995, “Introductory Note to *1951,” in Gödel 1995: 290–304.

Boolos, G. and R. Jeffrey, 1989, Computability and logic, 3rd revised edition, Cambridge: Cambridge University Press.

Carnap, R., 1934, Logische Syntax der Sprache, Vienna: Julius Springer.

Chihara, C., 1972, “On Alleged Refutations of Mechanism Using Gödel’s Incompleteness Results,” Journal of Philosophy, 69: 507–26.

Church, A., 1936a, “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, 58: 354–363. Republished in Davis 1965, 89–107.
–––, 1936b, “A Note on Entscheidungsproblem,” Journal of Symbolic Logic, 1: 40–41; correction, ibid., 101–102. Republished in Davis 1965, 110–115.

Cohen, P. J., 1963, “The Independence of the Continuum Hypothesis I,” Proceedings of the National Academy of Sciences, (U.S.A.), 50(6): 1143–48.
–––, 1964, “The Independence of the Continuum Hypothesis II,” Proceedings of the National Academy of Sciences, (U.S.A.), 51(1): 105–110.

Crocco, G., 2003, “Gödel, Carnap, and the Fregean Heritage,” Synthese, 137: 21–41.

Davis, M., 1965, The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Hewlett, NY: Raven Press.
–––, 1973, “Hilbert’s Tenth Problem is Unsolvable,” The American Mathematical Monthly, 80: 233–269.
–––, 1977, “Unsolvable Problems,” in Handbook of Mathematical Logic, J. Barwise (ed.), Amsterdam: North-Holland, pp. 567–594.
–––, 1990, “Is Mathematical Insight Algorithmic?” Behavioral and Brain Sciences, 13: 659–660.
–––, 1993, “How Subtle is Gödel’s Theorem? More on Roger Penrose,” Behavioral and Brain Sciences, 16: 611–612.

Davis, M., H. Putnam, and J. Robinson, 1961, “The decision problem for exponential diophantine equations,” Annals of Mathematics (2), 74(3): 425–436.

Dawson, J., 1985, “The Reception of Gödel’s Incompleteness Theorems,” PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1984, vol. II, pp. 253–271.
–––, 1997, Logical Dilemmas: The Life and Work of Kurt Gödel, Natick, MA: A. K. Peters.

Detlefsen, M., 1979, “On Interpreting Gödel’s Second Theorem,” Journal of Philosophical Logic, 8(1): 297–313.
–––, 1986, Hilbert’s Program: An Essay in Mathematical Instrumentalism, Dordrecht: Reidel.
–––, 1990, “On an Alleged Refutation of Hilbert’s Program Using Gödel’s First Incompleteness Theorem,” Journal of Philosophical Logic, 19(4): 343–377.
–––, 1995, “Wright on the Non-mechanizability of Intuitionist Reasoning,” Philosophia Mathematica, 3(1): 103–118.
–––, 2001, “What Does Gödel’s Second Theorem Say?” Philosophia Mathematica, 9: 37–71.

Dyson, V., J.P. Jones, and J.C. Shepherdson, 1982, “Some Diophantine Forms of Gödel’s Theorem,” Archiv für Mathematische Logik und Grundlagenforschung, 22: 51–60.

Ehrenfeucht, A. and S. Feferman, 1960, “Representability of recursively enumerable sets in formal theories”, Arch. Math. Logik Grundlag., 5(1–2), 37–41.

Feferman, S., 1960, “Arithmetization of Metamathematics in a General Setting,” Fundamenta Mathematicae, 49: 35–92.
–––, 1982, “Inductively Presented Systems and the Formalization of Meta-mathematics,” in Logic Colloquium ’80,

D. van Dalen et al. (eds.), Amsterdam: North-Holland, pp. 95–128.
–––, 1989a, “Finitary Inductively Presented Logics,” in Logic Colloquium ‘88, R. Ferro, et al. (eds.), Amsterdam: North-Holland, pp. 191–220. [available online]
–––, 1989b, “Infinity in Mathematics: Is Cantor Necessary?” Philosophical Topics, 17(2): 23–45.
–––, 1995, “Penrose’s Gödelian argument: A Review of Shadows of Mind, by Roger Penrose,” Psyche, 2 (7).
–––, 1997, “My Route to Arithmetization,” Theoria, 63: 168–181.

Finsler, P., 1926, “Formale Beweise und die Entscheidbarkeit,” Mathematische Zeitschrift, 25: 676–82.

Fitting, M., 2007, Incompleteness in the land of sets, London: College Publications. Series: Studies in logic ; v. 5.

Franks, C., 2009, The Autonomy of Mathematical Knowledge. Hilbert’s Program Revisited, Oxford: Oxford University Press.

Gaifman, H., 2006, “Naming and Diagonalization, From Cantor to Gödel to Kleene,” Logic Journal of the IGPL, 14: 709–728. [available online]

Gentzen, G., 1936, “Die Widerspruchsfreiheit der reinen Zahlentheorie,” Mathematische Annalen, 112: 493–565.

Gödel, K., 1931, “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,” Monatshefte für Mathematik Physik, 38: 173–198. English translation in van Heijenoort 1967, 596–616, and in Gödel 1986, 144–195.
–––, 1932, “Über Vollständigkeit und Widerspruchsfreiheit,” Ergebnisse eines mathematischen Kolloquiums, 3: 12–13. English translation “On Completeness and Consistency” in Gödel 1986: 235–7.
–––, 1933, “The Present Situation in Foundations of Mathematics,” in Gödel 1995: 45–53.
–––, 1934, “On Undecidable Propositions of Formal Mathematical Systems” (mimeographed lecture notes; taken by S. Kleene and J. Rosser), reprinted with corrections in Davis 1965, 41–81, and Gödel 1986, 346–371.
–––, 1935, “Review of Carnap 1934,” in Gödel 1986: 389.
–––, 1941, “In What Sense is Intuitionistic Logic Constructive?” in Gödel 1995: 189–200.
–––, 1944, “Russell’s Mathematical Logic,” in The Philosophy of Bertrand Russell, P. A. Schilpp (ed.), Evanston, Il.: Northwestern University, pp. 125–153. Reprinted in Gödel 1990: 119­–141.
–––, 1951, “Some Basic Theorems on the Foundations of Mathematics and their Implications” (Gibbs Lecture), in Gödel 1995: 304­–323.
–––, 1953/9, “Is Mathematics a Syntax of Language?,” lecture manuscript (two versions), in Gödel 1995: 334–362.
–––, 1963, “Note added 28 August 1963” (to Gödel 1931), in Gödel 1986: 195.
–––, 1986, Collected Works I. Publications 1929–1936, S. Feferman et al. (eds.), Oxford: Oxford University Press.
–––, 1990, Collected Works II. Publications 1938–1974, S. Feferman et al. (eds.), Oxford: Oxford University Press.
–––, 1995, Collected Works III. Unpublished Essays and Lectures, S. Feferman et al. (eds.), Oxford: Oxford University Press.

Goldfarb, W., 1995, “Introductory Note to *1953/9,” in Gödel 1995: 324–334.

Goldfarb, W. and T. Ricketts, 1992, “Carnap and the Philosophy of Mathematics,” in Science and Subjectivity, D.

Bell and W. Vossenkuhl (eds.), Berlin: Akademie Verlag, pp. 61–78.

Gómez Torrente, M., 2004, “The Indefinability of Truth in the Wahrheitsbegriff,” Annals of Pure and Applied Logic, 126(1–3): 27–37. [available online]

Goodstein, R., 1944, “On the Restricted Ordinal Theorem,” The Journal of Symbolic Logic, 9: 33–41.

Grelling, K., 1937, “Gibt es eine Gödelsche Antinomie?,” Theoria, 3: 297–306.

Hanson, W.H., 1971, “Mechanism and Gödel’s theorems,” The British Journal for the Philosophy of Science, 22: 9–16.

Hellman, G., 1981, “How to Gödel a Frege-Russell: Gödel’s Incompleteness Theorems and Logicism,” Nous, 15: 451–468.

Helmer, O., 1938, “Perelman versus Gödel,” Mind, 46: 58–60.

Henkin, L., 1952, “Problem,” The Journal of Symbolic Logic, 17: 160.
–––, 1962, “Are Mathematics and Logic Identical?” Science, 138: 788–794.

Hilbert, D., 1928, “Die Grundlagen der Mathematik,” Abhandlungen aus dem Mathematischen Seminar der Hamburgischen Universität, 6: 65–85. English translation in van Heijenoort 1967.

Hilbert, D. and P. Bernays, 1939, Grundlagen der Mathematik, vol. 2, Berlin: Springer.

Jeroslow, R., 1973, “Redundancies in the Hilbert-Bernays Derivability Conditions for Gödel’s Second Incompleteness Theorem,” Journal of Symbolic Logic, 38: 359–367.

Kaye, R., 1991, Models of Peano Arithmetic (Oxford Logic Guides), Oxford: Clarendon Press.

Kirby, L. and J. Paris, 1982, “Accessible Independence Results for Peano Arithmetic,” Bull. London. Math. Soc., 14: 285–93.

Kleene, S.C., 1936, “General recursive functions of natural numbers,”, Mathematische Annalen 112(1): 727–742.
–––,1937a, “Review of Perelman 1936,” Journal of Symbolic Logic, 2: 40–41.
–––, 1937b, “Review of Helmer 1937,” Journal of Symbolic Logic, 2: 48–49.
–––, 1986, “Introductory note to 1930b, 1931 and 1932b”, in Gödel 1986, pp. 126–141.

Kreisel, G., 1953, “On a Problem of Henkin’s,” Proc. Netherlands Acad. Sci. 56: 405–406.
–––, 1958, “Mathematical significance of consistency proofs,” The Journal of Symbolic Logic, 23: 159–182.
–––, 1967, “Mathematical Logic: What Has it Done For the Philosophy of Mathematics?” in Bertrand Russell: Philosopher of the Century, R. Schoenman (ed.), London: George Allen and Unwin.

Kruskal, J.B., 1960, “Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s Conjecture,” Transactions of the American Mathematical Society, 95 (2): 210–225.

Lindström, P., 2001, “Penrose’s New Argument,” Journal of Philosophical Logic, 30(3): 241–250.

Lucas, J. R., 1961, “Minds, Machines, and Gödel,” Philosophy, 36(137): 112–137 [available online].
–––, 1996, “Minds, Machines, and Gödel: A Retrospect,” in Machines and Thought. The Legacy of Alan Turing, Vol. 1, P.J.R. Millican and A. Clark (eds.), Oxford: Oxford University Press, 103–124.

Löb, M. H., 1955, “Solution of a Problem of Leon Henkin,” Journal of Symbolic Logic, 20: 115–118.

Mancosu, P., 1999, “Between Vienna and Berlin: The Immediate Reception of Gödel’s Incompleteness Theorems,” History and Philosophy of Logic, 20: 33–45.

Martin, D., 1977, “Descriptive Set Theory: Projective Sets,” in Handbook of Mathematical Logic, J. Barwise (ed.), Amsterdam: North-Holland, 783–815.

Martin, D. and Steel, J., 1988, “Projective Determinacy,” Proceedings of the National Academy of Sciences, (U.S.A.), 85: 6582–86.
–––, 1989, “A Proof of Projective Determinacy,” Journal of the A.M.S., 2: 71–125.

Matiyasevich, Y., 1970, “Diofantovost’ perechislimykh mnozhestv,” Dokl. Akad. Nauk SSSR, 191(2): 297–282 (Russian). (English translation, 1970, “Enumerable sets are Diophantine,” Soviet Math. Dokl., 11(2): 354–358.)
–––, 1993, Hilbert’s Tenth Problem, Cambridge, MA: MIT Press.

Milne, P., 2007, “On Gödel Sentences and What They Say,” Philosophia Mathematica, 15: 193–226.

Montague, R., 1962, “Theories Incomparable with Respect to Relative Interpretability,” The Journal of Symbolic Logic, 27: 195–211.

Murawski, R., 1998, “Undefinability of Truth. The Problem of Priority: Tarski vs. Gödel,” History and Philosophy of Logic, 19: 153–160.
–––, 1999, Recursive Functions and Metamathematics: Problems of Completeness and Decidability, Gödel’s Theorems, Dordrecht: Kluwer.

Musgrave, A., 1977, “Logicism Revisited,” British Journal for the Philosophy of Science, 28: 99–127.

Nagel, E. and J.R. Newman, 1958, Gödel’s Proof, New York: New York University Press.

Odifreddi, P., 1989, Classical Recursion Theory (Oxford Logic Guides), Amsterdam: North-Holland.
Paris, J. and L. Harrington, 1977, “A Mathematical Incompleteness in Peano Arithmetic,” in Handbook of

Mathematical Logic, J. Barwise (ed.), Amsterdam: North-Holland, pp. 1133–1142 [available online].
Paris, J. and L. Kirby, 1978, “Sn
Collection Schema in Arithmetic,” in Logic Colloquium ’77, A. McIntyre et al. (eds.), Amsterdam: North-Holland, pp. 199–209.

Parsons, C., 1970, “On Number Choice Schema and its Relation to Induction,” in Intuitionism and Proof Theory, Kino et al. (eds.), Amsterdam: North-Holland, pp. 459–473.

Penrose, R., 1989, The Emperor’s New Mind: Concerning Computers, Minds, and the Laws of Physics, New York: Oxford University Press.
–––, 1994, Shadows of the Mind: A Search for the Missing Science of Consciousness, New York: Oxford University Press
–––, 1995, “Beyond the Doubting of a Shadow: A Reply to Commentaries of Shadows of the Mind,” Psyche, Vol 2.
–––, 1997, “On understanding understanding”, International Studies in the Philosophy of Science, 11: 7–20.

Perelman, C., 1936, “L’Antinomie de M. Gödel,” Académie Royale de Belgique. Bulletin de la Classe des Sciences (Series 5), 22: 730–36.

Piccinini, G., 2003, “Alan Turing and the Mathematical Objection,” Minds and Machines, 13: 23–48.
Post, E., 1941, “Absolutely Unsolvable Problems and Relatively Unsolvable Propositions: Account of an Anticipation,” published in Davis 1965, 338–433.

Presburger, M., 1929, “Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt,” Sprawozdanie z I Kongresu Matematyków Krajów Slowiańskich, (= Comptes-rendus du I Congrès Mathématiciens des Pays Slaves), Warsaw, pp. 92–101. English translation, 1991,“On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation,” History and Philosophy of Logic, 12(2): 225–232.

Pudlák, P., 1996, “On the Length of Proofs of Consistency,” Collegium Logicum, Annals of the Kurt-Gödel-Society, 2: 65–86.
–––, 1999, “A Note on Applicability of the Incompleteness Theorem to Human Mind,” Annals of Pure and Applied Logic, 96: 335–342.

Putnam, H., 1960, “Minds and machines,” in Dimensions of Mind, S. Hook (ed.), New York: New York University Press. Reprinted in H. Putnam, 1975, Mind, Language, and Reality. Philosophical Papers, Vol 2, Cambridge:Cambridge University Press, pp. 325–341.
–––, 1975, “What is Mathematical Truth?” Historia Mathematica, 2: 529–545. Reprinted in H. Putnam, 1975, Mathematics, Matter and Method. Philosophical Papers, Vol 1, Cambridge: Cambridge University Press, pp. 60–78.

Quine, W.V. and J.S. Ullian, 1978, The Web of Belief, 2nd ed., New York: Random House.

Raatikainen, P., 2005, “On the Philosophical Relevance of Gödel’s Incompleteness Theorems,” Revue Internationale de Philosophie, 59: 513–534.

Ramsey, F. P., 1930, “On a Problem of Formal Logic,” Proceedings of the London Mathematical Society, series 2, 30: 264–286.

Ricketts, T., 1995, “Carnap’s Principle of Tolerance, Empiricism, and Conventionalism,” in Reading Putnam, P. Clark & B. Hale (eds.), Cambridge: Blackwell, pp. 176–200.

Rodríguez-Consuegra, F., 1993, “Russell, Gödel and Logicism,” in Philosophy of Mathematics, J. Czermak (ed.), Vienna: Hölder-Pichler-Tempsky, pp. 233–42. Reprinted in, 1998, Bertrand Russell: Critical Assessments, A.Irvine (ed.), vol. 2: Logic and mathematics, London: Routledge, pp. 320–29.

Roeper, P., 2003, “Giving an Account of Provability within a Theory,” Philosophia Mathematica, 11: 332–340.

Rosser, J. B., 1936, “Extensions of Some Theorems of Gödel and Church,” Journal of Symbolic Logic, 1: 87–91.
–––, 1938, “Review: Kurt Grelling, Gibt es eine Godelsche Antinomie? [Grelling 1937/8],” Journal of Symbolic Logic, 3(2): 86.

Searle, J., 1997, “Roger Penrose, Kurt Gödel, and the Cytoskeletons,” in J. Searle: Mystery of Consciousness, New York: New York Review of Books, pp. 55–93.

Shapiro, S., 1998, “Incompleteness, Mechanism, and Optimism,” Bulletin of Symbolic Logic, 4: 273–302.
–––, 2003, “Mechanism, Truth and Penrose’s New Argument,” Journal of Philosophical Logic, 32(1): 19–42.

Simpson, S.G., 1985, “Nonprovability of Certain Combinatorial Properties of Finite Trees,” in Harvey Friedman’s Research on the Foundations of Mathematics, L. Harrington et al. (eds.), Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, pp. 87–117
–––, 1999, Subsystems of Second Order Arithmetic, Berlin: Springer.

Skolem, T., 1930, “Über einige Satzfunktionen in der Arithmetik,” Skrifter utgitt av Det Norske Videnskaps-Akademi i Oslo, I, no. 7, 1–28. Reprinted in T. Skolem, 1970, Selected Works in Logic, (J. Fenstad, editor), Oslo: Universitetsforlaget, pp. 281–306.

Smoryński, C., 1977, “The Incompleteness Theorems,” in Handbook of Mathematical Logic, J. Barwise (ed.), Amsterdam: North-Holland, pp. 821–865.
–––, 1981, “Fifty Years of Self-reference in Arithmetic,” Notre Dame Journal of Formal Logic, 22(4): 357–374.
–––, 1991, “The Development of Self-reference: Löb’s Theorem,” in Perspectives on the History of Mathematical Logic, T. Drucker (ed.), Birkhauser, pp. 111–133.

Smullyan, R., 1992, Gödel’s Incompleteness Theorems, Oxford: Oxford University Press.

Solovay, R.M., 1970, “A Model of Set Theory in which Every Set of Reals is Lebesgue Measurable,” Annals of Mathematics, 92: 1–56.

Sternfeld, R., 1976, “The Logistic Thesis,” in Studien zu Frege/Studies on Frege I, M. Schirn (ed.), Stuttgart-Bad Cannstatt: Frommann-Holzboog, pp. 139–160.

Tarski, A., 1948, A Decision Method for Elementary Algebra and Geometry, manuscript. Santa Monica, CA: RAND Corp., 1948. Republished as A Decision Method for Elementary Algebra and Geometry, 2nd ed. Berkeley, CA: University of California Press, 1951.

Tarski, A., A. Mostowski, and R.M. Robinson, 1953, Undecidable Theories, Amsterdam: North-Holland.

Tennant, Neil, 2008, “Carnap, Gödel, and the Analyticity of Arithmetic”, Philosophia Mathematica, 16: 100–112.

Turing, A.M., 1936–7, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, Series 2, 42: 230–265; correction, ibid., 43: 544–546. Republished in Davis 1965, 115–154.

Van Heijenoort, J. (ed.), 1967, From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, Cambridge, MA: Harvard University Press.

Visser, A., 2011, “Can We Make the Second Incompleteness Theorem Coordinate Free,” Journal on Logic and Computation, 21(4): 543–560.

Woodin, H., 1988, “Supercompact Cardinals, Sets of Reals, and Weakly Homogeneous Trees,” Proceedings of the National Academy of Sciences, (U.S.A.), 85: 6587–91.

Wright, C., 1994, “About ‘The Philosophical Significance of Gödel’s Theorem’: Some Issues,” in The Philosophy of Michael Dummett, B. McGuinness and G. Oliveri (eds.) Dordrecht: Kluwer, pp. 167–202.
–––, 1995, “Intuitionists are not (Turing) Machines,” Philosophia Mathematica, 3: 86–102.

Zach, R., 2005, “Paper on the Incompleteness Theorems,” in Landmark Writings in Western Mathematics, I. Grattan-Guinness (ed.), Amsterdam: Elsevier, pp. 917–2

Weitere Internetressourcen

Artikel und Rezensionen von Sol Feferman zu Gödels Unvollständigkeitssatz:

• Rezension von Rebecca Goldsteins The Proof and Paradox of Kurt Gödel, in London Review of Books, 28(3) (9. Februar 2006).
• Der Einfluss der Unvollständigkeitssätze auf die Mathematik, Vorabdruck, Notices American Mathematical Society, 53(4) (April 2006): 434–439.
• Die Natur und Bedeutung von Gödels Unvollständigkeitssatz, Vortrag für das Gödel-Jubiläumsprogramm des Princeton Institute for Advanced Study, 17. November 2006.
• Gödels Unvollständigkeitssätze, freier Wille und mathematisches Denken, Vorabdruck des Artikels in Free Will and Modern Science, R. Swinburne (Hrsg.), Oxford: Oxford University Press, 2011, 102–122.
• Penroses Gödelsches Argument, Vorabdruck der Rezension, erschienen in PSYCHE, 2 (1996): 21–32.

Sonderausgabe (April 2006) der Notices of the American Mathematical Society (Band 53, Ausgabe 4) zum hundertsten Geburtstag von Kurt Gödel mit einer Sammlung von Artikeln über Gödel, sein Werk und dessen Einfluss auf die Mathematik.