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

Authors:
Publisher website
Google Scholar
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 Π ω 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.
Funding Information
  • National Science Foundation (2348792)
  • National Science Foundation (626304)
  • National Science Foundation (10.55776/P36781.)
  • National Science Foundation (101026834 - ACOSE)
  • Simons Foundation (2348792)
  • Simons Foundation (626304)
  • Simons Foundation (10.55776/P36781.)
  • Simons Foundation (101026834 - ACOSE)
  • Austrian Science Fund (2348792)
  • Austrian Science Fund (626304)
  • Austrian Science Fund (10.55776/P36781.)
  • Austrian Science Fund (101026834 - ACOSE)
  • H2020 Marie Skłodowska-Curie Actions (2348792)
  • H2020 Marie Skłodowska-Curie Actions (626304)
  • H2020 Marie Skłodowska-Curie Actions (10.55776/P36781.)
  • H2020 Marie Skłodowska-Curie Actions (101026834 - ACOSE)

This publication has 20 references indexed in Scilit: