Logik und Beweisbarkeit - Einzelansicht

Kann man alle wahren arithmetischen Aussagen (z.B.(?): es gibt unendlich viele Primzahlzwillinge) formal beweisen? Kurt Gödel hat mit seinen Unvollständigkeitssätzen gezeigt, dass das nicht geht. In dieser Vorlesung werden wir uns ansehen, was geht und was nicht geht, und warum es so ist.

Wir beginnen mit dem einfachen Fall der Aussagenlogik, gehen dann über die variablenfreie Arithmetik zur ∑₁-Arithmetik (das ist der Teil der Arithmetik ohne unbeschränkte Allquantoren).Für diese Logiken werden wir Vollständigkeitssätze für entsprechende Beweissysteme zeigen.

Damit haben wir gesehen, was geht. Weiter geht's mit dem, was nicht geht. Dafür brauchen wir als Fundament etwas Berechenbarkeitstheorie und verbinden dann – etwas verblüffend – die Begriffe Berechnung und Beweis. Auf diesem Fundament ist der Beweis des Gödelschen Unvollständigkeitssatzes recht einfach.

Zum Abschluss werden wir noch in die Original-Arbeit von Gödel schauen und sehen, was er anders gemacht hat.

• Gödel, K.: Über formal unentscheidbare Sätze der Pricipia Mathematica und verwandter Systeme I. Monatshefte der Mathematik und Physik, 38: 173-198, 1931.
• van Dalen, D.: Logic and Structure. Springer Verlag, 2004.
• Smith, P.: An Introduction to Gödel's Theorems. Cambridge University Press, 2013.
• Cutland, N.J.: Computability. Cambridge University Press, 1980.
• Wolf, R.S.: A Tour Through Mathematical Logic. The Mathematical Association of America, 2005.

• Formale Aussagenlogik und formale Arithmetik
• Formales Beweisen mittels Natürlichem Schließen
• Vollständigkeitssatz für Natürliches Schließen in der Aussagenlogik
• Vollständigkeitssatz für Natürliches Schließen mit den Robinson-Axiomen in der ∑₁-Arithmetik
• Berechenbarkeitstheorie: entscheidbare und semi-entscheidbare Mengen
• Semi-entscheidbare Mengen sind genau die durch ∑₁-Formeln beschriebenen Mengen
• Unvollständigkeitssätze von Gödel