Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T07:23:19.284Z Has data issue: false hasContentIssue false
  • English
  • Français

SEARCHING FOR AN ANALOGUE OF ATR0 IN THE WEIHRAUCH LATTICE

Part of: Computability and recursion theory General logic

Published online by Cambridge University Press:  10 July 2020

TAKAYUKI KIHARA ,
ALBERTO MARCONE  and
ARNO PAULY
TAKAYUKI KIHARA
Affiliation:
DEPARTMENT OF MATHEMATICAL INFORMATICS NAGOYA UNIVERSITYNAGOYA, JAPANE-mail: [email protected]
ALBERTO MARCONE
Affiliation:
DIPARTIMENTO DI SCIENZE MATEMATICHE, INFORMATICHE E FISICHE, UNIVERSITÁ DI UDINEUDINE, ITALYE-mail: [email protected]
ARNO PAULY
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE SWANSEA UNIVERSITYSWANSEA, UK DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF BIRMINGHAMBIRMINGHAM, UKE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

Keywords

Weihrauch degreesperfect set theoremopen and clopen determinacycomparability of well-orders

MSC classification

Primary: 03D78: Computation over the reals
Secondary: 03D30: Other degrees and reducibilities 03B30: Foundations of classical theories (including reverse mathematics)
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 3 , September 2020 , pp. 1006 - 1043
Check for updates
Copyright
© The Association for Symbolic Logic 2020

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

REFERENCES

