Logic seminar

Denis Hirschfeldt, University of Chicago

“Computability Theoretic Reduction between Pi12Principles”

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 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. Examples of particular relevance to this talk are versions of Koenig’s Lemma (such as KL and WKL) and of Ramsey’s Theorem (such as RT2n). We’ll discuss several notions of computability theoretic reducibility between such problems, and their connections with reverse mathematics. Among other things, I will explain how recasting the idea of “every omega-model of P is a model of Q” in terms of games allows us to define a notion of uniform reducibility from Q to P that permits the use of multiple instances of P to solve a single instance of Q. This is joint work with Carl Jockusch.

Please note room change for the term.