$\Pi ^{0}_{1}$ -Encodability and Omniscient Reductions

Notre Dame Journal of Formal Logic 60 (1):1-12 (2019)
  Copy   BIBTEX

Abstract

A set of integers A is computably encodable if every infinite set of integers has an infinite subset computing A. By a result of Solovay, the computably encodable sets are exactly the hyperarithmetic ones. In this article, we extend this notion of computable encodability to subsets of the Baire space, and we characterize the Π10-encodable compact sets as those which admit a nonempty Σ11-subset. Thanks to this equivalence, we prove that weak weak König’s lemma is not strongly computably reducible to Ramsey’s theorem. This answers a question of Hirschfeldt and Jockusch.

Links

PhilArchive



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

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

Difference sets and computability theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
Stability and Posets.Carl G. Jockusch, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon - 2009 - Journal of Symbolic Logic 74 (2):693-711.
On local non‐compactness in recursive mathematics.Jakob G. Simonsen - 2006 - Mathematical Logic Quarterly 52 (4):323-330.
Computability Over Structures of Infinite Signature.Armin Hemmerling - 1998 - Mathematical Logic Quarterly 44 (3):394-416.
Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.
The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Computable metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.
The computable Lipschitz degrees of computably enumerable sets are not dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
RT₂² does not imply WKL₀.Jiayi Liu - 2012 - Journal of Symbolic Logic 77 (2):609-620.

Analytics

Added to PP
2019-01-18

Downloads
23 (#683,628)

6 months
8 (#364,101)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
Recursive well-orderings.Clifford Spector - 1955 - Journal of Symbolic Logic 20 (2):151-163.

View all 15 references / Add more references