Connecticut CT Logic Seminar

Computability Theoretic Reduction between $\Pi^1_2$ Principles

Denis Hirschfeldt (University of Chicago)

Monday, April 14, 2014 4:45 pm
MSB 203

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 $RT^n_2$). 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.