Structural Properties of D.C.E. Degrees and Presentations of C.E. Reals

Abstract

In this thesis, we are mainly concerned with the structural properties of the d.c.e. degrees and the distribution of the simple reals among the c.e. degrees. In chapters 2 and 3, we study the relationship between the isolation phenomenon and the jump operator. We prove in chapter 2 that there is a high d.c.e. degree d isolated by a low2 degree a. We improve this result in chapter 3 by showing that the isolating degree a can be low. Chapters 4 and 5 are devoted to the study of the pseudo-isolation in the d.c.e. degrees. We prove that pseudo-isolated d.c.e. degrees are dense in the c.e. degrees, and that there is a high d.c.e. degree pseudo-isolated by a low d.c.e. degree. In chapter 6, we prove that there are two d.c.e. degrees between which there is exactly one c.e. degree and that there are two c.e. degree a1 < a2 and a d.c.e. degree d ∈ (a1, a2) such that the intervals (a1, d) and (d, a2) contains no c.e. degrees. In chapter 7, we construct an isolation pair (a, d) and a c.e. degree c such that c ∪ d = 0', c ∩ a = 0. This result gives an alternative proof of Downey's diamond embedding into the d.c.e. degrees. Chapter 8 is a contribution to the study of the distribution of the simple reals in the c.e. degrees. We show that there is a noncomputable c.e. degree bounding no noncomputable the simple reals. Thus, simple reals are not dense in the structure of the computably enumerable degrees.