Notre Dame Journal of Formal Logic 49 (3):227-243 (2008)

Abstract
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
Keywords $\Pi^0_1$ classes   Medvedev lattice   branching degree
Categories (categorize this paper)
DOI 10.1215/00294527-2008-009
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 72,577
Through your library

References found in this work BETA

Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
Density of the Medvedev Lattice of Π0 1 Classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Density of the Medvedev Lattice of Π [Sup0][Sub1].Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.

Add more references

Citations of this work BETA

No citations found.

Add more citations

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.
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.
On $\pi^0_1$ Classes and Their Ranked Points.Rod Downey - 1991 - Notre Dame Journal of Formal Logic 32 (4):499-512.
On the $\sigma^01$-Conservativity of $\sigma^01$-Completeness.Albert Visser - 1991 - Notre Dame Journal of Formal Logic 32 (4):554-561.
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 index
2010-09-13

Total views
23 ( #497,602 of 2,533,585 )

Recent downloads (6 months)
1 ( #390,861 of 2,533,585 )

How can I increase my downloads?

Downloads

My notes