Model completeness and relative decidability

Abstract

We study the implications of model completeness of a theory for the effectiveness of presentations of models of that theory. It is immediate that for a computable model $\mathcal{A}$ of a computably enumerable, model complete theory, the entire elementary diagram $E(\mathcal{A})$ must be decidable. We prove that indeed a c.e. theory $T$ is model complete if and only if there is a uniform procedure that succeeds in deciding $E(\mathcal{A})$ from the atomic diagram $\Delta (\mathcal{A})$ for all countable models $\mathcal{A}$ of $T$. Moreover, if every presentation of a single isomorphism type $\mathcal{A}$ has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion $(\mathcal{A},\vec{a})$ by finitely many new constants. We end with a conjecture about the situation when all models of a theory are relatively decidable.