Denis Hirschfeldt – Reductions between problems in reverse mathematics and computability theory

UConn Logic Group – Annual Logic Lecture, 8 March 2024

Denis Hirschfeldt (University of Chicago)

"Reductions between problems in reverse mathematics and computability theory"

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.