1 results
Non-branching degrees in the Medvedev lattice of Π10 classes
-
- Journal:
- The Journal of Symbolic Logic / Volume 72 / Issue 1 / March 2007
- Published online by Cambridge University Press:
- 12 March 2014, pp. 81-97
- Print publication:
- March 2007
-
- Article
- Export citation
-
A
class is the set of paths through a computable tree. Given classes P and Q, P is Medvedev reducible to Q, P ≤MQ, if there is a computably continuous functional mapping Q into P. We look at the lattice formed by subclasses of 2ω under this reduction. It is known that the degree of a splitting class of c.e. sets is non-branching. We further characterize non-branching degrees, providing two additional properties which guarantee non-branching: inseparable and hyperinseparable. Our main result is to show that non-branching iff inseparable if hyperinseparable if homogeneous and that all unstated implications do not hold. We also show that inseparable and not hyperinseparable degrees are downward dense.
class is the set of paths through a computable tree. Given classes 