The complexity of the index sets of ${\aleph }_0$-categorical theories and of Ehrenfeucht theories

Abstract

We classify the computability-theoretic complexity of two index sets of classes of first-order theories: We show that the property of being an ${\aleph }_0$-categorical theory is ${\Pi }_3^0$-complete; and the property of being an Ehrenfeucht theory ${\Pi }_1^1$-complete. We also show that the property of having continuum many models is ${\Sigma }_1^1$-hard. Finally, as a corollary, we note that the properties of having only decidable models, and of having only computable models, are both ${\Pi }_1^1$-complete.