We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.
The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.
.The partial ordering of Medvedev reducibility restricted to the family of Π01 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π01 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.
Important examples of $\Pi^0_1$ classes of functions $f \in {}^\omega\omega$ are the classes of sets (elements of ω 2) which separate a given pair of disjoint r.e. sets: ${\mathsf S}_2(A_0, A_1) := \{f \in{}^\omega2 : (\forall i < 2)(\forall x \in A_i)f(x) \neq i\}$ . A wider class consists of the classes of functions f ∈ ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: ${\mathsf S}_k(A_0,\ldots,A_k-1) := (...) \{f \in {}^\omega k : (\forall i < k) (\forall x \in A_i) f(x) \neq i\}$ . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let ${\mathcal S}^m_k$ denote the Medvedev degrees of those ${\mathsf S}_k(A_0,\ldots,A_{k-1})$ such that no m + 1 sets among A 0,...,A k-1 have a nonempty intersection. It is shown that each ${\mathcal S}^m_k$ is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions $\mathsf{DNR}_k$ is the greatest element of ${\mathcal S}^1_k$ . If 2 ≤ l < k, then 0 M is the only degree in ${\mathcal S}^1_l$ which is below a member of ${\mathcal S}^1_k$ . Each ${\mathcal S}^m_k$ is densely ordered and has the splitting property and the same holds for the lattice ${\mathcal L}^m_k$ it generates. The elements of ${\mathcal S}^m_k$ are exactly the joins of elements of ${\mathcal S}^1_i$ for $\lceil{k \over m}\rceil \leq i \leq k$. (shrink)
A result of Soare and Stob asserts that for any non-recursive r.e. setC, there exists a r.e.[C] setA such thatA⊕C is not of r.e. degree. A setY is called [of]m-REA (m-REA[C] [degree] iff it is [Turing equivalent to] the result of applyingm-many iterated ‘hops’ to the empty set (toC), where a hop is any function of the formX→X ⊕W e X . The cited result is the special casem=0,n=1 of our Theorem. Form=0,1, and any (m+1)-REA setC, ifC is not ofm-REA (...) degree, then for alln there exists an-r.e.[C] setA such thatA ⊕C is not of (m+n)-REA degree. We conjecture that this holds also form≥2. (shrink)
The partial order structure of degrees of unsolvability represented by continuous type-2 functionals is a proper extension of the partial order structure of type-1 degrees.
