Article contents
Non-branching degrees in the Medvedev lattice of Π10 classes
Published online by Cambridge University Press: 12 March 2014
Abstract
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.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 2007
References
REFERENCES
- 8
- Cited by