Density of the Medvedev lattice of Π01 classes

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

Abstract

Abstract.The partial ordering of Medvedev reducibility restricted to the family of Π01 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π01 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

Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Embedding FD(ω) into {mathcal{P}_s} densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.
Some remarks on the algebraic structure of the Medvedev lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
Topological aspects of the Medvedev lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
The Medvedev lattice of computably closed sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
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 density of truth in monadic fragments of some intermediate logics.Zofia Kostrzycka - 2007 - Journal of Logic, Language and Information 16 (3):283-302.
Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.
On some filters and ideals of the Medvedev lattice.Andrea Sorbi - 1990 - Archive for Mathematical Logic 30 (1):29-48.
A splitting theorem for the Medvedev and Muchnik lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.

Analytics

Added to PP
2014-03-12

Downloads
8 (#1,126,801)

6 months
2 (#648,997)

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.
The Medvedev lattice of computably closed sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.

View all 15 citations / Add more citations

References found in this work

No references found.

Add more references