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.

  • 2
    $\begingroup$ This is not easy to work through. You need some classic results of Solovay and Jockusch on "introreducibility". See Andreas Blass's paper Needed Reals and Recursion in Generic Reals [APAL 109 (2001), 77-88]. $\endgroup$ – François G. Dorais Sep 8 '15 at 2:02
  • $\begingroup$ I've read that paper - I don't immediately see how it addresses the question? (I'm probably missing something obvious.) $\endgroup$ – Noah Schweber Sep 8 '15 at 2:04
  • $\begingroup$ Blass addresses a different question but the paper does have the right tools and references. What you're asking is significantly harder, as far as I know. Maybe you'll also need something like the Baumgartner-Dordal analysis of Hechler forcing to get the right density arguments. $\endgroup$ – François G. Dorais Sep 8 '15 at 2:12
  • $\begingroup$ For the benefit of those who haven't read Blass's paper, he shows that the (1) every hyperarithmetic real is computable in every Hechler generic and (2) the only reals that are computable in every Hechler generic are the hyperarithmetic reals. $\endgroup$ – François G. Dorais Sep 8 '15 at 2:22
  • 1
    $\begingroup$ Why cannot we apply the same argument to trees computable in Kleene's $O$ (given that Kleene's $O$ is arithmetical in $r$) ? $\endgroup$ – Archimondain Oct 6 '15 at 22:48

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.