Model completeness and relative decidability

DOI10.1007/S00153-020-00753-4arXiv1903.00734WikidataQ105642085 ScholiaQ105642085MaRDI QIDQ6314930FDOQ6314930

Authors: Jennifer Chubb, Russell Miller, Reed Solomon 

Publication date: 2 March 2019

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.

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)

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)