Question regarding $W$ as not hyperarithmetic

Question

Consider the indexes of all ordinary programs generating functions from $\mathbb{N}^2$ to $\{0,1\}$. If we let $W$ be the set of exactly of all those indexes $e$ such that $\phi_e$ computes a total function that represents a well-order relation (on $\mathbb{N}$) for a recursive ordinal $\geq \omega$ then I think $W$ is not hyperarithmetic. That's because I have read it multiple times on various points.

Now consider the result that sets generated by an OTM (or, I think, reasonably similar model of ordinal comp.) in less than $\omega_{CK}$ time are equivalent to hyperarithmetic. Hopefully I am not making a mistake here, but it seems(?) that this result could be used to show that $W$ is not hyperarithmetic (given the assumption that $\omega_{CK}$ is admissible).

I seems that there is a relatively easy construction that shows that if $W$ was hyperarithmetic then $\omega_{CK}$ wouldn't be admissible. Hence we can conclude that $W$ is not hyperarithmetic. I have a question here that has been bothering a bit for a while, ever since few years ago that I noticed this point.

(Q1) The first concern is of course of "circularity". What I mean is that I have no idea what showing $\omega_{CK}$ as admissible really entails in terms of set theory involved. For example, perhaps(?) showing $\omega_{CK}$ as admissible already necessarily uses $W$ as non-hyperarithmetic as a lemma, which would make the above construction perhaps useful as an aid but void as a result. Since I don't know much in the way of detail here I thought it would be reasonable to ask.

(Q2) Secondly also I am wondering about one other point. We can use $<\omega_{CK}$-time sets as hyperarithmetic to also show for example the result mentioned by Andreas Blass here Mapping between Notations (see the comments below the answer). In one sentence, somewhat informally, the result is that the "mapping" between any two recursive well-orders must be hyperarithmetic.

Once again I am wondering whether there is any "circularity" in using OTM to show such a result or not? I am thinking not but I think it is better to be ask, since it is still just a guess on my part.

Answer 1

Here is a proof that $\omega_1^{\mathrm{ck}}$ is admissible; if someone knows where this fact is proved in the literature, please comment.

First note that there is no $\alpha<\omega_1^{\mathrm{ck}}$ which is admissible: otherwise we have a recursive wellorder $<^*$ in $L_\alpha$ which has length $\alpha$, and this easily contradicts admissibility.

Now toward showing that $\omega_1^{\mathrm{ck}}$ is admissible, the key is first to observe that $\omega_1^{\mathrm{ck}}$ is also the sup of the $\Delta^1_1$ wellorders of $\omega$. For this, use the local/effective version of the Kunen-Martin theorem (Moschovakis, "Descriptive set theory" 2009 Ed, Theorem 2G.2). That is, let $<^*$ be a $\Delta^1_1$ wellorder of $\omega$. Let $T$ be a recursive tree on $\omega^3$ such that for $m,n<\omega$, we have $m<^*n$ iff there is $b\in{^\omega}\omega$ with $(m,n,b)\in[T]$ (the set of infinite branches of $T$). Then let $R$ be the tree of attempts to build an infinite descending sequence through $<^*$, together with witnessing branches through $[T]$. That is, $R$ consists of finite sequences $$(\sigma_0,\sigma_1,\ldots,\sigma_{k-1})$$ where for each $i$, $$\sigma_i=(m_0,m_1,\ldots,m_{i},b_0,b_1,\ldots,b_{i-1})$$ where $m_j<\omega$ for each $i\leq i$, $b_j:i\to\omega$ for each $j\leq i$, and $$(m_j,m_{j+1},b_j)\in T$$ for each $j\leq i$, and if $i<k$ then $\sigma_i$ is ``consistent'' with $\sigma_{i+1}$, meaning that if $$\sigma_{i+1}=(m_0',m_1',\ldots,m_{i+1}',b_0',b_1',\ldots,b_i')$$, then $m_j=m_j'$ for each $j\leq i$, and $b_j=b_j'\upharpoonright i$ for each $j\leq i$. Define an associated relation $S$ on $\omega$ by setting $mSn$ iff either $m\in R$ but $n\notin R$, or $m,n\in R$ and $m$ is a proper extension of $n$ (so e.g. with $\sigma_i,\sigma_{i+1}$ as before, we have $\sigma_{i+1}S\sigma_i$). Then $S$ is wellfounded because $<^*$ is, but a straightforward argument shows that $S$ has rank at least that of $<^*$. Noting that the field of $R$ is recursive, we can convert $S$ into a recursive wellorder of $\omega$ of rank at least that of $S$, via the usual Kleene-Brouwer ordering.

Okay, now suppose that $\omega_1^{\mathrm{ck}}$ is not admissible. Then easily enough, we can fix a $\Sigma_1$ formula $\varphi$ such that $L_{\omega_1^{\mathrm{ck}}}\models$"For all $n<\omega$ there is $\beta\in\mathrm{OR}$ such that $\varphi(n,\beta)$", but there is no $\gamma<\omega_1^{\mathrm{ck}}$ such that $L_\gamma$ models the same statement. We can use this to define a $\Delta^1_1$ wellorder of $\omega$ in ordertype $\omega_1^{\mathrm{ck}}$, a contradiction. For this, put $$(n,m)<^*(n',m')$$ iff $n,m,n',m'<\omega$ and $n\leq n'$, and if $n=n'$ then there is a model $M$ for the language of set theory, such that:

• $M\models$"$V=L$",
• $M$ has wellfounded $\omega$,
• $M\models\varphi(n,\beta)+$"no proper segment of me models $\varphi(n,\beta)$", and
• $\pi^M(m)<\pi^M(m')$, where $\pi^M$ is the $M$-definably least bijection $\omega\to\mathrm{OR}\cap M$.

The model $M$ mentioned above is unique up to isomorphism, by Ville's Lemma / the Truncation Lemma. (That is, any such $M$ is wellfounded, and hence $M\cong L_\alpha$ for the least $\alpha$ such that $L_\alpha\models\varphi(n,\beta)$. For otherwise the wellfounded part of $M$ would be admissible, contradicting the earlier observation.) And it projects to $\omega$, so there is indeed an $M$-definable bijection $\pi:\omega\to\mathrm{OR}\cap M$.

Note that this gives a $\Sigma^1_1$ welorder of $\omega^2$, hence in fact a $\Delta^1_1$ such wellorder, whose length is $\geq\omega_1^{\mathrm{ck}}$, a contradiction.

Answer 2

As (maybe?) a classical computability theorist, here's how I think of this:

From $W$ we can obviously construct a copy of $\omega_1^{CK}$, namely $$\sum_{e\in W}\Phi_e$$ where $\Phi_e$ is the relation computed by $e$. So $W$ computes a well-ordering not isomorphic to any computable well-ordering.

Now a separate result by Spector shows that every hyperarithmetic, or even $\Sigma^1_1$, well-ordering is isomorphic to a computable well-ordering. The standard proof - which can be found in Sacks' Higher recursion theory or Ash/Knight's Computable structures and the hyperarithmetic hierarchy - uses the $\Pi^1_1$-completeness of $W$, but this isn't circular since we don't at this point in the story know that the projective hierarchy doesn't collapse; alternatively, for a more "hands-on" construction see this old answer of mine (taking the "structure parameter" $\mathfrak{A}$ to be something boring, say $(\mathbb{N};+)$). There are also proofs in Beckmann/Pohlers (theorem 3.7) and Pauly (corollary 81), but I'm not familiar with those enough to comment.

All of the above is done without reference to admissibility at all, and - while there is indeed no circularity to worry about here - this may feel more concrete.