# Is there a simple oracle that computes the ordinal $\beta_0$?

There is a certain large countable ordinal referred to in the literature as $$\beta_0$$. It was first discovered by Paul Cohen, and here are some equivalent characterizations of it:

• The smallest ordinal $$\beta$$ such that $$L_\beta$$ is a model of $$ZFC-P$$

• The smallest ordinal $$\beta$$ such that $$L_\beta\cap P(\mathbb{N})=L_{\beta+1}\cap P(\mathbb{N})$$

• The smallest $$\omega$$-admissible ordinal

This is a non-recursive ordinal, which implies that there is no notation for it in Kleene's $$O$$. But we can modify Kleene's $$O$$ to allow the use of an oracle $$A$$. Let's call this modification $$O_A$$. Then this answer shows that for any countable ordinal $$\alpha$$, there exists an oracle $$A$$ such that $$O_A$$ has a notation for $$\alpha$$.

But the proof of that result involves defining $$A$$ in terms of $$\alpha$$. My question is, is there a "naturally-occurring" oracle $$A$$ such that $$O_A$$ has a notation for $$\beta_0$$? By naturally-occurring I don't mean anything too precise, I just mean some simple oracle whose definition does not refer to $$\beta_0$$.

Here's an oracle which is defined in terms of $$\beta_0$$ but is nonetheless nontrivial:

Since for any sufficiently closed ordinal $$\alpha$$ the structure $$(L_\alpha;\in)$$ has definable Skolem functions, we know that the Mostowski collapse $$M_\alpha$$ of the substructure consisting of the definable elements of any such $$L_\alpha$$ is pointwise-definable. By Condensation, this $$M_\alpha$$ is itself a level of $$L$$ - call it "$$L_{\mu(\alpha)}$$."

But now it follows that for any theory $$T$$ which is satisfied by some level of $$L$$, the least level $$L_{\alpha_T}$$ of $$L$$ satisfying $$T$$ is pointwise definable (consider $$L_{\mu(\alpha_T)}$$). In particular, $$L_{\beta_0}$$ is pointwise definable.

Finally, if $$L_\gamma$$ is pointwise definable, we can compute a copy of $$\gamma$$ from $$Th(L_\gamma)$$: think about ordering the set of formulas which $$Th(L_\gamma)$$ proves defines an ordinal by $$Th(L_\gamma)$$-provable length (technically this is a preorder but we can then take equivalence classes). So $$Th(L_{\beta_0})$$ is a canonical oracle which computes a copy of $$\beta_0$$.

EDIT: we can also get away with talking about (fragments of) theories of different structures. In particular, we can show that the set of true $$\Pi^1_2$$ sentences computes a copy of $$\beta_0$$. However, this is massive overshooting, since it also computes (for example) the height of the smallest transitive model of ZFC + "There is a proper class of supercompact cardinals" (assuming that has a transitive model in the first place) and so on.

What about a bit lower? Well, unfortunately then we galactically undershoot: the set of true $$\Pi^1_1$$ sentences is basically just Kleene's $$\mathcal{O}$$, and it's not hard to show that $$\omega_1^{CK}(\mathcal{O})=\omega_2^{CK}$$ and more generally that $$\omega_1^{CK}(\mathcal{O}^a)=\omega_2^{CK}(a)$$ for any real $$a$$. In particular, even iterating the hyperjump (= the map $$a\mapsto\mathcal{O}^a$$) won't usefully approach $$\beta_0$$ - we'd need to iterate it $$\beta_0$$-many times!

• Precisely: suppose $$\alpha<\beta_0$$. Then there is some copy $$A$$ of $$\alpha$$ such that the "hyperjump sequence along $$A$$" (which I'll denote "$$HJ^A$$") does not compute a copy of $$\beta_0$$. Here $$HJ^A$$ is the unique $$A$$-indexed sequence of sets $$HJ^A=(HJ^A(k))_{k\in A}$$ such that for each $$n\in A$$ we have $$HJ^A(k)=\mathcal{O}^{\bigoplus_{m\in A, m<_Ak}HJ^A(m)}.$$

In particular, I'm not aware of any natural fragment of true second-order arithmetic which computes a copy of $$\beta_0$$ but doesn't compute copies of ordinals "much bigger" than $$\beta_0$$.

The point is that even though the structure of second-order arithmetic looks more natural than initial segments of $$L$$, it's hiding a lot of complexity - to the point that as we climb higher up the theory, we shoot dramatically up the ordinals. I think one of the takeaways of the study of $$L$$ is that it's often levels of the $$L$$-hierarchy (or of similar hierarchies), rather than various arithmetics, which usefully pin down ordinals. In particular I think this helps de-mystify and motivate fine structure from a computable-structure-theoretic perspective ("do you want to control computations of ordinals? then look no further!").

• Can you explain your comment in the other thread: "Again, though, galactic overshooting (and the fact that without further set-theoretic hypotheses it's not even absolute renders it further bizarre)"? The absoluteness part. – Keshav Srinivasan Nov 8 '19 at 17:43
• @KeshavSrinivasan For example, the sentence "There is a non-constructible real" is expressible in second-order arithmetic (in particular, it's $\Sigma^1_3$). Any model of ZFC which thinks that this sentence is part of true second-order arithmetic (e.g. any model of ZFC+V=L) has a forcing extension which thinks it's not. Enough large cardinals imply that the true second-order theory of arithmetic is unchanged by forcing, but we need a lot of power there. – Noah Schweber Nov 8 '19 at 17:45
• And I assume the set of $\Pi^1_2$ truths and $\Sigma^1_2$ truths is not enough to get you $\beta_0$? – Keshav Srinivasan Nov 9 '19 at 3:54
• Does the set of $\Pi^1_2$ truths and $\Sigma^1_2$ truths even get you beyond Church-Kleene? – Keshav Srinivasan Nov 10 '19 at 14:44
• I posted a follow-up question: ‪math.stackexchange.com/q/3433590/71829 – Keshav Srinivasan Nov 13 '19 at 22:26