Coding true arithmetic in the Medvedev and Muchnik degrees

Journal of Symbolic Logic 76 (1):267 - 288 (2011)
  Copy   BIBTEX

Abstract

We prove that the first-order theory of the Medvedev degrees, the first-order theory of the Muchnik degrees, and the third-order theory of true arithmetic are pairwise recursively isomorphic (obtained independently by Lewis, Nies, and Sorbi [7]). We then restrict our attention to the degrees of closed sets and prove that the following theories are pairwise recursively isomorphic: the first-order theory of the closed Medvedev degrees, the first-order theory of the compact Medvedev degrees, the first-order theory of the closed Muchnik degrees, the first-order theory of the compact Muchnik degrees, and the second-order theory of true arithmetic. Our coding methods also prove that neither the closed Medvedev degrees nor the compact Medvedev degrees are elementarily equivalent to either the closed Muchnik degrees or the compact Muchnik degrees

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,813

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

Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.
A survey of Mučnik and Medvedev degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
Interpreting true arithmetic in the [image] degrees.Thomas F. Kent - 2010 - Journal of Symbolic Logic 75 (2):522 - 550.
Some remarks on the algebraic structure of the Medvedev lattice.Andrea Sorbi - 1990 - Journal of Symbolic Logic 55 (2):831-853.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
The Π₃-Theory of the [image] -Enumeration Degrees Is Undecidable.Thomas F. Kent - 2006 - Journal of Symbolic Logic 71 (4):1284 - 1302.
On the Structure of the Medvedev Lattice.Sebastiaan A. Terwijn - 2008 - Journal of Symbolic Logic 73 (2):543 - 558.
On the t-degrees of partial functions.Paolo Casalegno - 1985 - Journal of Symbolic Logic 50 (3):580-588.

Analytics

Added to PP
2013-09-30

Downloads
23 (#701,105)

6 months
7 (#485,787)

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.
Mass problems and density.Stephen Binns, Richard A. Shore & Stephen G. Simpson - 2016 - Journal of Mathematical Logic 16 (2):1650006.

Add more citations

References found in this work

Embedding Brouwer algebras in the Medvedev lattice.Andrea Sorbi - 1991 - Notre Dame Journal of Formal Logic 32 (2):266-275.
Intermediate logics and factors of the Medvedev lattice.Andrea Sorbi & Sebastiaan A. Terwijn - 2008 - Annals of Pure and Applied Logic 155 (2):69-85.
Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (9-12):167-182.
Some Quotient Lattices of the Medvedev Lattice.Andrea Sorbi - 1991 - Mathematical Logic Quarterly 37 (9‐12):167-182.
Characterizing the Join-Irreducible Medvedev Degrees.Paul Shafer - 2011 - Notre Dame Journal of Formal Logic 52 (1):21-38.

View all 7 references / Add more references