The least admissible above a dominating real

Question

Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, and the ordering is given by $$(p, f)\le (q, g)\iff p\supseteq q, \forall n(f(n)\ge g(n)), \mbox{ and } \forall k\in dom(p)\setminus dom(q)(p(k)>g(k)).$$ Let $r$ be the real added by this forcing; my question is,

What is $\omega_1^r$ (the least ordinal with no copy computable from $r$)?

Clearly $\omega_1^r$ is at least $\omega_2^{CK}$: this is because if $T$ is a computable tree, then $T$ is ill-founded iff $T_{\hat{r}}$ is ill-founded for some $r'$ which is equal to $r$ on all but finitely many values, where $T_{\hat{r}}$ is the set of nodes $\sigma$ on $T$ such that $\sigma(i)<\hat{r}(i)$ for all $i\in dom(\sigma)$. The tree $T_{\hat{r}}$ is computable from $r$, and is effectively finitely branching, so it has a path computable from $r'$. So Kleene's $\mathcal{O}$ is arithmetical in $r$, and hence $\omega_1^{CK}$ has a copy arithmetical in $r$ - which means $\omega_1^{CK}$ has a copy computable in $r$.

My instinct is that $\omega_1^r$ should be the second admissible, $\omega_2^{CK}$, but I don't see how to prove this.

Answer 1

I think that the answer is the least $Σ^1_1$-reflecting ordinal. The least $Σ^1_1$-reflecting ordinal is also the least non-Gandy ordinal, the closure ordinal for $Σ^1_1$ inductive definitions, and the closure ordinal for $Σ^0_2$-games on integers, and is above the least ordinal that is stable up to an admissible.

While I do not quite prove this, I prove closely related results in my paper "Finitistic Properties of High Complexity", available at http://web.mit.edu/dmytro/www/FinitismPaper.htm (or without a few corrections at https://arxiv.org/abs/1707.05772).

Let us say that a proposition $P$ holds for every sufficiently fast-growing $A∈ω^ω$ iff $∃A'∈ω^ω \, ∀A∈ω^ω \, (∀t \, A'(t)≤A(t) ⇒ P(A)))$. Note that but for having an arbitrary initial finite segment, a Hechler real is sufficiently fast-growing for every $Π^1_1$ proposition (and one can go further to the extent we have enough generic absoluteness). However, non-arbitrariness of the initial segments of $A'$ is needed to allow uniformly $Σ^0_1(A)$ definitions, which are important to the paper (and its motivation).

We have:
* For every real $x$, an $r⊂ω$ is $Π^1_1(x)$ iff $r$ is uniformly in $y$ computably enumerable from $x,y$ for every sufficiently fast-growing (relative to $x$) $y∈ω^ω$. (Theorem 2.2; see also Theorem 2.3; it is likely that "uniformly" is optional, and similarly below).
* A real number is arithmetically definable from a Hechler real iff it is recursive in a finite hyperjump of 0 (Theorem 2.4, including its proof).
* An $r⊂ω$ is uniformly c.e. from every $x,y$ for a sufficiently fast-growing $x∈ω^ω$ and a sufficiently fast-growing (relative to $x$) $y$ iff $r$ is many-to-one reducible to the game quantifier for $Σ^0_2$-games on integers (Theorem 3.2).

To complete the proof for the answer, one would need:
* A literature check that an $r⊂ω$ and its complemement are both many-to-one reducible to the game quantifier for $Σ^0_2$-games on integers iff $r∈L_κ$ where $κ$ is the least $Σ^1_1$-reflecting ordinal. p.239 of Subsystems of Second Order Arithmetic (Second Edition) vaguely refers to $Σ^1_1$-reflecting ordinals and cites Weak axioms of determinacy and subsystems of analysis II ($Σ^0_2$ games) which uses different terminology and has further citations.
* A proof that if a real number (in $V$) is $Π^1_1$ in a Hechler real, then it is uniformly $Π^1_1$ in every sufficiently fast-growing element of $ω^ω$. I do not have a proof, but it might be a straightforward application of genericity.
* A proof that using reals in $V$ that are $Δ^1_1$ in a Hechler real $r$ does not underestimate $ω_1^r$.

A generalization of this question is to consider an $n$-step iteration adding a Hechler real $r_i$ at each step, and ask about descriptive complexity relative to the sequence $r$. I think that the answer would correspond to determinacy (and complexity of the strategies) for levels in the difference hierarchy of $Σ^0_2$-sets (which also appears to correspond to chains of $Σ_1$-elementary substructures), and my paper has partial results in that direction.