7. Die Unvollständigkeitssätze

Es gibt hier eine kleine Unsauberkeit in der Notation. Die Buchstaben „\(t\)“ und „\(u\)“ sind selbst keine Zeichen der Sprache von PA, sondern vielmehr Buchstaben, die wir (in unserer Metasprache) verwenden, um Ausdrücke der Sprache PA zu bezeichnen. Wenn wir zum Beispiel „der Ausdruck \((t+u)\)“ sagen, dann meinen wir nicht den Ausdruck, der aus den fünf Zeichen „\((\)“, „\(t\)“, „\(+\)“, „\(u\)“ und „\()\)“ besteht, sondern wir meinen das Ergebnis, das wir erhalten, wenn wir das Zeichen „\(+\)“ zwischen die Ausdrücke, die wir mit „\(t\)“ und „\(u\)“ bezeichnen, setzen und dann Klammer außen herum schreiben. Der so erhaltene Ausdruck kann mehr als fünf Zeichen enthalten, und sein zweites Zeichen ist nicht der Buchstabe „\(t\)“, sondern das erste Zeichen des Ausdrucks, den „\(t\)“ bezeichnet.

Es ist wichtig zu beachten, dass wir mit Einführung dieser Schreibweise nicht die Definition der Sprache von PA ändern. Zum Beispiel ist der Ausdruck \(S^{4}0\) kein Term der Sprache von PA. Es ist eine Abkürzung in unserer Metasprache, die den Ausdruck \(SSSS0\) bezeichnet, und nur dieser letzte Ausdruck ist tatsächlich ein Term der Sprache von PA.

Für die Definition von Substituierbarkeit und einer Erläuterung, warum diese Einschränkung notwendig ist, siehe Enderton (2001, S. 113). Wir werden diese Regel vor allem benutzen, wenn \(t\) ein Zahlzeichen ist, und Zahlzeichen sind in allen Formeln für alle Variablen substituierbar.

Anm. d. Übers.: Dieser stammt von Leibniz.

Es gibt einen Unterschied zwischen einer natürlichen Zahl \(n\), die ein Element von \(\mathbb{N}\) ist, und der Folge der Länge \(1\), deren einziges Glied \(n\) ist, die wir als \(\langle n\rangle\) schreiben würden und die ein Element von \(\mathbb{N}^{1}\) ist. Streng genommen besagt Definition 7.6, dass \(P(x_{1})\) nicht die Menge der Primzahlen, sondern vielmehr die Menge \(\{\langle n\rangle\in\mathbb{N}^{1}:n\text{ ist eine Primzahl}\}\) repräsentiert. Wir werden diese Unterscheidung jedoch meistens ignorieren und von einer Teilmenge von \(\mathbb{N}\) sagen, dass sie repräsentierbar ist, wenn die entsprechende Teilmenge von \(\mathbb{N}^{1}\) repräsentierbar ist.

Ein Beweis ist in vielen Logikbüchern zu finden. Siehe beispielsweise Enderton (2001, S. 220f).

Für eine genaue Definition siehe Cutland (1980).

Anm. d. Übers.: Dieses Lemma wird auch als Fixpunktlemma bezeichnet.

Der Leser könnte sich über die Tatsache wundern, dass \(\mathfrak{M}\) nicht isomorph zum Standardmodell sein muss, da wir in Kap. 2 gesagt haben, die Peano-Axiome seien kategorisch; anders gesagt, dass alle Modelle der Peano-Axiome isomorph seien. Die Erklärung für diesen offensichtlichen Widerspruch ist, dass die Peano-Axiome aus Kap. 2 in zweitstufiger Logik formuliert waren; insbesondere enthält das Induktionsaxiom (22)(vi) aus Kap. 2 Quantifikation über alle Begriffe. In diesem Kapitel arbeiten wir jedoch mit den erstufigen Axiomen, sodass wir uns die formalen Systeme logischer Axiome und Schlussregeln der Logik erster Stufe, die in Logikbüchern zu finden sind, zunutze machen können. Die erststufige Version des Induktionsaxioms in Definition 7.4(viii) ist schwächer als das zweitstufige Induktionsaxiom aus Kap. 2, weil die zweitstufige Version für alle Begriffe gilt, wohingegen die erststufige Version nur für Begriffe gilt, die durch eine Formel in der erststufigen Sprache der Zahlentheorie definierbar sind. Die zweitstufigen Peano-Axiome aus Kap. 2 sind kategorisch, aber die erststufige Theorie PA aus diesem Kapitel ist es nicht. Der Leser könnte sich nun fragen, warum wir dann nicht entschieden haben, in diesem Kapitel die zweitstufige Logik zu verwenden. Die Antwort ist, dass es kein formales System von Axiomen und Schlussregeln gibt, in dem man die logischen Folgerungen einer Menge von Axiomen, die in einer Sprache der Logik zweiter Stufe formuliert sind, herleiten kann. Tatsächlich kann der Erste Unvollständigkeitssatz verwendet werden, um zu zeigen, dass es ein solches formales System nicht geben kann. Für ein stärkeres Resultat, siehe Satz 41C auf S. 286 in Enderton (2001).

Dieser Satz wird üblicherweise dem polnischen Logiker Alfred Tarski (1902–1983) zugeschrieben, der diesen im Jahr 1933 als Erster veröffentlichte. Tarski betonte jedoch selbst (Tarski 1983, S. 247f, 277f), dass der Satz in Gödels Artikel von 1931 angedeutet wurde, und tatsächlich formulierte und bewies Gödel den Satz explizit in einem Brief an Zermelo im Jahr 1931 (Gödel 2010).

Boolos (1979).

Diese Übung basiert auf dem Beweis in Boolos (1989). Man könnte sie mit Übung 6.​3 aus Kap. 6 vergleichen, die auf Berrys Antinomie beruht.