Decidable Theories

Lectures in spring term 2024/25

This lecture now, in spring term 2023/24

#1 (21 Feb 2025)

• Decidable and recursively axiomatizable theories.
• Quantifier elimination and decidability.
• Syntactic QE sufficient condition.

#2 (26 Feb 2025)

• Syntactic QE example: discrete linear orders.
• Model-theoretic QE example: dense linear orders.
• Substructures, embeddings, diagrams.

#3 (5 Mar 2025)

• Criterion for quantifier elimination.
• Example: QE for algebraically closed fields.

#4 (12 Mar 2025)

• Example: QE for real-closed fields.
• Interpretations.

#5 (19 Mar 2025)

• Interpretations of models. Faithful interpretations.
• Example: Euclidean and hyperbolic geometry.

#6 (26 Mar 2025)

• Fraïssé limits.
• Existence of Fraïssé limits.

#7 (2 Apr 2025)

• Uniqueness of Fraïssé limits.
• Extension axioms.

#8 (9 Apr 2025)

• ω-categoricity and QE for Fraïssé limits.
• Example: atomless Boolean algebras.

#9 (16 Apr 2025)

• Ehrenfeucht–Fraïssé games.
• Quantifier rank and k-equivalence.
• Preservation of elementary equivalence.

#10 (23 Apr 2025)

• Graded back-and-forth systems.
• Quantifier elimination using GBFS.
• Example: Presburger arithmetic.

#11 (30 Apr 2025)

• (Repetition.)

#12 (7 May 2025)

• Presburger arithmetic (finish).
• Complexity of DLO and Presburger.

#13 (14 May 2025)

• Decidability of the theory of linear orders.

#14 (21 May 2025)

• Decidability of the theory of linear orders (finish).