Properties of relative recursive enumerability.

This dissertation is a contribution to the theory of the Turing degrees of sets of natural numbers. The focus is on the difference hierarchy over the recursively enumerable (r.e.) sets, in particular its relationship to sets which are r.e. relative to another r.e. set. An early result in this area asserts that for any two r.e. sets C T H ( C is properly recursive in H) there exists a set F such that C T F T H, and F is a difference of r.e. sets (d.r.e.) but is not of the same degree as any r.e. set. Our first result corrects an error in the proof and slightly improves this result. The methods developed are then applied to show that for any r.e. sets C T H, there exists an r.e. set C T D T H such that there is a set F with D T F, F is d.r.e. relative to D, and F is not of the same degree as any set in the difference hierarchy. If also C is high (has the highest possible jump) and G is any r.e. set satisfying G T H then there exists a set F such that G T F T H, F is r.e. relative to C and d.r.e. but not of r.e. degree. The result just mentioned actually establishes the existence of sets D and F with G T D T F D and F are r.e. relative to C and d.r.e., but there is no r.e. set E with D ≤ T E ≤ T F. Another result shows that for any r.e. set C, and in the absense of the bounding sets G and H there exists such an r.e. free interval with endpoints r.e. relative to C.Ph.D.MathematicsPure SciencesUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/131953/2/9938494.pd