Zeit: Mo von 9:45 bis 11:15 Uhr

Ort: HS 11, Oskar-Morgenstern-Platz 1, 2. Stock.

Die Vorlesung bietet eine erste Einführung in die mathematische Logik: Syntax und Semantik der Prädikatenlogik, formaler Beweisbegriff, Gödelscher Vollständigkeitssatz, Grundzüge der Berechenbarkeitstheorie, erster Gödelscher Unvollständigkeitssatz. Die Vorlesung folgt dem unten angegebenen Buch von Martin Ziegler.

Vera Fischer gibt die Vorlesung begleitende Übungen.

1. Vorlesung 07.03: Aussagenlogik. Skript pdf.
2. Vorlesung 14.03: Syntax und Semantik der Prädikatenlogik Seiten 2-9 (in Zieglers Buch), bis Koinzidenzlemma (Satz 2.1) ohne Beweis.
3. Vorlesung 04.04: S.9-13, Beweis Koinzidenzlemma (Satz 2.1), Substitutionslemma (Lemma 2.2), Allgemeingültigkeit, Zweites Koinzidenzlemma (siehe Lemma S.13).
4. Vorlesung 11.04: S.13-19, Tautologien, Hilbertkalkül, Korrektheitssatz (Richtung von links nach rechts im Vollständigkeitssatz S.17).
5. Vorlesung 18.04: Schritte 1 und 2 des Beweises von Satz 4.3 (S.19,20), Korollare Vollständigkeitssatz allgemeine Form und Kompaktheitssatz (Folgerungen 4.4 und 4.5, S.24).
6. Vorlesung 25.04: Beweis Satz 4.3 (S.21-23), Löwenheim-Skolem abwärts (Folgerung 4.5) und aufwärts (pdf.).
7. Vorlesung 02.05: Registermaschinen und Flussdiagramme (S.67,68,70,71).
8. Vorlesung 09.05: Rekursive und primitiv rekursive Funktionen (S.69), Beipiele (Lemma 13.1), rekursive Funktionen sind berechenbar (Satz 12.1).
9. Vorlesung 23.05: rekursive und primitiv rekursive Relationen (S.74,75), Kodierung von Folgen (Lemma 13.6), Gödelisierung von Maschinen (S.77)
10. Vorlesung 30.05: rekursiv gleich berechenbar (Beweis Satz 12.1), Kleene Prädikat, Kleene Normalform (S.77-79), rekursiv aufzählbare Mengen (S.80,81).
11. Vorlesung 06.06: arithmetische Mengen, Gödelsche Beta-Funktion, rekursive Funktionen sind arithmetisch.
12. Vorlesung 13.06: Gödelisierung prädikatenlogischer Syntax, effektiv axiomatisierbare und entscheidbare Theorien, Repräsentierbarkeit.
13. Vorlesung 20.06: Tarski's Satz über die Undefinierbarkeit der Wahrheit, Erster Gödelscher Unvollständigkeitssatz.

Skript ab Vorlesung 11: pdf

Literatur

• Martin Ziegler, Mathematische Logik, Reihe Mathematik Kompakt, Birkhäuser Verlag, 2010.
• Martin Ziegler, Mathematische Logik, Vorlesungsskript SS00 (hier)
• Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas: Einführung in die mathematische Logik, Spektrum Verlag, 5. Auflage, 2007.