Model completeness and relative decidability

DOI10.1007/S00153-020-00753-4MaRDI QIDQ6314930arXivWikidataFDO

Authors Jennifer Chubb, Russell Miller, Reed Solomon

Publication date 2 March 2019

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Quantifier elimination, model completeness, and related topics (03C10)

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 $mathcalA$ of a computably enumerable, model complete theory, the entire elementary diagram $E(mathcalA)$ 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(mathcalA)$ from the atomic diagram $Delta(mathcalA)$ for all countable models $mathcalA$ of $T$. Moreover, if every presentation of a single isomorphism type $mathcalA$ has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion $(mathcalA,veca)$ by finitely many new constants. We end with a conjecture about the situation when all models of a theory are relatively decidable.

This page was built for publication: Model completeness and relative decidability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314930)