Type structure complexity and decidability

Abstract:

We prove that for every countable homogeneous model $\mathcal {A}$ such that the set of recursive types of $\operatorname {Th} (\mathcal {A})$ is $\sum _2^0$, $\mathcal {A}$ is decidable iff the set of types realized in $\mathcal {A}$ is a $\sum _2^0$ set of recursive types. As a corollary to a lemma, we show that if a complete theory $T$ has a recursively saturated model that is decidable in the degree of $T$, then $T$ has a prime model.