Decidable Theories

Lectures in spring term 2023/24

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