The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories

Lempp, Steffen; Slaman, Theodore A.

The complexity of the index sets of $\aleph_0$-categorical theories and of Ehrenfeucht theories

Authors

Description

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 $Π^0_3$-complete; and the property of being an Ehrenfeucht theory $Π^1_1$-complete. We also show that the property of having continuum many models is $Σ^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 $Π^1_1$-complete.