Paper detail

Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial $Π^0_1$ subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty $Π^0_1$ subsets of Cantor space, we show the existence of a finite-$Δ^0_2$-piecewise degree containing infinitely many finite-$(Π^0_1)_2$-piecewise degrees, and a finite-$(Π^0_2)_2$-piecewise degree containing infinitely many finite-$Δ^0_2$-piecewise degrees (where $(Π^0_n)_2$ denotes the difference of two $Π^0_n$ sets), whereas the greatest degrees in these three "finite-$Γ$-piecewise" degree structures coincide. Moreover, as for nonempty $Π^0_1$ subsets of Cantor space, we also show that every nonzero finite-$(Π^0_1)_2$-piecewise degree includes infinitely many Medvedev (i.e., one-piecewise) degrees, every nonzero countable-$Δ^0_2$-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-$(Π^0_2)_2$-countable-$Δ^0_2$-piecewise degree includes infinitely many countable-$Δ^0_2$-piecewise degrees, and every nonzero Muchnik (i.e., countable-$Π^0_2$-piecewise) degree includes infinitely many finite-$(Π^0_2)_2$-countable-$Δ^0_2$-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-$Δ^0_2$-piecewise degree of a nonempty $Π^0_1$ subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev (Muchnik) degree structure and the finite-$Γ$-piecewise degree structure of all subsets of Baire space by showing that none of the finite-$Γ$-piecewise structures are Brouwerian, where $Γ$ is any of the Wadge classes mentioned above.