Archive for Mathematical Logic 42 (6):583-600 (2003)

The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes
Keywords Degree of difficulty  Medvedev lattice  Recursive functional  Density
Categories (categorize this paper)
DOI 10.1007/s00153-002-0166-7
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: 71,172
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Index Sets for Π01 Classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.

Add more references

Citations of this work BETA

Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Mass Problems and Hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
A Survey of Mučnik and Medvedev Degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
The Medvedev Lattice of Computably Closed Sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.

View all 17 citations / Add more citations

Similar books and articles

Degrees of Difficulty of Generalized R.E. Separating Classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
The Medvedev Lattice of Computably Closed Sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
Some Remarks on the Algebraic Structure of the Medvedev Lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
Topological Aspects of the Medvedev Lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
Embedding FD(Ω) Into {Mathcal{P}_s} Densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
The Density of Truth in Monadic Fragments of Some Intermediate Logics.Zofia Kostrzycka - 2007 - Journal of Logic, Language and Information 16 (3):283-302.
Small Π0 1 Classes.Stephen Binns - 2005 - Archive for Mathematical Logic 45 (4):393-410.


Added to PP index

Total views
9 ( #954,194 of 2,517,876 )

Recent downloads (6 months)
1 ( #409,482 of 2,517,876 )

How can I increase my downloads?


My notes