Mathematical Logic II

WS 2014/15


  • 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.


Type Date Location   Organizer
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



This course builds on the introductory lecture Mathematical Logic, which provided the basis of propositional logic, modal logic, and first-order logic. Mathematical Logic II will make the students acquainted with more advanced methods and with some of the fundamental achievements of mathematical logic in the 20th century.

We will focus on two areas of mathematical logic, namely set theory and model theory.

Set Theory and Foundations of Mathematics

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

Mathematics relies in a fundamental way on the notion of a set. But what are sets? A naive approach leads to paradoxes like the one, due to Russell, dealing with the set of all sets that are not elements of themselves.

We will explain in detail the axiom system ZFC (Zermelo-Fraenkel with Axiom of Choice) for set theory and try to understand the world of sets (Cantor's paradise) that they bring forth. This includes ordinals (how to count beyond the finite), cardinals (how to calculate with magnitudes of infinite sets), transfinite inductions, and recursion. We will discuss the importance of the Axiom of Choice and the Continuum Hypothesis.

The ultimate goal of the foundational efforts (Hilbert's program) was to put mathematics on a firm basis and to make sure that it is consistent (i.e., not contradictory). However, we will present a fundamental result, due to Gödel, that tells us that this dream will never come true: mathematics cannot be proved to be consistent, unless it is inconsistent!

Introduction to Model Theory

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

Model Theory is the study of mathematical structures with means of logic. The main goal of this part of the course is to learn the fundamental constructions and tools used in model theory, like compactness, types, and elementary extensions. We will concentrate on two questions.

  • Given a first-order theory T, how do the models of T look like?
    We will show how to construct models that are especially rich, i.e., contain every configuration that is not forbidden by T. Conversely, we will find models that omit everything not explicitly demanded by T. In most of these model constructions, the compactness theorem plays a central role.
  • What is the expressive power of a logic?
    We will introduce logical systems beyond first-order logic, like infinitary logic and fixed point logics, which are closely related to induction and recursion and which have applications in many areas, from set theory to computer science. To understand the power of these logics, we will study in detail the method of Ehrenfeucht-Fraïssé games and provide tools that make playing these games easier.


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].


[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.


  • Mathematical Logic


  • 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


  • 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


Erich Grädel, Frederic Reinhardt