Denis Hirschfeldt

Many mathematical principles can be stated in the form “for all X such that C(X) holds, there is a Y such that D(X,Y) holds”, where X and Y range over second-order objects, and C and D are arithmetic conditions. We can think of such a principle as a problem, where an instance of the problem is an X such that C(X) holds, and a solution to this instance is a Y such that D(X,Y) holds. I will discuss notions of reducibility between such problems coming from the closely-related perspectives of reverse mathematics and computability theory.