- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
The characterization of Weihrauch reducibility in systems containing
Journal of Symbolic Logic 86 (1):224-261 (2021)
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.My notes
Similar books and articles
The characterization of Weihrauch reducibility in systems containing e-pa ω + qf-ac0;0.Patrick Uftring - forthcoming - Journal of Symbolic Logic:1-35.
The open and clopen Ramsey theorems in the Weihrauch lattice.Alberto Marcone & Manlio Valenti - 2021 - Journal of Symbolic Logic 86 (1):316-351.
Weihrauch Goes Brouwerian.Vasco Brattka & Guido Gherardi - 2020 - Journal of Symbolic Logic 85 (4):1614-1653.
Searching for an analogue of atr0 in the Weihrauch lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
On Weihrauch reducibility and intuitionistic reverse mathematics.Rutger Kuyper - 2017 - Journal of Symbolic Logic 82 (4):1438-1458.
Using Ramsey’s theorem once.Jeffry L. Hirst & Carl Mummert - 2019 - Archive for Mathematical Logic 58 (7-8):857-866.
Borel reducibility and Hölder(α) embeddability between Banach spaces.Longyun Ding - 2012 - Journal of Symbolic Logic 77 (1):224-244.
A characterization of the Δ⁰₂ hyperhyperimmune sets.Roland Sh Omanadze & Andrea Sorbi - 2008 - Journal of Symbolic Logic 73 (4):1407-1415.
On the (semi)lattices induced by continuous reducibilities.Arno Pauly - 2010 - Mathematical Logic Quarterly 56 (5):488-502.
Weihrauch degrees, omniscience principles and weak computability.Vasco Brattka & Guido Gherardi - 2011 - Journal of Symbolic Logic 76 (1):143 - 176.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
A Characterization of the $\Delta _{2}^{0}$ Hyperhyperimmune Sets.Roland Sh Omanadze & Andrea Sorbi - 2008 - Journal of Symbolic Logic 73 (4):1407 - 1415.
Effective choice and boundedness principles in computable analysis.Vasco Brattka & Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (1):73-117.
A New Reducibility between Turing‐ and wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
Effective Borel measurability and reducibility of functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
Analytics
Added to PP
2021-07-11
Downloads
17 (#843,162)
6 months
7 (#425,192)
2021-07-11
Downloads
17 (#843,162)
6 months
7 (#425,192)
Historical graph of downloads
Citations of this work
Reduction games, provability and compactness.Damir D. Dzhafarov, Denis R. Hirschfeldt & Sarah Reitzes - 2022 - Journal of Mathematical Logic 22 (3).
References found in this work
Interpretation of analysis by means of constructive functionals of finite types.Georg Kreisel - 1959 - In A. Heyting (ed.), Constructivity in Mathematics. Amsterdam: North-Holland Pub. Co.. pp. 101--128.
Formal systems for some branches of intuitionistic analysis.G. Kreisel - 1970 - Annals of Mathematical Logic 1 (3):229.
A functional interpretation for nonstandard arithmetic.Benno van den Berg, Eyvind Briseid & Pavol Safarik - 2012 - Annals of Pure and Applied Logic 163 (12):1962-1994.
Classical Consequences of Continuous Choice Principles from Intuitionistic Analysis.François G. Dorais - 2014 - Notre Dame Journal of Formal Logic 55 (1):25-39.
Using Ramsey’s theorem once.Jeffry L. Hirst & Carl Mummert - 2019 - Archive for Mathematical Logic 58 (7-8):857-866.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-4c2ch uwo