Density of the Medvedev lattice of Π0 1 classes

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 89,654

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

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.

Analytics

Added to PP
2013-11-23

Downloads
11 (#965,719)

6 months
1 (#1,014,737)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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.

View all 17 citations / Add more citations

References found in this work

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

Add more references