The Journal of Symbolic Logic

Research Article

The upper semilattice of degrees ≤ 0′ is complemented

David B. Posner 1

San Jose State University, San Jose, California 95192

Let denote the set of degrees ≤ 0′. A degree a 0′ is said to be complemented in if there exists a degree b0′ such that ba = 0′ and ba = 0. R.W. Robinson (cf. [11]) showed that every degree a0′ satisfying a″ = 0″ is complemented in and the author [8] showed that every degree a0′ satisfying a′ = 0″ is complemented in . Also, in [2], R. L. Epstein showed that every r.e. degree is complemented in . In this paper we will show that in fact every degree ≤ 0′ is complemented in . We will further show that the same is true in the upper semilattice of degrees ≤ c, where c is any complete degree. This is in contrast to the situation in the upper semilattice of r.e. degrees in which, as Lachlan [6] has shown, no degree other than 0 and 0′ is complemented.

(Received July 23 1979)


1   This research was supported by NSF grant MCS 7903379