October 18
Russell Miller,
CUNY
Model Completeness and Relative Decidability
Model-completeness is a standard notion in model theory, and it is well known that a theory $T$ is model complete if and only if $T$ has quantifier elimination down to existential formulas. From the quantifier elimination, one quickly sees that every computable model of a computably enumerable, model-complete theory $T$ must be decidable. We call a structure relatively decidable if this holds more broadly: if for all its copies $\mathcal{A}$ with domain $\omega$, the elementary diagram of $\mathcal{A}$ is Turing-reducible to the atomic diagram of $\mathcal{A}$. In some cases, this reduction can be done uniformly by a single Turing functional for all copies of $\mathcal{A}$, or even for all models of a theory $T$.
We discuss connections between these notions. For a c.e. theory, model completeness is equivalent to uniform relative decidability of all countable models of the theory, but this fails if the condition of uniformity is excluded. On the other hand, for relatively decidable structures where the reduction is not uniform, it can be made uniform by expanding the language by finitely many constants to name certain specific elements. This is shown by a priority construction related to forcing. We had conjectured that a similar result might hold for theories $T$ such that every model of $T$ is relatively decidable, but in separate work, Matthew Harrison-Trainor has now shown relative decidability to be a $\Pi^1_1$-complete property of a theory, which is far more complicated than our conjectured equivalent property.
This is joint work with Jennifer Chubb and Reed Solomon.