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

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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2020.38
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,130
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

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.
Density of the Cototal Enumeration Degrees.Joseph S. Miller & Mariya I. Soskova - 2018 - Annals of Pure and Applied Logic 169 (5):450-462.

View all 10 references / Add more references

Citations of this work BETA

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

Add more citations

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 index

Total views
4 ( #1,278,078 of 2,506,426 )

Recent downloads (6 months)
2 ( #277,420 of 2,506,426 )

How can I increase my downloads?


My notes