Incompleteness, approximation and relative randomness

Abstract

We present some results about the structure of c.e. and Δ02 LR-degrees. First we give a technique for lower cone avoidance in the c.e. and Δ02 LR-degrees, and combine this with upper cone avoidance via Sacks restraints to construct a c.e. LR-degree which is incomparable with a given intermediate Δ02 LR-degree. Next we combine measure-guessing with an LR-incompleteness strategy to construct an incomplete c.e. LR-degree which is above a given low Δ02 LR-degree. This is in contrast to the Turing degrees, in which there is a low Δ02 Turing degree which is incomparable with all intermediate c.e. Turing degrees.