Model completeness and relative decidability

Archive for Mathematical Logic 60 (6):721-735 (2021)


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 A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} of a computably enumerable, model complete theory, the entire elementary diagram E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document} 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document} from the atomic diagram Δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta $$\end{document} for all countable models A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} of T. Moreover, if every presentation of a single isomorphism type A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$$$\end{document} by finitely many new constants.

Download options


    Upload a copy of this work     Papers currently archived: 72,766

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

4 (#1,287,659)

6 months
1 (#386,989)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

Similar books and articles

Decidability of an Xstit Logic.Gillman Payette - 2014 - Studia Logica 102 (3):577-607.
An Elementary System as and its Semi‐Completeness and Decidability.Qin Jun - 1992 - Mathematical Logic Quarterly 38 (1):305-320.
A Logic with Relative Knowledge Operators.Stéphane Demri - 1999 - Journal of Logic, Language and Information 8 (2):167-185.
Taming Logic.Maarten Marx, Szabolcs Mikul & István Németi - 1995 - Journal of Logic, Language and Information 4 (3):207-226.
Logic for Update Products and Steps Into the Past.Joshua Sack - 2010 - Annals of Pure and Applied Logic 161 (12):1431-1461.
Completeness and the Ends of Axiomatization.Michael Detlefsen - 2014 - In Juliette Cara Kennedy (ed.), Interpreting Gödel. New York: Cambridge University Press. pp. 59-77.
On the Decidability of the PVD Class with Equality.N. Peltier - 2001 - Logic Journal of the IGPL 9 (4):569-592.
Modal Logics for Parallelism, Orthogonality, and Affine Geometries.Philippe Balbiani & Valentin Goranko - 2002 - Journal of Applied Non-Classical Logics 12 (3-4):365-397.
Reasoning About Sequences of Memory States.Rémi Brochenin, Stéphane Demri & Etienne Lozes - 2010 - Annals of Pure and Applied Logic 161 (3):305-323.