Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-29T01:41:23.147Z Has data issue: false hasContentIssue false
  • English
  • Français

RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS

Part of: General logic Computability and recursion theory

Published online by Cambridge University Press:  05 October 2020

ROD DOWNEY ,
NOAM GREENBERG ,
MATTHEW HARRISON-TRAINOR ,
LUDOVIC PATEY  and
DAN TURETSKY
ROD DOWNEY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTONWELLINGTON, NEW ZEALANDE-mail: [email protected]: [email protected]
NOAM GREENBERG
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTONWELLINGTON, NEW ZEALANDE-mail: [email protected]: [email protected]
MATTHEW HARRISON-TRAINOR
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTONWELLINGTON, NEW ZEALAND and THE INSTITUTE OF NATURAL AND MATHEMATICAL SCIENCES MASSEY UNIVERSITYWELLINGTON, NEW ZEALANDE-mail: [email protected]
LUDOVIC PATEY
Affiliation:
INSTITUT CAMILLE JORDAN UNIVERSITÉ LYON 1, FRANCEE-mail: [email protected]
DAN TURETSKY
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICS VICTORIA UNIVERSITY OF WELLINGTONWELLINGTON, NEW ZEALANDE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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

reverse mathematicscomputability theoryhyperimmunity

MSC classification

Primary: 03B30: Foundations of classical theories (including reverse mathematics) 03D30: Other degrees and reducibilities 03D80: Applications of computability and recursion theory
Type
Article
Information
The Journal of Symbolic Logic , Volume 87 , Issue 1 , March 2022 , pp. 47 - 71
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Andrews, U., et al, On cototality and the skip operator in the enumeration degrees. Transactions of the American Mathematical Society , vol. 372 (2019), no. 3, pp. 1631–1670.CrossRefGoogle Scholar
Arslanov, M. M., Kalimullin, I. S., and Kuper, S. B., Splitting properties of total enumeration degrees . Algebra Logika , vol. 42(2003), no. 1, pp. 3–25, 125.CrossRefGoogle Scholar
Cholak, P. A., et al, Free sets and reverse mathematics . Reverse Mathematics , vol. 21 (2001), pp. 104–119.Google Scholar
Cholak, P. A., Jockusch, C. G., and Slaman, T. A., On the strength of Ramsey’s theorem for pairs , this Journal, vol. 66 (2001), no. 01, pp. 1–55.Google Scholar
Cholak, P. A. and Patey, L., Thin set theorems and cone avoidance. to appear, 2019.CrossRefGoogle Scholar
Dekker, J. C. E. and Myhill, J., Retraceable sets. Canadian Journal of Mathematics , vol. 10 (1958), pp. 357–373.CrossRefGoogle Scholar
Downey, R., Nies, A., Weber, R., and Yu, L., Lowness and ${\varPi}_2^0$ nullsets , this Journal, vol. 71 (2006), no. 3, pp. 1044–1052.Google Scholar
Dzhafarov, D. D. and Jockusch, C. G., Ramsey’s theorem and cone avoidance , this Journal, vol. 74 (2009), no. 2, pp. 557–578.Google Scholar
Friedberg, R. M. and Rogers, H. Jr. Reducibility and completeness for sets of integers . Mathematical Logic Quarterly , vol5 (1959), pp. 117–125.Google Scholar
Groszek, M. J and Slaman, T. A., Moduli of Computation (talk). Conference on Logic, Computability and Randomness, Buenos Aires, Argentina, 2007.Google Scholar
Hirschfeldt, D. R., et al, The strength of some combinatorial principles related to Ramsey’s theorem for pairs , Computational Prospects of Infinity, Part II: Presented Talks , Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 15, World Scientific Publishing, Hackensack, NJ, 2008, pp. 143–161.CrossRefGoogle Scholar
Jockusch, C. G., Ramsey’s theorem and recursion theory , this Journal, vol. 37 (1972), no. 2, pp. 268–280.Google Scholar
Jockusch, C. G. and Robert, I. S., ${\Pi}_0^1$ classes and degrees of theories . Transactions of the American Mathematical Society , vol. 173 (1972), pp. 33–56.Google Scholar
Jockusch, C. G. Jr. Semirecursive sets and positive reducibility . Transactions of the American Mathematical Society , vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
Jockusch, C. G. Jr. Reducibilities In Recursive Function Theory , (Ph.D thesis), Massachusetts Institute of Technology, ProQuest LLC, Ann Arbor, MI, 1966.Google Scholar
Kautz, S. M., Degrees of random sets , Ph.D thesis, Citeseer, 1991.Google Scholar
Kihara, T., Ng, K. M., and Pauly, A., Enumeration degrees and non-metrizable topology, 2019, arXiv:1904.04107 [math.GN].Google Scholar
Lerman, M., Solomon, R., and Towsner, H., Separating principles below Ramsey’s theorem for pairs . Journal of Mathematical Logic , vol. 13 (2013), no. 02, p. 1350007.Google Scholar
Liu, L, ${RT}_2^2$ does not imply WKL 0 , this Journal, vol. 77 (2012), no. 2, pp. 609–620.Google Scholar
Liu, L, Cone avoiding closed sets . Transactions of the American Mathematical Society , vol. 367 (2015), no. 3, pp. 1609–1630.CrossRefGoogle Scholar
Miller, J. S. and Soskova, M. I., Density of the cototal enumeration degrees . Annals of Pure and Applied Logic , vol. 169 (2018), no. 5, pp. 450–462.CrossRefGoogle Scholar
Patey, L., Combinatorial weaknesses of Ramseyan principles, In preparation. 2015. Available at http://ludovicpatey.com/media/research/combinatorial-weaknesses-draft.pdf.Google Scholar
Patey, L., Partial orders and immunity in reverse mathematics. Conference on Computability in Europe, 2016, Springer, Cham.CrossRefGoogle Scholar
Patey, L., The weakness of being cohesive, thin or free in reverse mathematics . Israel Journal of Mathematics , vol. 216 (2016), no. 2, pp. 905–955.CrossRefGoogle Scholar
Patey, L., Iterative forcing and hyperimmunity in reverse mathematics . Computability , vol. 6 (2017), no. 3, pp. 209–221.CrossRefGoogle Scholar
Patey, L., Ramsey-like theorems and moduli of computation. arXiv preprint, 2019, arXiv:1901.04388.CrossRefGoogle Scholar
Rice, B.. Thin set for pairs implies DNR. Notre Dame J. Formal Logic, to appear, 2015.Google Scholar
Rosenstein, J. G., Linear orderings volume 98 of Pure and Applied Mathematics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, NY-London, UK, 1982.Google Scholar
Seetapun, D. and Slaman, T. A., On the strength of Ramsey’s theorem . Notre Dame Journal of Formal Logic , vol. 36 (1995), no. 4, pp. 570–582.Google Scholar
Selman, A. L., Arithmetical reducibilities . Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , vol. 17 (1971), pp. 335–350.CrossRefGoogle Scholar
Simpson, S. G., Subsystems of Second Order Arithmetic . Cambridge University Press, Cambridge, MA, 2009.CrossRefGoogle Scholar
Terwijn, S. A. and Zambella, D., Computational randomness and lowness , this Journal, vol. 66 (2001), no. 3, pp. 1199–1205.Google Scholar
Wang, W., The definability strength of combinatorial principles, to appear, 2014. Available at http://arxiv.org/abs/1408.1465.Google Scholar
Wang, W., Some logically weak Ramseyan theorems . Advances in Mathematics , vol. 261 (2014), pp. 1–25.CrossRefGoogle Scholar