Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite View the MathML source2-piecewise computability 2 denotes the difference of two View the MathML sourceΠ10 sets), error-bounded learnability is equivalent to finite View (...) the MathML sourceΔ20-piecewise computability, and learnability is equivalent to countable View the MathML sourceΠ10-piecewise computability . Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/ Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games. (shrink)

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

Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer (...) and Hinman, we improve on the result of Binns and Simpson by showing that for any ${\mathcal{U} < _s \mathcal{V}}$ , we can lattice embed FD(ω) into ${\mathcal{P}_s}$ strictly between ${deg_s(\mathcal{U})}$ and ${deg_s({\mathcal V})}$ . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. (shrink)

A $\Pi^0_1$ class can be defined as the set of infinite paths through a computable tree. For classes $P$ and $Q$, say that $P$ is Medvedev reducible to $Q$, $P \leq_M Q$, if there is a computably continuous functional mapping $Q$ into $P$. Let $\mathcal{L}_M$ be the lattice of degrees formed by $\Pi^0_1$ subclasses of $2^\omega$ under the Medvedev reducibility. In "Non-branching degrees in the Medvedev lattice of $\Pi \sp{0}\sb{1} classes," I provided a characterization of nonbranching/branching and a classification of (...) the nonbranching degrees. In this paper, I present a similar classification of the branching degrees. In particular, $P$ is separable if there is a clopen set $C$ such that $P \cap C \neq \emptyset \neq P \cap C^c$ and $P \cap C \perp_M P \cap C^c$. By the results in the first paper, separability is an invariant of a Medvedev degree and a degree is branching if and only if it contains a separable member. Further define $P$ to be hyperseparable if, for all such $C$, $P \cap C \perp_M P \cap C^c$ and totally separable if, for all $X,Y \in P$, $X \perp_T Y$. I will show that totally separable implies hyperseparable implies separable and that the reverse implications do not hold, that is, that these are three distinct types of branching degrees. Along the way I will show some related results and present a combinatorial framework for constructing $\Pi^0_1$ classes with priority arguments. (shrink)