Logic Seminar

Richard ShoreCornell University
Almost Theorems of Hyperarithmetic Analysis

Tuesday, September 17, 2019 - 2:55pm
Malott 206

$Hyp(X)$, the collection of all sets hyperarithmetic in $X$ consists of those sets recursive in some iteration $X^{(\alpha)}$ of the jump of $X$ for $\alpha$ an ordinal recursive in $X$. These are also the sets $\Delta_{1}^{1}$ in $X$. A theorem (theory) $T$ is a THA, theorem (theory) of hyperarithmetic analysis if

  • For every $X\subseteq\mathbb{N}$, $(\mathbb{N},HYP(X))\vDash T$ and
  • If $(\mathbb{N},S)\vDash T$ and $X\in S$ then $HYP(X)\subseteq S$.

Our study of such theorems in graph theory led us to a new class of theorems and theories.
We began with a result about locally finite graphs appearing in the study of variations on Halin's infinite ray theorem. When combined with ACA$_{0}$ it turned out to be a THA. On its own, however, it is very weak. It is $\Pi_{1}^{1}$ conservative and $r$-$\Pi_{2}^{1}$ conservative over RCA$_{0}$ and so (over RCA$_{0}$) does not imply ACA$_{0}$ (or even WKL$_{0}$ or DNR$_{0}$). Moreover, even with the addition of WKL$_{0}$ it does not imply ACA$_{0}$. We named such theorems (theories) $T$ almost THA if $T+ACA_{0}$ (arithmetic comprehension) is a THA but it itself is not. We then realized that there is a general way of converting many known THA's to almost THA's and a general notion of forcing that can be used to prove all the conservation results and more for all the examples.