240035 Proseminar Grundlagen der Mathematik: Logik, Beweistheorie und Mengenlehre (PS) (SoSe 2017)

Was ist eine Aussage? und wann ist eine Aussage wahr?

Wie üblich, läßt die Mathematik Wesensfragen unbeantwortet. Aber sie kann Modelle beisteuern, die wesentliche Aspekte der Situation erfassen. Formale Logik liefert Modelle für Sätze und Bedeutungen. Aufbauend darauf lassen sich dann die Begriffe "Aussage" und "wahr" angehen.

Ein Blick in den Spiegel zeigt, daß wir als Mathematiker ständig Aussagen formulieren und beweisen. Es drängt sich also auf, das entwickelte Modell auf die Aussagen der Mathematik anzuwenden, zum Beispiel um zu klären, was ein Beweis ist. Danach läßt sich unter anderem das interessantes Ergebnis formulieren, daß Wahrheit und Beweisbarkeit nicht zusammenfallen: jedes Axiomensystem für die Mengenlehre ist entweder unvollständig (es gibt wahre Aussagen, die keinen Beweis erlauben) oder widersprüchlich (die Axiome implizieren einen Widerspruch und damit jede beliebige Aussage).

In diesem Themenkreis bewegt sich die Veranstaltung. Stichworte sind:

• Aussagenlogik und Prädikatenlogik
• Axiomensysteme, Theorien und Modelle
• Erfüllbarkeit und Widerspruchsfreiheit
• logische Kompaktheit
• Widerspruchsfreiheit und Vollständigkeit der Prädikatenlogik erster Stufe
• Unvollständigkeit der Arithmetik, der Mengenlehre, der Prädikatenlogik zweiter Stufe

NEU: Vorbesprechung am 20.2. ab 16:15 in U2-113

geplante Vorträge:

19.4. Aussagenlogik: Syntax, Semantik, Kompaktheit und Entscheidbarkeit (2, 1-17) (1, 39-43) (4, A-1)

26.4. Aussagenlogischer Kalkül: Korrektheit und Vollständigkeit (2, 18-24) (1, 61-74) (4, A-1)

03.5. Prädikatenlogik erster Stufe: Syntax, Semantik, Erfüllbarkeit und Allgemeingültigkeit (3, 3-16) (2, 33-57) (4, A-1)

10.5. Prädikatenlogik erster Stufe: Beweiskalkül nach Gentzen und Schnittelimination (5, 187-197) (7, 103-118) (4, D-2)

17.5. Prädikatenlogik erster Stufe: Vollständigkeit, Kompaktheit, Satz von Löwenheim-Skolem (3, 23-33) (4, A-1)

24.5. Prädikatenlogik erster Stufe: Schnittelimination (modelltheoretisch) (3, 35-41) (12, 52-65)

31.5. Prädikatenlogik erster Stufe: Satz von Herbrand (modelltheoretisch) (3, 43-49) (2, 106-111)

07.6. Prädikatenlogik erster Stufe: Satz von Herbrand (beweistheoretisch) (7, 132-140) (4, D-2)

14.6. Prädikatenlogik zweiter Stufe: Syntax und Semantik, Kategorizität (8, 140-146)

21.6. Arithmetik: Kategorizität in der Prädikatenlogik zweiter Stufe (8, 147-152)

28.6. Arithmetik: Nichtkategorizität in der Prädikatenlogik erster Stufe (8, 152-157)

05.7. Prädikatenlogik zweiter Stufe: Nichtkompaktheit und Unvollständigkeit (9, 172-176) (10, 348-354)

12.7. Zweiter Unvollständigkeitssatz: Rekursive Funktionen (15) (2, 169-175) (4, D-1)

19.7. Zweiter Unvollständigkeitssatz: Gödelisierung (15) (2, 176-188) (4, D-1)

26.7. Zweiter Unvollständigkeitssatz: Beweis (15) (2, 189-199) (4, D-1)

Requirements for participation, required level

Lineare Algebra I und II
Analysis I und II

Bibliography

[1] W. Rautenberg: Klassische und nichtklassische Aussagenlogik
[2] W. Rautenberg: Einführung in die mathematische Logik
[3] M. Ziegler: Mathematische Logik
[4] J. Barwise: Handbook of Mathematical Logic
[5] D. van Dalen: Logic and Structure
[6] G. Gentzen: Untersuchungen über das Logische Schließen I und II (Math. Z. 1935)
[7] L. Heindorf: Elementare Beweistheorie
[8] H. Hermes: Einführung in die mathematische Logik
[9] H. Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit
[10] W. Essler / E. Brendel: Grundzüge der Logik II - Klassen . Relationen . Zahlen
[11] P. Halmos: Naive Mengenlehre
[12] W. Pohlers: Proof Theory - The First Step into Impredicability
[13] W. Markwald: Einführung in die formale Logik und Metamathematik
[14] D. Hilbert, W. Ackermann: Grundzüge der theoretischen Logik
[15] K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme