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

154 Views Asked by At

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$ (see question #3222781)

  • 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$.

1

There are 1 best solutions below

7
On

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