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.

Categories

Keywords

Reprint years

DOI

10.1007/s00153-002-0166-7

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

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

Through your library

My notes

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.
A Note on Closed Degrees of Difficulty of the Medvedev Lattice.Caterina Bianchini & Andrea Sorbi - 1996 - Mathematical Logic Quarterly 42 (1):127-133.
Topological aspects of the Medvedev lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
Classifying the Branching Degrees in the Medvedev Lattice of $\Pi^0_1$ Classes.Christopher P. Alfeld - 2008 - Notre Dame Journal of Formal Logic 49 (3):227-243.
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.
Embeddings into the Medvedev and Muchnik lattices of Π0 1 classes.Stephen Binns & Stephen G. Simpson - 2004 - Archive for Mathematical Logic 43 (3):399-414.
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
16 (#883,649)

6 months
9 (#290,637)

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