arXiv:1511.05189 Abstract | arXiv Analytics

arXiv:1511.05189 [math.LO]Abstract References Reviews Resources

On Weihrauch Reducibility and Intuitionistic Reverse Mathematics

Published 2015-11-16Version 1

We show that there is a strong connection between Weihrauch reducibility on one hand, and provability in EL_0, the intuitionistic version of RCA_0, 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 EL_0 together with Markov's principle, and that Weihrauch reducibility is captured by an affine subsystem of EL_0 plus Markov's principle.

Categories: math.LO

Subjects: 03B30, 03B20, 03D30, 03F35

Keywords: weihrauch reducibility, intuitionistic reverse mathematics, plus markovs principle, intuitionistic version, provability

Related articles: Most relevant | Search more

arXiv:1910.13186 [math.LO] (Published 2019-10-29)

Completion of Choice

Vasco Brattka, Guido Gherardi

arXiv:1611.03134 [math.LO] (Published 2016-11-09)

Using Ramsey's Theorem Once

Jeffry L. Hirst, Carl Mummert

arXiv:2105.01719 [math.LO] (Published 2021-05-04)

Reverse mathematics and Weihrauch analysis motivated by finite complexity theory