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!").

  • $\begingroup$ 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. $\endgroup$ – Keshav Srinivasan Nov 8 '19 at 17:43
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Nov 8 '19 at 17:45
  • $\begingroup$ And I assume the set of $\Pi^1_2$ truths and $\Sigma^1_2$ truths is not enough to get you $\beta_0$? $\endgroup$ – Keshav Srinivasan Nov 9 '19 at 3:54
  • $\begingroup$ Does the set of $\Pi^1_2$ truths and $\Sigma^1_2$ truths even get you beyond Church-Kleene? $\endgroup$ – Keshav Srinivasan Nov 10 '19 at 14:44
  • $\begingroup$ I posted a follow-up question: ‪math.stackexchange.com/q/3433590/71829 $\endgroup$ – Keshav Srinivasan Nov 13 '19 at 22:26

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.