The Borel complexity of the class of models of first-order theories

2024/02/15 by Andrews, Uri, Gonzalez, David, Lempp, Steffen +2 · 1 citation
#03C52 #03C62 #03E15 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2402.10029

Abstract

We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Knight and Solovay, we give a sharp condition for complete theories to have a \pmbΠ_ω⁰-complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a \pmbΠ_ω⁰-complete set of models. We also give sharp conditions for theories to have a \pmbΠ⁰_n-complete set of models.

Cited by

• A COMPLETE BOUNDED THEORY WITH UNBOUNDED TYPES

Related

• The complexity of the index sets of ℵ₀-categorical theories and of Ehrenfeucht theories
• A Walk on the Wild Side: Notions of maximality in first-order theories
• The Borel Complexity of Isomorphism for Complete Theories of Linear Orders With Unary Predicates
• Most(?) theories have Borel complete reducts
• Borel Complexity and Potential Canonical Scott Sentences