March 9
Damir Dzhafarov,
University of Connecticut
Reduction games, provability, and compactness
Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between given $\Pi^1_2$ principles over $\omega$-models of ${\rm RCA}_0$. They also introduced a version of this game that similarly captures provability over (full) ${\rm RCA}_0$. We generalize this game for provability over arbitrary subsystems of second-order arithmetic, and establish a compactness argument that shows that certain winning strategies can always be chosen to win in a number of moves bounded by a number independent of the instance of the principles being considered. Our compactness result also generalizes an old proof-theoretic fact due to H. Wang, and has a number of other applications. This is joint work with Denis Hirschfeldt and Sarah Reitzes.