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

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 ${\Pi }_{\omega }^0$-complete set of models. In particular, any sequential theory (a class of foundational theories isolated by Pudlák) has a ${\Pi }_{\omega }^0$-complete set of models. We also give sharp conditions for theories to have a ${\Pi }_n^0$-complete set of models.