Mathematische Logik II

WS 2014/15

Aktuelles

  • Ein Skript zur Modallogik gibt es hier.
  • Zusätzliches Material zur Fixpunktlogik gibt es auch im Skript zur Vorlesung "Algorithmische Modelltheorie" (insbesondere Kapitel 4 und 5).
  • Bitte schreiben Sie zur Vereinbarung eines Prüfungstermins eine E-Mail an Prof. Grädel. Sollten Sie besondere Terminwünsche haben, geben Sie diese bitte an.
  • Am Donnerstag dem 5.2. fällt die Vorlesung wegen dem Gedenkkolloquium zu Ehren von Prof. Berthold Vöcking aus.
  • Am 10.12 und 11.12. finden keine Vorlesungen statt.
  • Das erste Übungsblatt ist online. Die Übungen können in Gruppen bearbeitet werden (max. 3 Studenten). Geben Sie Ihre Lösungen bis Mittwoch am Lehrstuhl oder in der Vorlesung ab.

Termine

Art Termin Ort   Veranstalter
V4 Mi 10:15 – 11:45 Hörsaal III Beginn 15. Oktober E. Grädel
Do 14:15 – 15:45 Hörsaal III Beginn 16. Oktober E. Grädel
Ü2 Do 16:15 – 17:45 AH I Beginn 23. Oktober F. Reinhardt

Übungen

Inhalt

Diese Vorlesung baut auf der Einführungsvorlesung Mathematische Logik auf, in der bereits die Grundlagen der Aussagenlogik, Modallogik und der Prädikatenlogik vermittelt wurden. In Mathematischer Logik II werden die Studenten mit fortgeschrittenen Methoden sowie einigen fundamentalen Errungenschaften der mathematischen Logik im 20. Jahrhundert vertraut gemacht.

In der Vorlesung werden hauptsächlich zwei Gebiete der mathematischen Logik vertieft: Mengenlehre und Modelltheorie.

Mengenlehre als Grundsäule der Mathematik

Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können.
(David Hilbert, 1926)

Die Mathematik beruht grundlegend auf dem Begriff einer Menge. Was sind jedoch Mengen? Naive Definitionen führen in der Regel zu Widersprüchen wie z.B. dem Russellschen Paradoxon der Menge aller Mengen, die sich nicht selbst enthalten.

Wir werden uns detailliert mit dem Axiomensystem ZFC (Zermelo-Fraenkel mit Auswahlaxiom) für die Mengenlehre auseinandersetzen und versuchen, die sich daraus ergebende Welt der Mengen (Cantors Paradies) zu verstehen. Insbesondere werden wir auf Ordinal- und Kardinalzahlen (wie kann man im Unendlichen weiterzählen und wie kann man im Unendlichen rechnen?), transfinite Induktion und Rekursion sowie die Bedeutung des Auswahlaxioms und der Kontinuumshypothese eingehen.

Das erklärte Ziel der durch Hilberts Programm beschriebenen Bestrebungen lag Anfang des 20. Jahrhunderts darin, die Mathematik auf ein starkes widerspruchsfreies und damit konsistentes Fundament zu stellen. Gödel zeigte jedoch mit seinen Unvollständigkeitssätzen, dass dieses Unterfangen unmöglich ist: Es ist nicht beweisbar, dass die Mathematik konsistent ist, es sei denn, sie wäre inkonsistent.

Einführung in die Modelltheorie

Model theorists are mad tailors: they are making all the possible clothes hoping to produce also something suitable for dressing.
(after Stanislav Lem)

