Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?


share|improve this question
The questioner never claimed what $\omega + 1$ was, the issue is what $PA$ seemingly proves about $1 + \omega$. –  student 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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.