Undecidability and 1-types in Intervals of the Computably Enumerable Degrees

by Klaus Ambos-Spies, Denis R. Hirschfeldt, and Richard A. Shore

Status: published in the Annals of Pure and Applied Logic, vol. 106 (2000), pp. 1 - 47.

Availability: DVI and PostScript

Abstract. We show that the theory of the partial ordering of the computably enumerable degrees in any given nontrivial interval is undecidable and has uncountably many 1-types.