Andrews, U., Gonzalez, D., Lempp, S., Rossegger, D., & Zhu, H. (2025). The Borel complexity of the class of models of first-order theories. Proceedings of the American Mathematical Society, 153(9), 4013–4024. https://doi.org/10.1090/proc/17308
Borel complexity; countable models; descriptive set theory; Models of arithmetic
en
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 ∏⁰ω-complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a ∏⁰ω-complete set of models. We also give sharp conditions for theories to have a ∏⁰ₙ-complete set of models.
en
Project title:
Algorithmische Komplexität von Strukturen und deren Äquivalenzrelationen: 101026834 (European Commission) Strukturen durch Lernen Klassifizieren: P 36781-N (FWF - Österr. Wissenschaftsfonds)
