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}$

Categories

Keywords

Reprint years

2009

DOI

10.1007/s00153-009-0150-6

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 107,751

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

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.
Topological aspects of the Medvedev lattice.Andrew Em Lewis, Richard A. Shore & Andrea Sorbi - 2011 - Archive for Mathematical Logic 50 (3-4):319-340.
Degrees of difficulty of generalized r.e. separating classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
Non-Branching Degrees in the Medvedev Lattice of [image] Classes.Christopher P. Alfeld - 2007 - Journal of Symbolic Logic 72 (1):81 - 97.
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.
Coding true arithmetic in the Medvedev and Muchnik degrees.Paul Shafer - 2011 - Journal of Symbolic Logic 76 (1):267 - 288.
On the C.E. Degrees realizable in $\pi ^0_1$ classes.Barbara F. Csima, Rod Downey & N. G. Keng Meng - 2024 - Journal of Symbolic Logic 89 (3):1370-1395.
A closed subset of Baire space not Medvedev equivalent to any closed set of Cantor space.Joshua A. Cole - forthcoming - Archive for Mathematical Logic:1-9.
The Medvedev lattice of computably closed sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
Comparing the degrees of enumerability and the closed Medvedev degrees.Paul Shafer & Andrea Sorbi - 2019 - Archive for Mathematical Logic 58 (5-6):527-542.

Analytics

Added to PP
2013-11-23

Downloads
30 (#893,352)

6 months
1 (#1,688,303)

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.

Add more references