Computable Trees, Prime Models, and Relative Decidability

by Denis R. Hirschfeldt

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.