Effective prime uniqueness

DOI10.1090/PROC/13675MaRDI QIDQ4592760zbMATH OpenOpenAlexFDO

Authors Peter A. Cholak, Charlie C. S. C. McCoy

Publication date 8 November 2017

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.5976

zbMATH Keywords

atomic modelscomputable function, computable isomorphismdecidable modelsdecidable theoryeffectively atomic modelseffectively prime modelsprime modelsreverse mathematicssecond-order arithmetic

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Abstract: Assuming the obvious definitions (see paper) we show the a decidable model that is effectively prime is also effectively atomic. This implies that two effectively prime (decidable) models are computably isomorphic. This is in contrast to the theorem that there are two atomic decidable models which are not computably isomorphic. The implications of this work in reverse mathematics is that "effectively prime implies effectively atomic" holds in topped models. But due to an observation of David Belanger, "effectively prime implies effectively atomic" fails for some Scott sets. The reserve mathematical strength of "Prime Uniqueness" remains open.

Recommendations

• Degree spectra of prime models
• Constructivizability of a prime model
• Computable trees, prime models, and relative decidability
• On decidable categoricity and almost prime models
• Prime models and almost decidability

Cites work

• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 1302870 (Why is no real title available?)
• Model theory.
• Reverse mathematics of first-order theories with finitely many models
• The atomic model theorem and type omitting

Cited in

(12)

• Constructivizability of a prime model
• Model completeness and relative decidability
• A note on decidable categoricity and index sets
• Effectively existentially-atomic structures
• Some Questions in Computable Mathematics
• Computable trees, prime models, and relative decidability
• On some forms of atomicity among countable models in the class \(E^+_T\) for \(\Delta-\mathrm{PJ}\)-theories and \(\Delta-\mathrm{PR}\)-theories
• Classifying model-theoretic properties
• Degree spectra of prime models
• Bounding prime models
• Weihrauch complexity for elementary embeddings into countable saturated models
• Weihrauch degrees of elementary embeddings for prime and saturated models

This page was built for publication: Effective prime uniqueness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592760)