The Journal of Symbolic Logic

Research Article

Complementation in the Turing degrees

Theodore A. Slamana1 and John R. Steela2

a1 Department of Mathematics, University of Chicago, Chicago, Illinois 60637

a2 Department of Mathematics, U. C. L. A., Los Angeles, California 90024

Abstract

Posner [6] has shown, by a nonuniform proof, that every degree has a complement below 0′. We show that a 1-generic complement for each set of degree between 0 and 0′ can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above ∅′. In the second half of the paper, we show that the complementation of the degrees below 0′ does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees a above b such that no degree strictly below a joins b above a. (This result is independently due to S. B. Cooper.) We end with some open problems.

(Received January 02 1986)

(Revised August 27 1987)