##
Reduction Games, Provability, and Compactness

Status: to appear in the *Journal of Mathematical Logic*

Availability:
preprint

**Abstract.** 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
Π^{1}_{2}
principles over ω-models of RCA_{0}. They also introduced a
version of this game that similarly captures provability over
RCA_{0}. We
generalize and extend this game-theoretic framework to other formal
systems, and establish a certain compactness result that shows that if an
implication Q → P between two principles holds, then
there exists a winning strategy that achieves victory in a number of moves
bounded by a number independent of the specific run of the game. This
compactness result generalizes an old proof-theoretic fact noted by
H. Wang (1981), and has applications to the reverse mathematics of
combinatorial principles.

We also demonstrate how this framework leads to a new kind of analysis
of the logical strength of mathematical problems that refines both
that of reverse mathematics and that of computability-theoretic
notions such as Weihrauch reducibility, allowing for a
kind of fine-structural comparison between Π^{1}_{2}
principles that
has both computability-theoretic and proof-theoretic aspects, and can
help us distinguish between these, for example by showing that a
certain use of a principle in a proof is "purely proof-theoretic",
as opposed to relying on its computability-theoretic strength.

We give examples of this analysis to a number of principles at the
level of BΣ^{0}_{2}, uncovering new differences
between
their logical strengths.

drh@math.uchicago.edu