Als Modelltheorie bezeichnet man die Untersuchung mathematischer Strukturen mittels Logik. In diesem Teil der Vorlesung werden die zentralen Konstruktionen und Werkzeuge vorgestellt, die in der Modelltheorie eine Rolle spielen wie z.B. Kompaktheit, Typen und elementare Erweiterungen. Dabei werden wir uns auf folgende Fragestellungen konzentrieren:

  • Gegeben sei eine first-order Theorie T, wie sehen die Modelle von T aus?
    Wir werden zeigen, wie sich einerseits sehr reichhaltige Modelle, also Modelle die alles umfassen, was von T nicht explizit verboten wird, andererseits aber auch sehr sparsame Modelle von T konstruieren lassen, die nichts enthalten, was nicht von T explizit gefordert wird. In vielen dieser Konstruktionen spielt der Kompaktheitssatz eine zentrale Rolle.
  • Wie ausdrucksstark ist eine Logik?
    Wir werden Logiken vorstellen, die stärker sind als die Prädikatenlogik erster Stufe, wie z.B. inifinitäre Logik oder Fixpunktlogiken, die eng mit Induktions- bzw. Rekursionsmechanismen verknüpft sind und vielfältige Anwendungsmöglichkeiten von der Mengenlehre bis hin zur Informatik haben. Um die Ausdrucksstärke dieser Logiken besser charakterisieren zu können, werden wir uns eingehend mit Ehrenfeucht-Fraïssé-Spielen für diese Logiken befassen.

Material

Sie können hier das Skript zur Mengenlehre von Achim Blumensath herunterladen. Ferner steht jeweils ein kurzes Skriptum mit Material zu Modelltheorie beziehungsweise Fixpunktlogik zur Verfügung. Bitte beachten Sie, dass der Teil zu Fixpunktlogiken die Abschnitte über inflationäre beziehungsweise partielle Fixpunktlogiken noch nicht enthält. Wir verweisen für diese Teile vorerst auf [9].

Literatur

[1] E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer Verlag, 1997.
[2] A. Blumensath. Set Theory. In Logic and Algebra. Unpublished, 2008.
[3] C. Chang and J. Keisler. Model Theory. North-Holland, 1990.
[4] R. Cori and D. Lascar. Logique mathématique. Masson, 1994.
[5] B. Cooper. Computability Theory. Chapman Hall/CRC Mathematics, 2003.
[6] K. Doets. Basic Model Theory. CSLI Publications, 1996.
[7] H. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1999.
[8] H. Ebbinghaus, J. Flum, and W. Thomas. Einführung in die mathematische Logik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1986.
[9] H. Ebbinghaus. Einführung in die Mengenlehre. BI Wissenschaftsverlag, 1994.
[10] E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema, and S.Weinstein. Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[11] M. Fitting. First-order logic and automated theorem proving. Springer, 1996.
[12] O. Grumberg, E. Clarke, and D. Peled. Model Checking. MIT Press, 1999.
[13] W. Hodges. A shorter model theory. Cambridge University Press, 1997.
[14] R. Lassaigne and M. de Rougemont. Logique et complexité. Hermes, 1996.
[15] Y. Moses, R. Fagin, J. Halpern, and M. Vardi. Reasoning about Knowledge. MIT Press, 1995.
[16] M. Manzano. Model Theory. Clarendon Press, 1999.
[17] Y. Moschovakis. Notes on Set Theory. Springer Verlag, 1994.
[18] B. Poizat. A Course in Model Theory. Springer Verlag, 2000.
[19] M. D. Potter. Mengentheorie. Spektrum Akademischer Verlag, 1994.
[20] P. Rothmaler. Einführung in die Modelltheorie. Spektrum Verlag, 1995.
[21] R. Smullyan. Theory of formal systems. Princeton University Press, 1961.
[22] R. Smullyan. Gödel's Incompleteness Theorems. Oxford University Press, 1992.

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Mathematik (D): Reine Mathematik
  • Mathematik (B.Sc.): 5./6. Semester
  • Mathematik (M.Sc.) Reine Mathematik
  • Informatik (D): Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Informatik (M.Sc.): Theoretische Informatik
  • Informatik (B.Sc.): Wahlpflicht Theoretische Informatik
  • Informatik (GYM+GS,SII): Math. Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science

Leistungsnachweis

  • Diplomstudiengänge: Übungsschein bei aktiver Teilnahme an den Übungen
  • Bachelor-Studiengänge: Übungsschein bei aktiver Teilnahme an den Übungen und Bestehen einer mündlichen Prüfung
  • Software Systems Engineering (M.Sc.): active participation in exercises and final examination

Rückfragen

Erich Grädel, Frederic Reinhardt