Answers are grounded in this paper and cite their sources.
This analysis reveals sharp conditions for complete theories to achieve Pi omega 0 complexity in models, indicating significant implications for foundational theories.
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 Π _ω ^0 -complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a Π ω 0 Π _ω ^0 -complete set of models. We also give sharp conditions for theories to have a Π n 0 Π ^0_n -complete set of models.
No takes yet. Share an insight, caveat, or question.
Andrews et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: