A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$

Question

In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does this via a somewhat involved process (described below) which uniformly in $\alpha \leq_{\mathscr{O}} w^{ck}_1$ produces a computable tree $T^{\alpha}_0 \subset \omega^{< \omega}$ containing only $\alpha$-subgenerics. However, at the end of the notes Harrington claims he can produce a computable tree whose elements are $\alpha$-subgeneric for all $\alpha \leq_{\mathscr{O}} w^{ck}_{1}$. I'm not seeing how you get this. Can anyone help me figure out how this can be proved?

Yes, you can go ahead and define these non-standard ordinal notations which must have well-ordered initial segment of length $\omega_1^{CK}$ which Harrington refers to (says something about taking the leftmost path). However, I don't see how this gets you a computable tree all of whose paths are $< \omega_1^{CK}$ sub-generic since the method he uses to produce a computable tree of $\alpha$-subgenerics -- projecting down a tree $T_\alpha \leq_T 0^{(\alpha)}$ -- can't be directly applied to a path through $\mathscr{O}$ since that would allow the construction of a computable tree with only a single path that was $< \omega_1^{CK}$-subgeneric contradicting the fact that if $f$ is the unique path through a computable tree $f$ is hyperarithmetic.

In case it helps, I've included a bit of a further explanation of the argument as I understand it below.

---

$\alpha$-subgeneric

$f \in \omega^{\omega}$ is $\alpha$-subgeneric for $\alpha \in \mathscr{O}$ if

• $(\forall \beta \leq_{\mathscr{O}} \alpha)(0^{(\beta)} \oplus f \equiv_T f^{(\beta)})$
• $(\forall X \leq_T 0^{(\alpha)})(\forall \beta \leq_{\mathscr{O}} \alpha)( X \leq_T f^{(\beta)} \implies X \leq_T 0^{(\beta)} $

---

The way he constructs such reals is (I presume since it seems to work and it's the only approach in the notes) is to start with a tree $T_\alpha$ computable in $0^{(\alpha)}$ and at each level $\beta \leq_{\mathscr{O}} \alpha$ building $T_\beta$ computable in $0^{(\beta)}$ to produce an ultimate tree $T_0$ with $[T_0]$ homeomorphic to $[T_\alpha]$ and with all paths through $T_\alpha$ being $\alpha$-subgeneric.

The basic idea is to handle this one step at a time by combining a kind of jump-inversion to build $T_\beta$ homeomorphic to $T_{\beta+1}$ while at the same time trying to force (in local forcing) $\Sigma^0_1(0^{(\beta)})$ facts. There are some tricky issues that aren't covered in the notes but if you do it right the local forcing plus the assumptions about subgenericity for $T_{\beta+1}$ (and some nasty utility lemmas to keep the notations well-behaved at limit levels) are enough to ensure that you end up with $\alpha$-subgeneric paths through $T_0$

And that's all nicely uniform, so we can assume that we have $T^{\alpha}_0$, a computable tree with only $\alpha$-subgeneric paths (e.g. say only a single one) uniformly in $\alpha$. But I don't see what lets us put them together to get a computable tree which is $< \omega_1^{CK}$ subgeneric -- and that argument must somehow ensure that the tree we build has a perfect set of paths.

Answer 1

So I emailed back and forth with Leo about this and, after the usual part where I drag the conversation into confusion by getting overly specific, I believe I understand how this is supposed to work.

The really short answer is that, when you use a non-standard $\alpha$ you no longer get that $[T_0]$ is homeomorphic to $[T_\alpha]$ but merely that it contains an image of $[T_\alpha]$ so you can't limit the paths through $T_0$ anymore but you can guarantee that every path through $T_0$ goes through trees defined as in the original construction up through $\omega_{CK}^1$. Then, (mistakes here are mine not Leo's) since you can use a set variable to code the complete sequence of trees/maps/etc between $T_\alpha$ and $T_0$ you can write a $\Sigma^1_1$ formula with free variable $\alpha$ asserting that the construction succeeds when you start with some tree $T$ as $T_\alpha$ and that every path through this $T_\alpha$ is mapped down to a path through $T_0$. Since you can't give a $\Sigma^1_1$ definition of a path through $\mathscr{O}$ it follows that there must be a non-standard $\alpha$ which results in a construction which leaves $[T_0]$ non-empty and the particular tree $T_0$ can be read off the witness to the $\Sigma^1_1$ formula.

---

For a longer answer:

In the original construction, what we actually do is simultaneously build the sequence of trees $T_\beta, \beta < \alpha$ and a sequence of functionals $\Gamma^{\gamma}_{\beta}$ that homeomorphically map $[T_\gamma]$ down to $[T_\beta]$ (when $\gamma \geq \beta$). This is done via the recursion theorem in the normal fashion for transfinite recursion arguments (we define $\Phi_{f(e)}$ assuming that $\Phi_e$ gives our functional but applying one more stage).

Now there is [2] a $\Sigma^1_1$ class of 'non-standard' ordinal notations $\mathscr{O}^{*}$ such that the standard predecessors of any $\alpha \in \mathscr{O}^{*} - \mathscr{O}$ form a path through $\mathscr{O}$. We take $\alpha$ to be such an element. Moreover, $\mathscr{O}^{*}$ has the property that any non-empty hyperarithmetic subset has a least element.

Fix some arithmetic tree $T_\alpha$ (can be extended to hyperarithmetic easily) and perform the construction as before. Now, since $\alpha$ isn't a true ordinal notation we won't be able to ensure that the resulting construction has all the properties of the original but since the construction is in effect [1] entirely local we can prove that everything works as desired on the standard part.

Specifically, by transfinite induction, we can prove that whenever $\gamma, \beta < \omega_{CK}^1$ (true notations) then $\Gamma^{\gamma}_{\beta}$ really is a homeomorphism of $[T_\gamma]$ with $[T_\beta]$ and that the image of any path under $\Gamma^{\gamma}_{0}$ is $\gamma$ sub-generic. This holds because the properties used (in effect [1]) don't depend on $\alpha$ so don't care if it's non-standard. Thus, any path through $T_0$ really will be the image of a path in $T_\gamma$ for each $\gamma < \omega_{CK}^1$ and thus $\gamma$-subgeneric for each $\gamma$. This leaves only the surprisingly difficult task of proving that $[T_0]$ isn't empty. For, our homeomorphism no longer extends all the way up to $T_\alpha$ and it's not even totally obvious what it would even mean to extend the argument to non-standard notations.

However, given an arithmetic [3] tree $T$ we can define a predicate $Q(X,\alpha)$ that holds just if for all $\beta < \alpha$ $X^{[\beta]}$ codes a set $T_\beta$, $0^{\beta}$ (i.e. a solution to the predicate defining the $H$ sets for $\beta$) and functionals $\Gamma^{\beta}_{\beta'}$ for all $\beta' < \beta$ and these sets all relate to each other as demanded by the application of the construction to the tree $T$ at the notation $\alpha$ and have $T_\alpha$ equal to $T$. In particular, we demand that whenever $\sigma \in T_\gamma, \beta < \gamma$ then $\Gamma^{\gamma}_\beta(\sigma) \in T_\beta$.

We can define $Q$ to be arithmetic. Now, consider the property

$$ \alpha \in \mathscr{O}^{*} \land (\exists X)Q(X, \alpha)$$.

This property is $\Sigma^1_1$ as $\mathscr{O}^{*}$ is $\Sigma^1_1$. Moreover, since the construction in fact succeeds at every genuine ordinal notation, this property holds of every $\beta \in \mathscr{O}$. However, as $\mathscr{O}$ is properly $\Pi^1_1$ it must also hold of some element $\alpha \in \mathscr{O}^{*} - \mathscr{O}$. Now consider a witness $X$ to $Q(X, \alpha)$ and note that $\Gamma^{\alpha}_0(f) \in [T_0]$ for any $f \in [T_\alpha]. This gives us that $[T_0]$ is non-empty.

Note that if we'd wanted to express the claim that $\Gamma^{\gamma}_\beta$ was a genuine homeomorphism we couldn't have made $Q$ hyperarithmetic since well-foundedness isn't a hyperarithmetic property.

---

[1]: When I say that the properties 'in effect' don't depend on $\alpha$ it's still true that we use $\alpha$ to define a computable function that, for each $\beta$, tells us that $T_\beta$ should copy all strings of length $n$ from some $T_\lambda$ for some $\lambda$ above $\beta$. However, this all works out in a unproblematic way for our standard notations as there is no hyperarithmetic infinite decreasing sequence below $\alpha$.

[2]: see Feferman and Spector, Incompleteness Along Paths in Progressions of Theories