Spring term 2025/26, course code NMAG570, Thursday 14:00, room K4
Consultations: drop me an email to arrange a meeting
Syllabus
We will study basic methods for proving algorithmic decidability of first-order theories and main examples of
decidable theories.
Tools:
- quantifier elimination
- interpretations
- Fraïssé limits
- Ehrenfeucht–Fraïssé games
- Feferman–Vaught-like theorems
Exhibits (depending on time constraints):
- algebraically closed and real-closed fields
- theories of linear orders
- theories of Boolean algebras
- theories of random structures and locally free algebras
- theories of abelian groups and modules
- ordered abelian groups (divisible, Presburger arithmetic)
- Skolem arithmetic
This lecture in spring term 2024/25, spring term 2023/24
Exam
There will be an oral exam assessing understanding of the main results presented during the course. Each student
will present one of the main topic groups of their own choosing. The list of topics will depend on our actual
progress during the semester, but the exam topics for the previous year were as follows:
- Syntactic and semantic criteria for QE. Algebraically closed fields.
- Fraïssé limits. Atomless Boolean algebras.
- Ehrenfeucht–Fraïssé games, graded back-and-forth systems. Presburger arithmetic.
- The theory of linear orders.
Recommended literature
- Wilfrid Hodges, Model Theory, Cambridge University Press, 1993.
- Michael O. Rabin, Decidable theories, in: Handbook of Mathematical Logic (ed. Jon Barwise), 1977, §C.3, pp. 595–629.
- Hans Läuchli, John Leonard, On the elementary theory of linear order, Fundamenta Mathematicae 59 (1966), no. 1, pp. 109–116. See also A note on the theory of well orders.
NB: Excepting the Note, these electronic materials are provided strictly for individual study purposes, not for further distribution; I hold no copyrights to them.
Lectures
#1 (20 Feb 2026)
- Decidable and recursively axiomatizable theories.
- Quantifier elimination and decidability.
- Syntactic QE example: discrete linear orders.