Consider the countable semilattice R-T consisting of the recursively enumerable Turing degrees. Although R-T is known to be structurally rich, a major source of frustration is that no specific, natural degrees in R-T have been discovered, except the bottom and top degrees, 0 and 0'. In order to overcome this difficulty, we embed R-T into a larger degree structure which is better behaved. Namely, consider the countable distributive lattice P-w consisting of the weak degrees (also known as Muchnik degrees) of mass problems associated with non-empty Ill subsets of 2'. It is known that Pw contains a bottom degree 0 and a top degree 1 and is structurally rich. Moreover, Pw contains many specific, natural degrees other than 0 and 1. In particular, we show that in Pw one has 0 < d < r(1) < inf(r(2), 1) < 1. Here, d is the weak degree of the diagonally non-recursive functions, and r is the weak degree of the n-random reals. It is known that r(1) can be characterized as the maximum weak degree of a II10 subset of 2(omega) of positive measure. We now show that inf(r(2), 1) can be characterized as the maximum weak degree of a II01 subset of 2(omega), the Turing upward closure of which is of positive measure. We exhibit a natural embedding of R-T into P-w which is one-to-one, preserves the semilattice structure of R-T, carries 0 to 0, and carries 0' to 1. Identifying R-T with its image in P-W, we show that all of the degrees in R-T except 0 and 1 are incomparable with the specific degrees d, r(1), and inf(r(2), 1) in P-W.
展开▼
