The Borel complexity of the class of models of first-order theories
Uri Andrews, David Gonzalez, Steffen Lempp, Dino Rossegger, Hongyu Zhu · Proceedings of the American Mathematical Society · 2025
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 Π ω 0 \boldsymbol \Pi _\omega ^0 -complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a Π ω 0 \boldsymbol \Pi _\omega ^0 -complete set of models. We also give sharp conditions for theories to have a Π n 0 \boldsymbol \Pi ^0_n -complete set of models.