What is the proof-theoretic ordinal of true arithmetic?

219 Views Asked by At

The proof theoretic ordinal of $PA$ is $\epsilon_0$. My question is, what is the proof-theoretic ordinal of true arithmetic, i.e. $Th(\mathbb{N})$?

I’m assuming you get something bigger than $\epsilon_0$ and smaller than $\Gamma_0$, the Feferman-Schutte ordinal which is significantly less than $\omega_1^{CK}$. I say this because Feferman and Schutte constructed infinitary deductive systems for ramified second-order arithmetic which included the omega-rule, and those systems had proof-theoretic ordinal $\Gamma_0$. And true arithmetic is obtained by adding the omega-rule to $PA$.

Would it be cleaner to ask what the proof-theoretic ordinal of $ACA_0$ plus the omega rule is, since you can then speak more explicitly about a relation being a well-order?

1

There are 1 best solutions below

7
On

This isn't really a question that makes sense. Let me illustrate this with two common interpretations of the term:

  • One idea is that "The proof-theoretic ordinal of $\mathsf{PA}$ is $\le\epsilon_0$" means "$\mathsf{PRA}$ + an induction scheme along a natural notation for $\epsilon_0$ proves $Con(\mathsf{PA})$." So analogously we would ask how much induction we need to prove the consistency of true arithmetic. However, the above relies on the expressibility of $Con(\mathsf{PA})$ in the first place. Since per Tarski true arithmetic isn't even definable, we can't even set up the relevant question here.

  • On the other hand, we could just ask something like: "Which ordinal notations does our theory prove the $\Sigma_1$ induction scheme for?" Here Tarski poses no barrier, but the answer trivializes in a different way. True arithmetic proves induction along all computable well-orders! So by this account the proof-theoretic ordinal of true arithmetic would just be $\omega_1^{CK}$.

So there is no real way to make sense of "the proof-theoretic ordinal of true arithmetic." Any notion of proof-theoretic ordinal relies on the theory in question being reasonably simple, which true arithmetic isn't.