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

Remote Access
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

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

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia