Computable Trees, Prime Models, and Relative Decidability
Status: published in the Proceedings
of the American Mathematical
Society 134 (2006) 1495 - 1498.
Availability: journal
version and preprint
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