3
$\begingroup$

Gentzen's theorem states that Peano arithmetic is consistent up to $\varepsilon_0$. In finite case, $1+a \neq a$ holds where a is a finite natural number. As transfinite induction up to $\varepsilon_0$ is there, it seems that $1+\omega \neq \omega$ must hold. However, we all know that $1+\omega = \omega$.

What am I thinking wrongly?

Thanks.

  • 1
    Previous comment rephrased. Gentzen's consistency **proof** uses induction up to $\varepsilon_0$. This has nothing to do with the order structure of the natural numbers.2012-05-03

1 Answers 1

2

One thing is that $PA$ doesn't have the ability to even talk about $\omega$. You might try that $PA$ proves $\exists x (x> 0 \land x >S 0 \land \dots)$, but this is not a finite formula. In fact the natural numbers, since they are a model of $PA$, and only contain finite numbers, will frustrate any attempt to show that $PA$ can infinite ordinals like $\omega$. So the problem with $PA$ proving anything about $\omega$ is that $PA$ can't even talk about $\omega$!

As Andre mentions above, the assumption that there is a "well-ordering up to ordinal $\gamma$" takes place outside of $PA$, and not in $PA$. (Formally Gentzen's proof takes place in a theory, like $ZFC$ which can talk about infinite ordinals.)

EDIT: Aside from what can be proved in any formal theory, I think you are confusing what transfinite recursion says. It doesn't say that if you've proved some property up to an ordinal $\alpha$, than you have it for $\alpha$. What it does say is that if you've proved the implication from all smaller ordinals than $\alpha$ having the property to $\alpha$ having that property, then the property holds for all ordinals. Think about this: you can prove that for any $n$, $n$ is finite, but it doesn't follow that $\omega$ is finite. For more info see here: http://en.wikipedia.org/wiki/Transfinite_induction