2019/03/02 by Chubb, Jennifer, Miller, Russell, Solomon, Reed
#03C57 #03D45 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1903.00734
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 Δ(\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,a) by finitely many new constants. We end with a conjecture about the situation when all models of a theory are relatively decidable.