# transfinite induction confusion

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.

-
The questioner never claimed what $\omega + 1$ was, the issue is what $PA$ seemingly proves about $1 + \omega$. – lesnikow May 3 '12 at 4:33
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. – André Nicolas May 3 '12 at 4:48

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