An extension of the recursively enumerable Turing degrees

摘要

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