Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T21:30:42.132Z Has data issue: false hasContentIssue false
  • English
  • Français

THE CHARACTERIZATION OF WEIHRAUCH REDUCIBILITY IN SYSTEMS CONTAINING $E-PA^{\omega } + QF-AC^{0,0}$

Part of: General logic Computability and recursion theory Proof theory and constructive mathematics

Published online by Cambridge University Press:  27 October 2020

PATRICK UFTRING
PATRICK UFTRING*
Affiliation:
DEPARTMENT OF MATHEMATICS TECHNISCHE UNIVERSITÄT DARMSTADT SCHLOSSGARTENSTRAßE 7 64289DARMSTADT, GERMANYE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We characterize Weihrauch reducibility in $ \operatorname {\mathrm {E-PA^{\omega }}} + \operatorname {\mathrm {QF-AC^{0,0}}}$ and all systems containing it by the provability in a linear variant of the same calculus using modifications of Gödel’s Dialectica interpretation that incorporate ideas from linear logic, nonstandard arithmetic, higher-order computability, and phase semantics.

Keywords

Weihrauch reducibilitylinear logicDialectica interpretationnonstandard arithmetichigher-order computability theoryphase semantics

MSC classification

Primary: 03B47: Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
Secondary: 03F52: Linear logic and other substructural logics 03D65: Higher-type and set recursion theory 03D30: Other degrees and reducibilities
Type
Article
Information
The Journal of Symbolic Logic , Volume 86 , Issue 1 , March 2021 , pp. 224 - 261
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

Brattka, V. and Gherardi, G., Weihrauch degrees, omniscience principles and weak computability , this Journal, vol. 76 (2011), no. 1, pp. 143–176.Google Scholar
de Paiva, V., The dialectica categories , Categories in Computer Science and Logic: Proceedings of the Ams-Ims-Siam Joint Summer Research Conference (Gray, J. W. and Ščedrov, A., editors), Contemporary Mathematics, vol. 92, American Mathematical Society, Providence, RI, 1989, pp. 47–62.CrossRefGoogle Scholar
de Paiva, V., The Dialectica categories, Technical Report UCAM-CL-TR-213, University of Cambridge, Computer Laboratory, 1991.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
Ferreira, G. and Oliva, P., Functional interpretations of intuitionistic linear logic , CSL 2009 , (Grädel, E. and Kahle, R., editors), Lecture Notes in Computer Science, vol. 5771, Springer, Berlin, 2009, pp. 3–19.Google Scholar
Ferreira, G. and Oliva, P., Functional Interpretations of Intuitionistic Linear Logic . Logical Methods in Computer Science , vol. 7 (2011), no. 1, pp. 1–22.CrossRefGoogle Scholar
Fujiwara, M., Intuitionistic and uniform provability in reverse mathematics , Ph.D. thesis, Tohoku University, 2015.Google Scholar
Fujiwara, M., Weihrauch and constructive reducibility between existence statements . Computability , to appear.Google Scholar
Girard, J.-Y., Linear logic . Theoretical Computer Science , vol. 50 (1987), no. 1, pp. 1–101.CrossRefGoogle Scholar
Girard, J.-Y., The Blind Spot: Lectures on Logic , European Mathematical Society, Zürich, 2011.CrossRefGoogle Scholar
Hirst, J. L. and Mummert, C., Using Ramsey’s theorem once . Archive for Mathematical Logic , vol. 58 (2019), pp. 857–866.CrossRefGoogle Scholar
Kleene, S. C., Countable functionals , Constructivity in Mathematics (Heyting, A., editor), North-Holland, Amsterdam, 1959, pp. 81–100.Google Scholar
Kohlenbach, U., Applied Proof Theory: Proof Interpretations and Their Use in Mathematics , Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2008.Google Scholar
Kreisel, G., Interpretation of analysis by means of constructive functionals of finite types , Constructivity in Mathematics (Heyting, A., editor), North-Holland, Amsterdam, 1959, pp. 101–128.Google Scholar
Kreisel, G. and Troelstra, A. S., Formal systems for some branches of intuitionistic analysis . Annals of Mathematical Logic , vol. 1 (1970), no. 3, pp. 229–387.CrossRefGoogle Scholar
Kuyper, R., On Weihrauch reducibility and intuitionistic reverse mathematics , this Journal, vol. 82 (2017), no. 4, pp. 1438–1458.Google Scholar
Lindström, P., Aspects of Incompleteness , Lecture Notes in Logic, vol. 10, Springer-Verlag, Berlin, 1997.CrossRefGoogle Scholar
Oliva, P., Computational interpretations of classical linear logic , Wollic 2007 (Leivant, D. and de Queiroz, R., editors), Lecture Notes in Computer Science, vol. 4576, Springer, Berlin, 2007, pp. 285–296.Google Scholar
Scott, D., Algebras of sets binumerable in complete extensions of arithmetic . Recursive Function Theory (Dekker, J. C. E., editor), vol. 5 (1962), pp. 117–121.Google Scholar
Shirahata, M., The dialectica interpretation of first-order classical affine logic . Theory and Applications of Categories , vol. 17 (2006), no. 4, pp. 49–79.Google Scholar
Troelstra, A. S. (editor), Metamathematical Investigation of Intuitionistic Arithmetic and Analysis , Lecture Notes in Mathematics, vol. 344, Springer-Verlag Berlin, 1973.CrossRefGoogle Scholar
Uftring, P., Proof-theoretic characterization of Weihrauch reducibility, Master’s thesis, Department of Mathematics, Universität Darmstadt, 2018.Google Scholar
van den Berg, B., Briseid, E., and Safarik, P., A functional interpretation for nonstandard arithmetic . Annals of Pure and Applied Logic , vol. 163 (2012), no. 12, pp. 1962–1994.CrossRefGoogle Scholar
Weihrauch, K., The TTE-interpretation of three hierarchies of omniscience principles , Informatik Berichte, vol. 130, FernUniversität in Hagen, Hagen, 1992.Google Scholar
Weihrauch, K., The degrees of discontinuity of some translators between representations of the real numbers, Technical Report TR-92-050, International Computer Science Institute, Berkeley, 1992.Google Scholar