Relationships between computability-theoretic properties of problems

Journal of Symbolic Logic 87 (1):47-71 (2022)
  Copy   BIBTEX


A problem is a multivalued function from a set of instances to a set of solutions. We consider only instances and solutions coded by sets of integers. A problem admits preservation of some computability-theoretic weakness property if every computable instance of the problem admits a solution relative to which the property holds. For example, cone avoidance is the ability, given a noncomputable set A and a computable instance of a problem ${\mathsf {P}}$, to find a solution relative to which A is still noncomputable.In this article, we compare relativized versions of computability-theoretic notions of preservation which have been studied in reverse mathematics, and prove that the ones which were not already separated by natural statements in the literature actually coincide. In particular, we prove that it is equivalent to admit avoidance of one cone, of $\omega $ cones, of one hyperimmunity or of one non- $\Sigma ^{0}_1$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non- $\Sigma ^{0}_1$ definitions coincide. On the other hand, none of these notions coincide in a nonrelativized setting.



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

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

Lattice representations for computability theory.Peter A. Fejer - 1998 - Annals of Pure and Applied Logic 94 (1-3):53-74.
Computability and Randomness.André Nies - 2008 - Oxford, England: Oxford University Press UK.
The veblen functions for computability theorists.Alberto Marcone & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (2):575 - 602.
On the notion of effectiveness.Stewart Shapiro - 1980 - History and Philosophy of Logic 1 (1-2):209-230.
Computability of the ergodic decomposition.Mathieu Hoyrup - 2013 - Annals of Pure and Applied Logic 164 (5):542-549.
Classifying model-theoretic properties.Chris J. Conidis - 2008 - Journal of Symbolic Logic 73 (3):885-905.
Embeddings between well-orderings: Computability-theoretic reductions.Jun Le Goh - 2020 - Annals of Pure and Applied Logic 171 (6):102789.


Added to PP

18 (#835,873)

6 months
7 (#437,422)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Punctual definability on structures.Iskander Kalimullin, Alexander Melnikov & Antonio Montalban - 2021 - Annals of Pure and Applied Logic 172 (8):102987.

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.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
Arithmetical Reducibilities I.Alan L. Selman - 1971 - Mathematical Logic Quarterly 17 (1):335-350.

View all 10 references / Add more references