Bienvenu, L., Greenberg, N., and Monin, B., Continuous higher randomness . Journal of Mathematical Logic , vol. 17 (2017), no. 1, p. 53.CrossRefGoogle Scholar
Blass, A., Complexity of winning strategies . Discrete Mathematics , vol. 3 (1972), pp. 295–300.CrossRefGoogle Scholar
Brattka, V., Effective borel measurability and reducibility of functions . Mathematical Logic Quarterly , vol. 51 (2005), pp. 19–44.CrossRefGoogle Scholar
Brattka, V., A Galois connection between turing jumps and limits . Logical Methods in Computer Science , vol. 14 (2018), no. 3, pp. 1–37.Google Scholar
Brattka, V., de Brecht, M., and Pauly, A., Closed choice and a uniform low basis theorem . Annals of Pure and Applied Logic , vol. 163 (2012), no. 8, pp. 968–1008.CrossRefGoogle Scholar
Brattka, V. and Gherardi, G., Effective choice and boundedness principles in computable analysis . Bulletin of Symbolic Logic , vol. 17 (2011), pp. 73–117.CrossRefGoogle Scholar
Brattka, V. and Gherardi, G., Weihrauch degrees, omniscience principles and weak computability, this Journal, vol. 76 (2011), pp. 143–176.Google Scholar
Brattka, V., Gherardi, G., and Hölzl, R., Probabilistic computability and choice . Information and Computation , vol. 242 (2015), pp. 249–286.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., Hölzl, R., Nobrega, H., and Pauly, A., Borel choice, in preparation.Google Scholar
Brattka, V., Gherardi, G., Hölzl, R., and Pauly, A., The Vitali covering theorem in the Weihrauch lattice , Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A., and Rosamond, F., editors), Springer International Publishing, Cham, 2017, pp. 188–200.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., and Marcone, A., The Bolzano-Weierstrass Theorem is the jump of Weak König’s Lemma . Annals of Pure and Applied Logic , vol. 163 (2012), no. 6, pp. 623–625.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., and Pauly, A.. Weihrauch complexity in computable analysis. Preprint, 2017. http://arxiv.org/abs/1707.03202.Google Scholar
Brattka, V., Kawamura, A., Marcone, A., and Pauly, A., Measuring the complexity of computational content (Dagstuhl Seminar 15392) . Dagstuhl Reports , vol. 5 (2016), no. 9, pp. 77–104.Google Scholar
Brattka, V. and Pauly, A., Computation with advice . Electronic Proceedings in Theoretical Computer Science , vol. 24 (2010), pp. 41–55 CrossRefGoogle Scholar
Brattka, V. and Pauly, A., On the algebraic structure of Weihrauch degrees . Logical Methods in Computer Science , vol. 14 (2018), no. 4, pp. 1–36 Google Scholar
Chong, C. T. and Yu, L., Randomness in the higher setting , this Journal, vol. 80 (2015), no. 4, pp. 1131–1148.Google Scholar
Dzhafarov, D., Joins in the strong Weihrauch degrees . Mathematical Research Letters , vol. 26 (2019), no. 3, pp. 749–767.CrossRefGoogle Scholar
Dzhafarov, D. D., Le Goh, J., Hirschfeldt, D. R., Patey, L., and Pauly, A., Ramsey’s theorem and products in the Weihrauch degrees. Preprint, 2018. https://arxiv.org/abs/1804.10968.Google Scholar
Friedman, H. M. and Hirst, J. L., Weak comparability of well orderings and reverse mathematics . Annals of Pure and Applied Logic , vol. 47 (1990), pp. 11–29.CrossRefGoogle Scholar
Gherardi, G. and Marcone, A., How incomputable is the separable Hahn-Banach theorem? Notre Dame Journal of Formal Logic , vol. 50 (2009), no. 4, pp. 393–425.CrossRefGoogle Scholar
Goh, J. L., Embeddings between well-orderings: computability-theoretic reductions . Annals of Pure and Applied Logic , vol. 171 (2020), no. 6, art. 102789.CrossRefGoogle Scholar
Gregoriades, V., Kispéter, T., and Pauly, A., A comparison of concepts from computable analysis and effective descriptive set theory . Mathematical Structures in Computer Science , vol. 27 (2017), vol. 8, pp. 1414–1436.CrossRefGoogle Scholar
Higuchi, K. and Pauly, A., The degree-structure of Weihrauch-reducibility . Logical Methods in Computer Science , vol. 9 (2013), no. 2, pp. 1–17.CrossRefGoogle Scholar
Hirschfeldt, D. R., Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles , World Scientific, Hackensack, NJ, 2014.CrossRefGoogle Scholar
Jockusch, C. G. Jr. and Soare, R. I., ${\varPi}_1^0$ classes and degrees of theories . Transactions of the American Mathematical Society , vol. 173 (1972), pp. 33–56.Google Scholar
Kihara, T. and Pauly, A., Dividing by zero – How bad is it, really? 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) (Faliszewski, P., Muscholl, A., and Niedermeier, R., editors), Leibniz International Proceedings in Informatics (LIPIcs), volume 58, Schloss Dagstuhl, Dagstuhl, 2016, pp. 58:1–58:14.Google Scholar
Kleene, S. C., Hierarchies of number-theoretic predicates . Bulletin of the American Mathematical Society , vol. 61 (1955), pp. 193–213.CrossRefGoogle Scholar
Kleene, S. C., Quantification of number-theoretic functions . Compositio Mathematica , vol. 14 (1959), pp. 23–40.Google Scholar
Kreisel, G., Analysis of the Cantor-Bendixson theorem by means of the analytic hierarchy . Bulletin de l’Académie Polonaise des Sciences. Série des Sciences Mathématiques, Astronomiques et Physiques , vol. 7 (1959), pp. 621–626.Google Scholar
Le Roux, S. and Pauly, A., Weihrauch degrees of finding equilibria in sequential games , Evolving Computability (Beckmann, A., Mitrana, V., and Soskova, M., editors), Lecture Notes in Computer Science, volume 9136, Springer, Cham, 2015, pp. 246–257.CrossRefGoogle Scholar
Montalbán, A., On the ${\varPi}_1^1$ -separation principle . Mathematical Logic Quarterly , vol. 54 (2008), no. 6, pp. 563–578.CrossRefGoogle Scholar
Neumann, E. and Pauly, A., A topological view on algebraic computations models . Journal of Complexity , vol. 44 (2018), pp. 1–22.CrossRefGoogle Scholar
Nies, A., Computability and Randomness , Oxford Logic Guides, volume 51, Oxford, Oxford University Press, 2009.CrossRefGoogle Scholar
Nobrega, H. and Pauly, A., Game characterizations and lower cones in the Weihrauch degrees . Logical Methods in Computer Science , vol. 15 (2019), no. 3, pp. 11.1–11.29.Google Scholar
Pauly, A., How incomputable is finding Nash equilibria? Journal of Universal Computer Science , vol. 16 (2010), no. 18, pp. 2686–2710.Google Scholar
Pauly, A., On the (semi)lattices induced by continuous reducibilities . Mathematical Logic Quarterly , vol. 56 (2010), no. 5, pp. 488–502.CrossRefGoogle Scholar
Pauly, A., Computable metamathematics and its application to game theory , Ph.D. thesis, University of Cambridge, 2012.Google Scholar
Pauly, A., On the topological aspects of the theory of represented spaces . Computability , vol. 5 (2016), no. 2, pp. 159–180.CrossRefGoogle Scholar
Pauly, A., Computability on the space of countable ordinals, this Journal, accepted for publication. http://arxiv.org/abs/1501.00386.Google Scholar
Pauly, A. and de Brecht, M., Towards synthetic descriptive set theory: An instantiation with represented spaces. Preprint, 2013. http://arxiv.org/abs/1307.1850.Google Scholar
Sacks, G. E., Higher Recursion Theory , Perspectives in Mathematical Logic, vol. 2, Springer-Verlag, Berlin, 1990.CrossRefGoogle Scholar
Simpson, S., Subsystems of Second Order Arithmetic , Perspectives in Logic, Cambridge University Press, Cambridge, 2009.CrossRefGoogle Scholar
von Stein, T., Vergleich nicht konstruktiv lösbarer Probleme in der Analysis , Diplomarbeit , Fachbereich Informatik, FernUniversität Hagen, 1989.Google Scholar
Weihrauch, K., The degrees of discontinuity of some translators between representations of the real numbers , Informatik Berichte , vol. 129, FernUniversität Hagen, Hagen, 1992.Google Scholar