### Files

### 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.

### Details

### Actions

### Statistics

from

to