Lower Bounds for Pairs of Recursively Enumerable Degrees

The degrees of unsolvability have been extensively studied by Sacks in (4). This paper studies problems concerned with lower bounds of pairs of recursively enumerable (r.e.) degrees. It grew out of an unpublished paper written in June 1964 which presented a proof of the following conjecture of Sacks ((4) 170): there exist two r.e. degrees a, b whose greatest lower bound is 0. This result was first announced by Yates (6); the present author's proof is superficially at least quite different from that of Yates. The author is grateful to Yates for pointing out two errors in the original proof of Lemma 3, and for his careful reading of the whole of the earlier paper. The result already mentioned is Theorem 1 of this paper. As a by-product of the construction we can obtain a' = b' = 0'; Yates has made a similar observation regarding his construction. In Theorem 2 it is proved that there are r.e. degrees a, b whose greatest lower bound is 0 such that a, b are the degrees of maximal r.e. sets. Next, we show that only for some r.e. degrees c in 0 < c < 0' do there exist r.e. degrees a, b such that c is the greatest lower bound of a and b. Finally, we show that if a and b are non-recursive r.e. degrees such that a u b = 0' then there exists a non-recursive r.e. degree c such that c < a and c < b. As a corollary it is shown that the upper semi-lattice of the r.e. degrees is not a lattice, thus verifying another conjecture of Sacks ((4) 170). Before this proof was discovered Sacks himself was developing a proof of the same conjecture. I should like to thank the referee for helpful comments.