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

reverse mathematicssecond-order arithmeticdecidable theoryprime modelsdecidable modelsatomic modelscomputable function, computable isomorphismeffectively atomic modelseffectively prime models

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

(9)

• Computable trees, prime models, and relative decidability
• Some Questions in Computable Mathematics
• Degree spectra of prime models
• A note on decidable categoricity and index sets
• Classifying model-theoretic properties
• Effectively existentially-atomic structures
• Constructivizability of a prime model
• On some forms of atomicity among countable models in the class \(E^+_T\) for \(\Delta-\mathrm{PJ}\)-theories and \(\Delta-\mathrm{PR}\)-theories
• Bounding prime 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)