Advanced Logic (Summer 2025)

Organisation

• Lecturer: Prof. Dr. Markus Lohrey
• Lecture:
  • Monday, 14:00-16:00, in H-C 7327
• Tutorials:
  • Friday, 8:00-10:00, in H-C 7326 (Rahul Jain)
  • The first tutorial will be on Friday, April 11.

 

Some topics

• Undecidability in predicate logic
• The theorems of Church and Trakhtenbrot
• Undecidability of arithmetics and Gödel's theorem
• Automatic Structures
• Monadic second order logic and regular languages (Büchi's theorem)
• Existential second-order logic (Fagin's theorem)

 

Slides

 

Exercise sheets

• Exercise 1 Solutions
• Exercise 2 Solutions
• Exercise 3 Solutions
• Exercise 4 Solutions
• Exercise 5 Solutions
• Exercise 6

Literature

• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Einführung in die mathematische Logik, Springer
• Uwe Schöning: Logik für Informatiker, Spektrum Akademischer Verlag

Impressum