The principal result of the paper is that there exist two incomparable recursively enumerable degrees whose greatest lower bound in the upper semilattice of degrees is 0. This was conjectured by Sacks. As a secondary result, it is proven that on the other hand there exists a recursively enumerable degree a < 0(1) such that for no non-zero recursively enumerable degree b is 0 the greatest lower bound of a and b. The proof of the main theorem involves a method that was developed elsewhere to deal with situations in which a partial recursive functional may interfere infinitely often with an opposed requirement of lower priority. A different method of handling such problems has been previously introduced by Sacks and used by him to prove that the recursively enumerable degrees are dense. In the definition of two recursively enumerable degrees which are merely incomparable, as in the original papers of Friedberg and Mucnik, each partial recursive functional eventually ceases to interfere with the construction, although there is no effective procedure for deciding at which state in the construction this occurs. A theorem given provides another variation on this theme.
展开▼
