Degree structures below 0'
Jiang Liu · 2010
This thesis is concerned with various degree structures below 0 , varying from Turing degrees to truth-table degrees, from computably enumerable degrees to ∆ 0 2 degrees.In Chapter 1, we first provide a general introduction to the development of computability theory in the last few decades, after which, we will present the motivation of our results contained in this thesis.Notation and terminology will be introduced briefly at the end of this chapter.In Chapter 2, we consider the interaction between the cupping property and the high/low hierarchy.Cholak, Groszek and Slaman proved the existence of a c.e. degree cupping every low c.e. degree to a low degree, and claimed that for any nonzero c.e. degree a, there is a nonhigh c.e. degree b such that a ∪ b, the supremum of a and b, is high.Jockusch, Li and Yang proved that the c.e. degree b above can be low 2 , and Wu proved that this degree can also be cappable.Our result in Chapter 2 shows that b above can even be a noncuppable degree, improving all the results along this line.Chapters 3 and 4 are devoted to the infima of degrees at different levels in the Ershov hierarchy.Lachlan's nondiamond theorem shows that in R, the structure of the computably enumerable degrees, if nonzero degrees a and b have supremum 0 , then they cannot have infimum 0. In contrast to this, Downey showed the existence of two nonzero d.c.e.degrees a and b with supremum 0 and infimum 0 in the structure of d.c.e.degrees.That is, the diamond lattice can be embedded into the d.c.e.degrees preserving 0 and 1.This provides an elementary difference between R and D 2 .In his Ph.D. thesis, Wu provided another approach of such a lattice embedding by using the isolation pairs.Lachlan observed that the infimum of two c.e. degrees in R, if exists, coincides