The complexity of the index sets of ℵ₀-categorical theories and of Ehrenfeucht theories
Steffen Lempp, Theodore A. Slaman · Contemporary mathematics - American Mathematical Society · 2007
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 ℵ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. 1. The Main Theorem Measuring the complexity of mathematical notions is one of the main tasks of mathematical logic. Two of the main tools to classify complexity are provided by Kleene’s arithmetical and analytical hierarchy. These two hierarchies provide convenient ways to determine the exact complexity of properties by various notions of completeness, and to give lower bounds on the complexity by various notions of hardness. (See, e.g., Kleene [1], Soare [10] or Odifreddi [4, 5] for the definitions.) This paper will investigate the complexity of properties of a firstorder theory, more precisely, the complexity of a countable first-order theory having a certain number of models. Recall that a theory is called ℵ0-categorical if it has only one countable model up to isomorphism, and an Ehrenfeucht theory if it has more than one but only finitely many countable models up to isomorphism. In order to measure the complexity of these notions, we will use decidable first-order theories,