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 \(\varDelta (\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},\mathbf {a})\) by finitely many new constants.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ash, C.J., Knight, J.F., Manasse, M.S., Slaman, T.A.: Generic copies of countable structures. Ann. Pure Appl. Logic 42, 195–205 (1989)
Chang, C.C., Keisler, H.J.: Model Theory, 3rd edn. Elsevier, Amsterdam (1990)
Goncharov, S.S., Harizanov, V.S., Laskowski, C., Lempp, S., McCoy, C.: Trivial strongly minimal theories are model complete after naming constants. Proc. A.M.S 131(12), 3901–3912 (2003)
Harizanov, V.S.: Pure Computable Model Theory. Handbook of Recursive Mathematics, vol. 1, pp. 3–114. Elsevier, Amsterdam (1998)
Harrison-Trainor,M.: There is a no simple characterization of the relatively decidable theories, submitted for publication
Harrison-Trainor, M., Melnikov, A., Miller, R., Montalbán, A.: Computable functors and effective interpretability. J. Symbol. Logic 82(1), 77–97 (2017)
Hirschfeldt, D.R., Khoussainov, B., Shore, R.A., Slinko, A.M.: Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Logic 115, 71–113 (2002)
Miller, R., Poonen, B., Schoutens, H., Shlapentokh, A.: A computable functor from graphs to fields. J. Symbol. Logic 83(1), 326–348 (2018)
Montalbán, A.: Computability theoretic classifications for classes of structures. Proc. ICM 2014(2), 79–101 (2014)
Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer, New York (1987)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interests
The authors declare that they have no conflict of interest, and add that there is no data associated with this work.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Russell Miller was supported by NSF Grant # DMS-1362206, Simons Foundation Grant # 581896, and several PSC-CUNY research awards.
Rights and permissions
About this article
Cite this article
Chubb, J., Miller, R. & Solomon, R. Model completeness and relative decidability. Arch. Math. Logic 60, 721–735 (2021). https://doi.org/10.1007/s00153-020-00753-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-020-00753-4