Relationships between computability-theoretic properties of problems

DOI10.1017/JSL.2020.38zbMATH Open1507.03067arXiv1903.04273MaRDI QIDQ6315397FDOQ6315397

Authors: Rodney G. Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, Dan Turetsky 

Publication date: 11 March 2019

Abstract: A problem is a multivalued function from a set of emph{instances} to a set of emph{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 non-computable set $A$ and a computable instance of a problem $mathsfP$, to find a solution relative to which $A$ is still non-computable. 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 1 cone, of $omega$ cones, of 1 hyperimmunity or of 1 non-$Sigm{a}_1^0$ definition. We also prove that the hierarchies of preservation of hyperimmunity and non-$Sigm{a}_1^0$ definitions coincide. On the other hand, none of these notions coincide in a non-relativized setting.

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

This page was built for publication: Relationships between computability-theoretic properties of problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6315397)