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. We also give sharp conditions for theories to have a Π⁰ₙ-complete set of models. Finally, we determine the Turing degrees needed to witness the completeness.
No takes yet. Share an insight, caveat, or question.
Andrews et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: