Embeddings into the Medvedev and Muchnik lattices of Π0 1 classes

Archive for Mathematical Logic 43 (3):399-414 (2004)
  Copy   BIBTEX

Abstract

Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

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

A splitting theorem for the Medvedev and Muchnik lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
Some remarks on the algebraic structure of the Medvedev lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
Hyperimmunity in 2\sp ℕ.Stephen Binns - 2007 - Notre Dame Journal of Formal Logic 48 (2):293-316.
Infinite substructure lattices of models of Peano Arithmetic.James H. Schmerl - 2010 - Journal of Symbolic Logic 75 (4):1366-1382.
Coding true arithmetic in the Medvedev and Muchnik degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
Small Π0 1 Classes.Stephen Binns - 2005 - Archive for Mathematical Logic 45 (4):393-410.
The Medvedev lattice of computably closed sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
Subsystems of second-order arithmetic between RCA0 and WKL0.Carl Mummert - 2008 - Archive for Mathematical Logic 47 (3):205-210.
Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Constructive Logic and the Medvedev Lattice.Sebastiaan A. Terwijn - 2006 - Notre Dame Journal of Formal Logic 47 (1):73-82.

Analytics

Added to PP
2013-11-23

Downloads
30 (#459,346)

6 months
1 (#1,040,386)

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.
Mass problems and almost everywhere domination.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):483-492.

View all 19 citations / Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
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.
N? Sets and models of wkl0.Stephen G. Simpson - 2005 - In Stephen Simpson (ed.), Reverse Mathematics 2001. pp. 21--352.

Add more references