3
$\begingroup$

This might be an elementary question, and I apologize for that.

I've been dabbling in ordinal analysis / proof theory for a few days, back when I read W. Buchholz, “A new system of proof-theoretic ordinal functions”. Then, I read up on ordinal analysis itself on Wikipedia. There, it states that:

  1. The proof-theoretic ordinal $n$ of some theory $\mathsf{T}$ is the supremum of all ordinals the theory can prove is founded.
  2. The proof-theoretic ordinal for Robinson arithmetic, $\mathsf{Q}$, is $\omega$ (and I'm assuming $\omega$ is defined as $\{0,1,2,\dots\}$.

So my question is:

How do we know that $\omega$ is the proof-theoretic ordinal? Couldn't it be some other ordinal $n$ where $n>\omega$? Is there some method of proving the ordinal is infact the proof-theoretic ordinal?

Thanks in advance!

E: It should hereby be noted that the example of $\mathsf{Q}$, mentioned here, is just an example -- the question applies to other theories, and is a "general" question; i.e. how does this work for other theories?

The question mentioned does help explain that $\omega$ is in fact the proof-theoretic ordinal for $\mathsf{Q}$, but that it does not elaborate on how one knows that $\omega$ is the supremum of $\mathsf{Q}$, as well as elaborating on the method of finding a supremum for any given theory $\mathsf{T}$, as I elaborated above.

$\endgroup$
4
  • $\begingroup$ As wiki says $\omega$ is the set of all natural numbers, so what should $n\ge \omega$ mean? $\endgroup$
    – trula
    Commented Aug 11 at 19:32
  • 2
    $\begingroup$ @trula: $n$ is an ordinal here, not a natural number. $\endgroup$ Commented Aug 11 at 20:15
  • $\begingroup$ In order for it to be $>\omega$, $Q$ would have to prove induction on $\omega$. (Though as Wikipedia alludes to, Q is so weak that concepts such as this struggle to make sense.) $\endgroup$ Commented Aug 12 at 0:39
  • $\begingroup$ This question is similar to: proof theoretic ordinal for Robinson's arithmetic. If you believe it’s different, please edit the question, make it clear how it’s different and/or how the answers on that question are not helpful for your problem. $\endgroup$ Commented Aug 12 at 1:46

1 Answer 1

2
$\begingroup$

How do we know that 𝜔 is the proof-theoretic ordinal?

The same way we know any other sufficiently precise mathematical statement, there is a proof of it.

how does this work for other theories?

To my understanding, the general strategy is to develop an infinitary proof system for the theory and prove a cut elimination theorem for the system. Ordinals are used to measure the height of deductions. A nice overview is Michael Rathjen's The Art of Ordinal Analysis.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .