Non-Branching Degrees in the Medvedev Lattice of [image] Classes

Journal of Symbolic Logic 72 (1):81 - 97 (2007)
  Copy   BIBTEX

Abstract

A $\Pi _{1}^{0}$ class is the set of paths through a computable tree. Given classes P and Q, P is Medvedev reducible to Q, P ≤M Q, if there is a computably continuous functional mapping Q into P. We look at the lattice formed by $\Pi _{1}^{0}$ 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,931

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Some remarks on the algebraic structure of the Medvedev lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.
The degrees of conditional problems.Su Gao - 1994 - Journal of Symbolic Logic 59 (1):166-181.
A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
Π⁰₁ classes with complex elements.Stephen Binns - 2008 - Journal of Symbolic Logic 73 (4):1341-1353.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
Embedding Brouwer algebras in the Medvedev lattice.Andrea Sorbi - 1991 - Notre Dame Journal of Formal Logic 32 (2):266-275.
Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.
On the complexity-relativized strong reducibilites.Jari Talja - 1983 - Studia Logica 42 (2-3):259 - 267.

Analytics

Added to PP
2010-08-24

Downloads
29 (#567,950)

6 months
13 (#220,183)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references