Computability, definability, categoricity, and automorphisms
Robert Irving Soare, Russell Miller · 2000
In Chapter 1, we consider the spectrum of a linear order. Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable D02 degree, but not 0. In Chapter 2, we define a property R(A 0, A1) in the partial order E of computably enumerable sets under inclusion, and, prove that R implies that A0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A 0 and A1 which we build satisfying R form a Friedberg splitting of their union A, with A1 prompt and A promptly simple. We conclude that A0 and A1 lie in distinct orbits under automorphisms of E , yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit. In Chapter 3, we prove that no computable tree of height ω is computably categorical, and indeed that all such trees have computable dimension ω. The necessary construction requires us to prove several new versions of Kruskal's Lemma on the embeddability of finite trees. In Chapter 4, given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of E mapping A to a set B such that C n T B. Thus, the orbit in E of the low set A cannot be contained in the upper cone above C. This complements a result of Harrington, who showed that the orbit of a noncomputable c.e. set cannot be contained in the lower cone below any incomplete c.e. set.