The ∀∃-theory of the effectively closed Medvedev degrees is decidable

Archive for Mathematical Logic 49 (1):1-16 (2010)
  Copy   BIBTEX

Abstract

We show that there is a computable procedure which, given an ∀∃-sentence ${\varphi}$ in the language of the partially ordered sets with a top element 1 and a bottom element 0, computes whether ${\varphi}$ is true in the Medvedev degrees of ${\Pi^0_1}$ classes in Cantor space, sometimes denoted by ${\mathcal{P}_s}$

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

Coding true arithmetic in the Medvedev and Muchnik degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
Topological aspects of the Medvedev lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.
Degrees of difficulty of generalized r.e. separating classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
A splitting theorem for the Medvedev and Muchnik lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
The Medvedev lattice of computably closed sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
The Medvedev Lattice of Degrees of Difficulty.Andrea Sorbi - 1996 - In S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.), Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Cambridge University Press. pp. 224--289.
Some remarks on the algebraic structure of the Medvedev lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.

Analytics

Added to PP
2013-11-23

Downloads
14 (#846,877)

6 months
3 (#447,120)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
Inside the Muchnik degrees I: Discontinuity, learnability and constructivism.K. Higuchi & T. Kihara - 2014 - Annals of Pure and Applied Logic 165 (5):1058-1114.
Coding true arithmetic in the Medvedev degrees of classes.Paul Shafer - 2012 - Annals of Pure and Applied Logic 163 (3):321-337.

Add more citations

References found in this work

Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
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.
Working below a low2 recursively enumerably degree.Richard A. Shore & Theodore A. Slaman - 1990 - Archive for Mathematical Logic 29 (3):201-211.

View all 6 references / Add more references