Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-17T14:54:11.429Z Has data issue: false hasContentIssue false
  • English
  • Français

ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS

Published online by Cambridge University Press:  15 May 2017

RUTGER KUYPER
RUTGER KUYPER*
Affiliation:
SCHOOL OF MATHEMATICS AND STATISTICSVICTORIA UNIVERSITY OF WELLINGTONPO BOX 600, WELLINGTON 6140NEW ZEALANDE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that there is a strong connection between Weihrauch reducibility on one hand, and provability in EL0, the intuitionistic version of RCA0, on the other hand. More precisely, we show that Weihrauch reducibility to the composition of finitely many instances of a theorem is captured by provability in EL0 together with Markov’s principle, and that Weihrauch reducibility is captured by an affine subsystem of EL0 plus Markov’s principle.

Keywords

03B3003B2003D3003F35reverse mathematicsWeihrauch reducibilityintuitionistic logic
Type
Articles
Information
The Journal of Symbolic Logic , Volume 82 , Issue 4 , December 2017 , pp. 1438 - 1458
Copyright
Copyright © The Association for Symbolic Logic 2017 

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

Brattka, V. and Gherardi, G., Weihrauch degrees, omniscience principles and weak computability, this Journal, vol. 76 (2011), no. 1, pp. 143–176.Google 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), pp. 623–655.Google Scholar
Brattka, V., Oliva, P., and Pauly, A., On the algebraic structure of Weihrauch degrees, 2013, arXiv:1604.08348.Google Scholar
Buss, S. R. (ed.), Handbook of Proof Theory, Elsevier, Amsterdam, 1998.Google Scholar
Dorais, F. G., Classical consequences of continuous choice principles from intuitionistic analysis . Notre Dame Journal of Formal Logic, vol. 55 (2014), no. 1, pp. 25–39.CrossRefGoogle Scholar
Dorais, F. G., Dzhafarov, D. D., Hirst, J. L., Mileti, J. R., and Shafer, P., On uniform relationships between combinatorial problems . Transactions of the American Mathematical Society, vol. 368 (2016), pp. 1321–1359.Google Scholar
Dzhafarov, D. D., Strong reductions between combinatorial principles, this Journal, vol. 81 (2016), no. 4, pp. 1405–1431.Google Scholar
Fujiwara, M., Intuitionistic provability versus uniform provability in RCA , CiE 2015 (Beckmann, A., Mitrana, V., and Soskova, M., editors), Lecture Notes in Computer Science, vol. 9136, Springer, 2015, pp. 186–195.Google Scholar
Hirst, J. L. and Mummert, C., Reverse mathematics and uniformity in proofs without excluded middle . Notre Dame Journal of Formal Logic, vol. 52 (2011), no. 2, pp. 149–162.Google Scholar
Kleene, S. C., Formalized Recursive Functionals and Formalized Realizability, Memoirs of the American Mathematical Society, vol. 89, American Mathematical Society, Providence, RI, 1969.Google Scholar
Kohlenbach, U., Higher order reverse mathematics , Reverse Mathematics 2001 (Simpson, S. G., editor), Lecture Notes in Logic, vol. 21, A. K. Peters, Wellesley, MA, 2005, pp. 281–295.Google Scholar
Kuroda, S., Intuitionistic investigations of formalist logic . Nagoya Mathematical Journal, vol. 2 (1951), pp. 35–47 (in German).Google Scholar
Simpson, S. G., Subsystems of Second Order Arithmetic, Springer-Verlag, New York, NY, 1999.Google Scholar
Troelstra, A. S (ed.), Metamathematical Investigation of Intuitionistic Arithmetic and Analysis, Lecture Notes in Mathematics, vol. 344, Springer, 1973.CrossRefGoogle Scholar