3
$\begingroup$

The proof-theoretic ordinal of first-order arithmetic ($\mathsf{PA}$) is $\varepsilon_{0}$. However, in pages 3 and 4 of Andreas Weiermann's Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results, he mentions it is possible to define a primitive recursive well-ordering $\prec$ whose order type is $\omega$ but such that $\mathsf{PA}$ cannot prove transfinite induction along $\omega$. No reference is provided other than the name Kreisel.

First, does anyone know how to construct $\prec$, or perhaps may provide a modern reference where this is accomplished?

Second, if such a pathological well-ordering $\prec$ exists, could not we use it to prove the consistency of $\mathsf{PA}$ by using finitary methods plus transfinite induction along $\prec$? If this is the case, why do we define the proof-theoretic ordinal of a theory $T$ the way we do, and not simply as

The least ordinal $\alpha$ such that transfinite induction along $\alpha$ (plus finitary methods) proves the consistency of $T$.

I guess this would depend on the ordinal notation used; and since the definition of proof-theoretic ordinal does not depend on a notation, it is then more robust. Is that it, or there is more?


EDIT: I just found out that my question is also answered in Math Overflow. There are very informative and useful answers provided there.

$\endgroup$

1 Answer 1

3
$\begingroup$

Re: your first question, this is disappointingly easy: writing "$Con(\mathsf{PA},x)$" for "There is no proof of a contradiction in $\mathsf{PA}$ of length $<x$," consider the relation given by $$a\prec b\quad \equiv \quad (a<b)\leftrightarrow Con(\mathsf{PA}, \min\{a,b\}).$$ Intuitively, this describes the following process: we start listing the natural numbers in their usual order, and if we ever see a contradiction in $\mathsf{PA}$ we shift tactics (so to speak) and build a descending chain. For example, if there were a shortest proof of a contradiction in $\mathsf{PA}$ of length $5$, the $\prec$-order would look like $$0,1,2,3,4, ... ,8,7,6,5$$ and have ordertype $5+\omega^*$ (which is not a well-order, to put it mildly). This is a primitive recursive process, though, and so we have a p.r. "copy" of $\omega$ which $\mathsf{PA}$ can't appropriately analyze.

Note that this trick works with any ("reasonable") theory in place of $\mathsf{PA}$. In particular, your proposal would lead to every proof-theoretic ordinal being just $\omega$.

$\endgroup$
0

You must log in to answer this question.

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