@article{THESIS,
      recid = {4732},
      author = {Reitzes, Sarah},
      title = {Computability Theory and Reverse Mathematics: Making Use  of the Overlaps},
      publisher = {University of Chicago},
      school = {Ph.D.},
      address = {2022-08},
      number = {THESIS},
      pages = {165},
      abstract = {In this dissertation we look at the overlaps between  computability theory and reverse mathematics. We start off  by examining the reverse mathematical strength of a  variation of Hindman's Theorem ($\textup{HT}$), constructed  by essentially combining $\textup{HT}$ with the Thin Set  Theorem ($\textup{TS}$) to obtain a principle which we call  $\textup{thin-HT}$. $\textup{thin-HT}$ says that every  coloring $c: \mathbb{N} \to \mathbb{N}$ has an infinite set  $S \subseteq \mathbb{N}$ whose finite sums are thin for  $c$, meaning that there is an $i$ with $c(s) \neq i$ for  all finite sums $s$ of distinct elements from $S$. 

Next,  we look at the two-player game introduced by Hirschfeldt  and Jockusch in 2016 in whichwinning strategies for one or  the other player precisely correspond to
implications and  non-implications between $\Pi^1_2$ principles  over
$\omega$-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  $\textup{Q} \to \textup{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.
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 $\Pi^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  $\textup{B}\Sigma^0_2$, uncovering new differences  between
their logical strengths.

Finally, we further  explore the notions of Weihrauch and generalized Weihrauch  reducibility over subsystems of second-order arithmetic  $\Gamma$ that we have defined. We look specifically at  $\Gamma = \RCA_0$ and $\Gamma = \RCA_0^*$. We focus on  particular formulations of $\Sigma^0_1$-induction,  $\Delta^0_2$-induction, and $\Sigma^0_2$-bounding as  $\Pi^1_2$-principles, and how these principles relate to  each other using this novel method of comparison. In  particular, we prove an analogue of Slaman's 2004 result  about the equivalence of $\Sigma^0_n$-bounding and  $\Delta^0_n$-induction in models of $\textup{PA}^- +  \textup{I}\Delta^0_1 + \textup{exp}$, for $n=2$, in our  setting. We present specific results as well as a more  general metatheorem. },
      url = {http://knowledge.uchicago.edu/record/4732},
      doi = {https://doi.org/10.6082/uchicago.4732},
}