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. Each student will present one of the following topic groups of their own choosing:
- Syntactic and semantic criteria for QE. Algebraically closed fields.
- Fraïssé limits. Either random graphs or atomless Boolean algebras.
- Ehrenfeucht–Fraïssé games, graded back-and-forth systems. Presburger arithmetic.
- The theory of linear orders.
- Feferman–Vaught theorems. Skolem arithmetic.
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 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)
- Decidability of LO (almost finish the proof).
#11 (7 May 2024)
- Finish the decidability of LO.
- The theory of well orders.
- Reduced products.
- A Feferman–Vaught theorem for reduced products.
#12 (21 May 2024)
- QE for atomic Boolean algebras.
- A Feferman–Vaught theorem for weak products.
- Example: Skolem arithmetic.