Journal of Symbolic Logic 87 (1):47-71 (2022)
Abstract |
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 |
Options |
![]() ![]() ![]() ![]() |
Download options
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.
Separating Principles Below Ramsey's Theorem for Pairs.Manuel Lerman, Reed Solomon & Henry Towsner - 2013 - Journal of Mathematical Logic 13 (2):1350007.
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.
Similar books and articles
Finitely Generated Groups Are Universal Among Finitely Generated Structures.Matthew Harrison-Trainor & Meng-Che “Turbo” Ho - 2021 - Annals of Pure and Applied Logic 172 (1):102855.
Lattice Representations for Computability Theory.Peter A. Fejer - 1998 - Annals of Pure and Applied Logic 94 (1-3):53-74.
Degree Spectra and Computable Dimensions in Algebraic Structures.Denis R. Hirschfeldt, Bakhadyr Khoussainov, Richard A. Shore & Arkadii M. Slinko - 2002 - Annals of Pure and Applied Logic 115 (1-3):71-113.
Computability-Theoretic Categoricity and Scott Families.Ekaterina Fokina, Valentina Harizanov & Daniel Turetsky - 2019 - Annals of Pure and Applied Logic 170 (6):699-717.
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.
Review of Denis R. Hirschfeldt, Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles. [REVIEW]Benedict Eastaugh - 2017 - Studia Logica 105 (4):873-879.
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.
Computability of String Functions Over Algebraic Structures Armin Hemmerling.Armin Hemmerling - 1998 - Mathematical Logic Quarterly 44 (1):1-44.
Computability and Uncountable Linear Orders II: Degree Spectra.Noam Greenberg, Asher M. Kach, Steffen Lempp & Daniel D. Turetsky - 2015 - Journal of Symbolic Logic 80 (1):145-178.
Computability and Uncountable Linear Orders I: Computable Categoricity.Noam Greenberg, Asher M. Kach, Steffen Lempp & Daniel D. Turetsky - 2015 - Journal of Symbolic Logic 80 (1):116-144.
Linear Orders Realized by C.E. Equivalence Relations.Ekaterina Fokina, Bakhadyr Khoussainov, Pavel Semukhin & Daniel Turetsky - 2016 - Journal of Symbolic Logic 81 (2):463-482.
Analytics
Added to PP index
2020-10-06
Total views
4 ( #1,278,078 of 2,506,426 )
Recent downloads (6 months)
2 ( #277,420 of 2,506,426 )
2020-10-06
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?
Downloads