Model completeness and relative decidability

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 of a computably enumerable, model complete theory, the entire elementary diagram E ( A ) must be decidable. We prove that indeed...

Full description

Saved in:
Bibliographic Details
Published in:Archive for mathematical logic 2021-08, Vol.60 (6), p.721-735
Main Authors: Chubb, Jennifer, Miller, Russell, Solomon, Reed
Format: Article
Language:English
Subjects:
Algebra
Completeness
Isomorphism
Mathematical Logic and Foundations
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 of a computably enumerable, model complete theory, the entire elementary diagram E ( 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 ( A ) from the atomic diagram Δ ( A ) for all countable models A of T . Moreover, if every presentation of a single isomorphism type A has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion ( A , a ) by finitely many new constants.
ISSN:0933-5846
1432-0665
DOI:10.1007/s00153-020-00753-4