arxiv: 2604.17039 · v1 · submitted 2026-04-18 · 🧮 math.LO

Recognition: unknown

Characterizing relative decidability in terms of model completeness

Liam Tan, Matthew Harrison-Trainor

Pith reviewed 2026-05-10 06:36 UTC · model grok-4.3

classification 🧮 math.LO

keywords relative decidabilitymodel completenessconservative extensioncomplete theorieselementary diagramatomic diagrammodel theorycomputability

0 comments

The pith

For complete theories, relative decidability is equivalent to the existence of a conservative model-complete extension by one existentially realizable formula with constants.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that a complete theory T allows one to compute the elementary diagram of any model from its atomic diagram together with T exactly when T admits a conservative model-complete extension obtained by adding a single formula with new constants, where T already proves that formula has realizations. This supplies a model-theoretic criterion for when diagram computability works uniformly across all models. The same equivalence fails when T is not complete, so the characterization requires completeness as an essential precondition. A sympathetic reader cares because the result links a computability notion directly to the existence of a simple syntactic extension that makes the theory model complete.

Core claim

For complete theories T, T is relatively decidable if and only if T has a conservative model complete extension of the form T ∪ {ϕ(c̄)} where T ⊨ ∃x̄ ϕ(x̄). No such characterization works for incomplete theories.

What carries the argument

A conservative model-complete extension of T by adjoining a single formula ϕ(c̄) with new constants such that T already proves the sentence ∃x̄ ϕ(x̄).

If this is right

Relative decidability becomes checkable by searching for a model-complete conservative extension rather than by direct computation of diagrams.
Any model of such a T has its elementary diagram computable from the atomic diagram plus T.
Model completeness after a one-formula conservative extension guarantees uniform diagram computability across all models.
The failure for incomplete theories shows that completeness is necessary for the equivalence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The result suggests that other computability properties of diagrams might reduce to syntactic conditions on conservative extensions.
One could test whether similar single-formula extensions characterize decidability of the theory itself rather than of its diagrams.
In model theory applications, one might first check for such an extension to decide whether diagram computations are feasible before building concrete models.

Load-bearing premise

The theory T must be complete.

What would settle it

Exhibit a complete theory that is relatively decidable yet possesses no conservative model-complete extension of the required single-formula form, or exhibit an incomplete theory for which the existence of such an extension coincides exactly with relative decidability.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper confirms the Chubb-Miller-Solomon conjecture with a precise if-and-only-if for complete theories via conservative model-complete extensions by one sentence, and shows why the same condition fails for incomplete theories.

read the letter

The main takeaway is that Harrison-Trainor and Tan have settled the conjecture. For a complete theory T, relative decidability holds exactly when T admits a conservative model-complete extension of the form T union one sentence ϕ(c-bar) where T already proves the existence of such a tuple. They also give counterexamples showing no similar characterization works once T is allowed to be incomplete. This is the core new content: a clean equivalence in one direction and a clear negative result in the other. The positive direction uses model completeness to recover the elementary diagram from the atomic diagram plus T, while the converse direction builds the required extension from the relative decidability assumption. The counterexamples are explicit and prevent any overstatement. The argument stays within standard model theory and computability definitions, with no apparent circularity or extra parameters. The stress-test note aligns with this; there is no load-bearing gap in the complete case. A minor soft spot is that the technical construction of the extension may require some background in model completeness to follow in detail, but that is typical for the area and not a flaw in the result itself. The paper is aimed at researchers in computable model theory who care about when diagrams become computable relative to a theory. Readers working on decidability or model-theoretic characterizations will get direct value from the equivalence. It deserves a serious referee because it resolves an open conjecture with both directions grounded and the negative case handled cleanly. I would send it out for peer review.

Referee Report

0 major / 3 minor

Summary. The paper proves that a complete theory T is relatively decidable if and only if it admits a conservative model-complete extension of the form T ∪ {ϕ(c̄)} where T ⊨ ∃x̄ ϕ(x̄). It also shows that this syntactic condition does not characterize relative decidability when T is incomplete, by exhibiting explicit counterexamples.

Significance. The result verifies a conjecture of Chubb, Miller, and Solomon, giving a clean model-theoretic characterization of relative decidability precisely when T is complete. The argument proceeds by constructing the required extension in one direction and deriving relative decidability from model completeness plus the single-sentence extension in the other; the counterexamples for incomplete theories are direct and illustrate why completeness is essential. This strengthens the bridge between computable model theory and classical model theory.

minor comments (3)

§2, Definition 2.3: the phrase 'conservative model complete extension' is used before its precise meaning (conservative over T and model complete) is restated; a single forward reference to the definition would improve readability.
Theorem 3.4: the proof sketch for the 'only if' direction relies on the existence of a computable model whose atomic diagram is given; it would help to explicitly note that the construction preserves the completeness of T.
§4, Example 4.2: the counterexample for incomplete theories is presented via a theory with two completions; adding a brief remark on why the same construction cannot be adapted to the complete case would clarify the boundary.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment and recommendation to accept the manuscript. We are pleased that the report recognizes the verification of the Chubb-Miller-Solomon conjecture and the clean model-theoretic characterization for complete theories, as well as the necessity of completeness shown by the counterexamples.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes a direct if-and-only-if equivalence for complete theories T by constructing a conservative model-complete extension of the required syntactic form in one direction and deriving relative decidability from model completeness plus the single-sentence extension in the other, relying solely on standard model-theoretic definitions and explicit counterexamples for the incomplete case. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the argument is self-contained against external benchmarks in model theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies entirely on standard definitions and results from model theory and computability; no new free parameters, ad hoc axioms, or invented entities are introduced.

axioms (1)

standard math Standard definitions of model completeness, conservative extensions, atomic and elementary diagrams from model theory
The central claim is built directly on these established concepts without additional justification needed in the abstract.

pith-pipeline@v0.9.0 · 5390 in / 1166 out tokens · 77273 ms · 2026-05-10T06:36:29.033946+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

1 extracted references

[1]

Elsevier Science, 2000

[AK00] Chris Ash and Julia Knight.Computable Structures and the Hyperarithmetical Hierarchy. Elsevier Science, 2000. [AKMS89] Chris Ash, Julia Knight, Mark Manasse, and Theodore Slaman. Generic copies of countable structures.Ann. Pure Appl. Logic, 42(3):195–205, 1989. [BHT19] Nikolay Bazhenov and Matthew Harrison-Trainor. Constructing decidable graphs fro...

2000