Imagen de Portada
Código QR

ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS.

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 provabili...

Descripción completa

Publicado en:Journal of Symbolic Logic Vol. 82; no. 4; pp. 1438 - 1459
Autor principal: KUYPER, RUTGER
Formato: Artículo
Publicado: Cambridge University Press Dec2017
Materias:
Reverse mathematics
Mathematical logic
Reversible computing
Mathematical analysis
Intuitionistic mathematics
Acceso en línea:Ver este registro en EBSCOhost
Sumario: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.