What ordinals are computable using $\Sigma^1_2$ and $\Pi^1_2$ truth

computabilityoraclesordinalssecond-order-logicset-theory

The least non-recursive ordinal is $\omega_1^{CK}$, the Church-Kleene ordinal. But with the benefit of oracles, you can compute more ordinals. Or at least you can with the benefit of sufficiently powerful oracles; this answer shows that‪ using the set of all truths of first-order‬ arithmetic doesn’t buy you any more ordinals.

But my question is, what ordinals do you get if you use the set of all $\Sigma_2^1$ and $\Pi_2^1$ truths? That is to say, let $T$ be the set of all Gödel numbers of true $\Sigma_2^1$ and $\Pi_2^1$ statements in the language of second-order arithmetic. Then what is the least ordinal with no copy computable using $T$ as an oracle?

I realize that ordinal might be difficult to describe exactly, but can we at least put some upper and lower bounds on how big it is? In any case, the reason I ask is because of the connection to these kinds of truths with Schoenfeld’s Absoluteness Theorem.

Best Answer

The set $Th_{\Pi^1_2}(\mathbb{N})$ (which I'll call "$X_2$") computes really really big ordinals; so big, in fact, that there's a decent argument that their supremum $\omega_1^{CK}(X_2)$ is "fundamentally non-concrete."

(Below, I'm only thinking about limit ordinals for simplicity. Also note that this is an elaboration of Yair Hayut's comment above.)

The idea is to use the fact that $L$ has definable Skolem functions; this means that "first-order phenomena" in $L$ can be located relatively easily, namely in a $\Pi^1_2$ way, and so all ordinals corresponding to such will have copies computable from $X_2$. For simplicity, all ordinals are limit ordinals, all theories contain KPi + V=L, and I'll conflate a set $A$ with the corresponding structure $(A; \in\upharpoonright A)$.

  • It's worth noting that there's an important subtlety here. The levels of the arithmetic hierarchy correspond to iterates of the Turing jump, but the levels of the projective hierarchy do not correspond to iterates of the hyperjump. In particular, $\mathcal{O}^\mathcal{O}$ is galactically simpler than $X_2$, and $\omega_1^{CK}(\mathcal{O}^{(n)})$ is just $\omega_{n+1}^{CK}$. (The key point is that $\mathcal{O}^{(n)}\in L_{\omega_{n+1}^{CK}}$.) It's a good exercise to check why the "obvious" proof that $\mathcal{O}^\mathcal{O}\equiv_TX_2$ breaks down (HINT: think about what you're quantifying over ...).

First, the setup:

For $A$ a set, let $D(A)$ be the set of definable elements of $A$ and let $M(A)$ be the Mostowski collapse of $A$. The key thing to think about is the map $$A\mapsto M(D(A)).$$ In general $A$ and $M(D(A))$ may have very little to do with each other; however, a couple very nice things happen in case $A=L_\theta$ for some ordinal $\theta$:

  • Since $L_\theta$ has definable Skolem functions, we have $D(L_\theta)\preccurlyeq L_\theta$ and so $M(D(L_\theta))\equiv L_\theta$.

  • By condensation we have $M(D(L_\theta))=L_{\theta'}$ for some $\theta'\le\theta$, with $\theta'=\theta$ iff $D(L_\theta)=L_\theta$ (that is, iff $L_\theta$ is pointwise-definable).

(In fact, we also know that $M(D(M(D(L_\theta))))=M(D(L_\theta))$ - that is, after applying $M\circ D$ we get something pointwise-definable - but that won't be needed here.)

Now, here's how the above observations lead to a lot of pointwise-definable levels of $L$.

Suppose $T$ is a theory and $L_\theta$ is the least level of $L$ satisfying $T$. Then since $L_{\theta'}$ also satisfies $T$ we must have $\theta'=\theta$ - that is, we must have $L_\theta$ be pointwise-definable.

In particular, $L_{\omega_{17}^{CK}}$ is pointwise-definable: take $T$ to be KPi + V=L + "There are sixteen admissible ordinals." Similarly, $L_{\beta_0}$ are pointwise-definable.

Indeed, it turns out that the set of $\alpha$ such that $L_\alpha$ is pointwise-definable is cofinal in $\omega_1^L$ (see Hamkins/Linetsky/Reitz).

OK, so what?

Well, if $L_\alpha$ is pointwise-definable, then $Th(L_\alpha)$ computes a copy of $\alpha$ - simply ask $Th(L_\alpha)$ which formulas correspond to ordinals and how they should be ordered. So in particular, if $L_\alpha$ is pointwise-definable and $Th(L_\alpha)\le_TX_2$ then $\alpha<\omega_1^{CK}(X_2)$.

So we wrap up with the following observation. For a theory $T$, let $$\alpha_T=\min\{\beta: L_\beta\models T\}$$ (with the convention that $\alpha_T=0$ if no level of $L$ satisfies $T$). Then we have:

Theorem: If $T$ is computable, then $Th(L_{\alpha_T})$ is $\Delta^1_2$.

(Proof: The point is that $L_{\alpha_T}$ is in fact the unique level of $L$ satisfying $T$ + "$T$ has no transitive models." So we have $L_{\alpha_T}\models\varphi$ iff every well-founded model of $T$ + "$T$ has no well-founded models" satisfies $\varphi$ iff there is some well-founded model of $T$ + "$T$ has no well-founded models" which satisfies $\varphi$, and these last two clauses are $\Pi^1_2$ and $\Sigma^1_2$ respectively.)

Putting this all together, we get $\alpha_T<\omega_1^{CK}(X_2)$ for every computable theory $T$. For example, $\beta_0<\omega_1^{CK}(X_2)$ (take $T=ZFC -P + V=L$). This more-or-less precludes any "from-below" characterization of $\omega_1^{CK}(X_2)$; we're left with characterizations in terms of reflection principles and their ilk, which can be a bit tautological. So ultimately I'd take this as an argument that this ordinal is simply too huge to be well-described.

Related Question