Characterizing relative decidability in terms of model completeness
A theory $T$ is said to be relatively decidable if for every model of $T$, one can compute the elementary diagram of that model from its atomic diagram together with $T$. We verify a conjecture of Chubb, Miller, and Solomon by showing that for complete theories $T$, $T$ is relatively decidable if and only if $T$ has a conservative model complete extension of the form $T \cup \{\varphi(\bar{c})\}$ where $T \models \exists \bar{x} \; \varphi(\bar{x})$. We also show that no such characterization works for incomplete theories.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.17039
curl -X POST /api/v1/records/arxiv/2604.17039/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.17039/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'