The Friedberg-Muchnik Theorem Re-Examined

Source abstract

In the well-known solution to Post's problem, Friedberg [ 1 ] and Muchnik [ 13 ] each constructed a pair of incomparable recursively enumerable (r.e.) degrees a and b . Subsequently, Sacks [ 15 , p. 81] constructed r.e. degrees c and d such that c ∪ d = 0’ and C’ = d’ = 0' . Lachlan showed [ 7 , p. 69] that such degrees c, d could have no greatest lower bound in the upper semilattice of r.e. degrees. We show that the original Friedberg-Muchnik degrees a, b automatically satisfy Sack's conditions and hence witness that the upper semi-lattice of r.e. degrees is not a lattice.