Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Computable trees, prime models, and relative decidability


Author: Denis R. Hirschfeldt
Journal: Proc. Amer. Math. Soc. 134 (2006), 1495-1498
MSC (2000): Primary 03C57, 03D45
Published electronically: October 4, 2005
MathSciNet review: 2199197
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that for every computable tree $\mathcal T$ with no dead ends and all paths computable, and every $D >_T \emptyset$, there is a $D$-computable listing of the isolated paths of $\mathcal T$. It follows that for every complete decidable theory $T$ such that all the types of $T$ are computable and every $D >_T \emptyset$, there is a $D$-decidable prime model of $T$. This result extends a theorem of Csima and yields a stronger version of the theorem, due independently to Slaman and Wehner, that there is a structure with presentations of every nonzero degree but no computable presentation.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03C57, 03D45

Retrieve articles in all journals with MSC (2000): 03C57, 03D45


Additional Information

Denis R. Hirschfeldt
Affiliation: Department of Mathematics, The University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637
Email: drh@math.uchicago.edu

DOI: http://dx.doi.org/10.1090/S0002-9939-05-08097-4
PII: S 0002-9939(05)08097-4
Received by editor(s): November 17, 2004
Published electronically: October 4, 2005
Additional Notes: This research was partially supported by NSF Grant DMS-02-00465.
The author thanks Robert Soare for many enlightening discussions related to this paper.
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2005 American Mathematical Society