Spring term 2023/24, course code NMAG499, Tuesday 17:20, room K9
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
- Ehrenfeucht–Fraïssé games
- Mostowski and Feferman–Vaught theorems
- Fraïssé limits
Exhibits (depending on time constraints):
- theories of abelian groups and modules
- ordered abelian groups (divisible, Presburger arithmetic)
- algebraically closed and real-closed fields
- theories of linear orders
- theories of Boolean algebras
- theories of random structures
- theories of locally free algebras
- Skolem arithmetic
Exam
There will be an oral exam assessing understanding of the main results presented during the course.
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.
NB: These electronic materials are provided strictly for individual study purposes, not for further distribution. I hold no copyrights to any of these.
Lectures
#1 (20 Feb 2024)
- Decidable and recursively axiomatizable theories.
- Quantifier elimination and decidability.
- Syntactic QE example: discrete linear orders.
#2 (27 Feb 2024)
- Model-theoretic QE example: dense linear orders.
- Criterion for quantifier elimination.
#3 (5 Mar 2024)
- Example: QE for algebraically closed and real-closed fields.
- Interpretations.
#4 (12 Mar 2024)
- Interpretations of models. Faithful interpretations.
- Example: Euclidean and hyperbolic geometry.
- Fraïssé limits.
#5 (19 Mar 2024)
- Existence and uniqueness of Fraïssé limits.
- Extension axioms.
#6 (2 Apr 2024)
- ω-categoricity and QE for Fraïssé limits.
- Example: atomless Boolean algebras.
- Example: random graphs, 0–1 law.
#7 (9 Apr 2024)
- Ehrenfeucht–Fraïssé games.
- Quantifier rank and k-equivalence.
- Preservation of elementary equivalence.
- Graded back-and-forth systems.
#8 (16 Apr 2024)
- Quantifier elimination using GBFS.
- Example: Presburger arithmetic.
- Complexity of DLO and Presburger.
#9 (23 Apr 2024)
- Presburger arithmetic (correction).
- Decidability of the theory of linear orders.
#10 (30 Apr 2024)
Plan:
- Decidability of LO (finish the proof).