Abstract

Weihrauch complexity can be seen as a more uniform version of different varieties of reverse mathematics. This is true, in particular, for classical reverse mathematics (in the sense of Friedman and Simpson) as well as for constructive reverse mathematics (in the sense of Ishihara) and probably for other varieties too. In both cases “more uniform” only holds modulo certain additional differences. In both cases the question appears, when certain Weihrauch degrees legitimately correspond to certain axiom systems. In some cases, such as WKL , there is a widely accepted answer to this question. In other cases, such as ATR or induction and boundedness principles, this is debated somewhat controversially. We will propose a thesis that can be used as a necessary condition for legitimacy and it roughly says that the theories of the respective axiom systems should correspond to the lower cones of the corresponding Weihrauch degrees. This leads to a discussion of closure under compositional product and parallelization.