Computable Trees, Prime Models, and Relative Decidability
Status: published in the Proceedings of the American Mathematical
Society vol. 134 (2006), pp. 1495 - 1498.
Availability: PostScript, DVI, and PDF
Abstract. We show that for every computable tree T with no
dead ends and all paths computable, and every noncomputable D,
there is a D-computable listing of the isolated paths of T.
It follows that for every complete decidable theory T such that all
the types of T are computable and every noncomputable D,
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.
drh@math.uchicago.edu