The property of smallness for Π0 1 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π0 1 class depends only on the Muchnik degree of a Π0 1 class. A comparison is made with the idea of thinness for Π0 1 classesmsthm.

The property of smallness for Π01 classes is introduced and is investigated with respect to Medvedev and Muchnik degree. It is shown that the property of containing a small Π01 class depends only on the Muchnik degree of a Π01 class. A comparison is made with the idea of thinness for Π01 classesmsthm.

Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. We say that P is strongly reducible to Q if every member of Q Turing computes a member of P via a fixed Turing functional. The weak degrees and strong degrees are the equivalence classes of mass problems under weak and strong reducibility, respectively. We (...) focus on the countable distributive lattices P w and P s of weak and strong degrees of mass problems given by nonempty Π 1 0 subsets of 2 ω . Using an abstract Gödel/Rosser incompleteness property, we characterize the Π 1 0 subsets of 2 ω whose associated mass problems are of top degree in P w and P s , respectively. Let R be the set of Turing oracles which are random in the sense of Martin-Löf, and let r be the weak degree of R. We show that r is a natural intermediate degree within P w . Namely, we characterize r as the unique largest weak degree of a Π 1 0 subset of 2 ω of positive measure. Within P w we show that r is meet irreducible, does not join to 1, and is incomparable with all weak degrees of nonempty thin perfect Π 1 0 subsets of 2 ω . In addition, we present other natural examples of intermediate degrees in P w . We relate these examples to reverse mathematics, computational complexity, and Gentzen-style proof theory. (shrink)