Uniform principal types and computable prime models

Definitions and mathematical statement

Question 19 asks what additional information is needed to build a computable prime model of a decidable theory $T$ with countably many countable models, noting that $\omega$-stability suffices. The count is understood up to isomorphism in the aid's usual countable-language setting. The source does not explicitly settle completeness or whether "countably many" includes finitely many. The following DCF/Turing-degree heading belongs to the next section and does not restrict this question or attribute it to Calvert.

For the aid's conditional result assume $T$ is a complete decidable atomic theory in a computable countable language. A complete type is principal when isolated by a consistent formula; atomic means principal types are dense among consistent formulas. A prime model admits an elementary embedding into every model of $T$. A computable copy has decidable atomic diagram, while a decidable copy has decidable full elementary diagram.

Assume further that the prime-model isomorphism type is relatively decidable: for every copy $P$ of that type, its elementary diagram is computable from its atomic diagram. The aid reports equivalence of:

1. a computable prime copy of $T$ exists;
2. a decidable prime copy exists;
3. the complete principal types, across finite arities, have a uniform computable listing;
4. there is a computable principal-type selector returning indices for total computable characteristic functions.

For clarity, a uniform type listing supplies total effective membership tests for the listed complete types and includes every principal type, allowing repetitions. The selector, in the aid's intended formulation, takes a consistent formula $\varphi(\bar x)$ and returns an index for a complete principal type containing it, whose characteristic function on formulas is total. Merely listing isolating candidates or producing partial indices is not that conclusion. The summary does not reproduce its exact coding/uniformity definitions, so these details require checking against the full statement.

The aid further reports that every c.e. model-complete theory is uniformly relatively decidable: elementary diagrams are computable uniformly from atomic diagrams. Model-complete means every embedding between models is elementary. Consequently all four conditions are equivalent for every complete decidable atomic model-complete theory, including that portion of the few-countable-models setting. The extra relative-decidability hypothesis is not asserted automatic for every complete decidable atomic theory, and the equivalence alone does not say its four conditions always hold. The unrestricted workshop question remains open in the supplied assessment.

Short English statement

The source asks how to obtain computable prime models in the few-model setting. The aid gives equivalent effective type-selection conditions when the prime type is relatively decidable, with model-completeness supplying that extra hypothesis. It distinguishes computable atomic diagrams from decidable elementary diagrams and does not claim a general construction for the original class.

Sources

• Local UnsolvedMath registry, permanent ID 20002321, exact source code catalogue entry; canonical aim-logic-notes.json, notes[96], tag question; AIM Workshop Problem Lists, Logic, Computable stability theory, Question 19. Created and updated 14 August 2026.
• Source URL https://aimath.org/pastworkshops/computestabproblems.pdf. The supplied verification separates the following "Turing degrees of DCFs (Calvert)" heading. The original notes $\omega$-stability as sufficient. The PDF was not accessed.
• Attempt 1: conditional_result, problem status at run open, rigor label proved, novelty confidence low; classification PARTIAL-PROGRESS, suggested difficulty L4, registry status partially_solved. Candidate: principal-type-selector equivalence under relative decidability, including the model-complete specialization. No full authoritative theorem references are supplied.
• Ulam AI / UnsolvedMath Contributors; CC BY 4.0. Machine-generated research aid, not peer reviewed; independently verify before citation.