Question

This is a question asked out of curiosity, and because I can't understand the wikipedia page.

I have often been told that PA cannot prove the validity of induction up to $\epsilon_0$, which has been expressed to me roughly as the claim that $\epsilon_0$ is well-ordered. I understand what ordinals are, and what $\epsilon_0$ is. I also understand first order logic and axiom schemes, so I understand how the induction axiom scheme formalizes the notion that $\omega$ is well-ordered.

What I don't understand is how one could formulate the statement that $\epsilon_0$ is well-ordered as a first order sentence in arithmetic. Would someone mind spelling this out for me?

Answer 1

Here's a more detailed answer:

The above-mentioned link constructs a recursive relation $E$ on $\omega$, such that $(\omega, E)$ is isomorphic to $(\epsilon_0, \in )$. Then, induction up to $\epsilon_0$ is interpreted as $E$-induction, that is, for every predicate $\phi$, if $(\forall x E y \phi(x))\rightarrow \phi(y)$ then $\forall y \phi(y)$.

Answer 2

Maybe it's spelled out in a more convenient way in Wikipedia here (about Goodstein sequences), or in the page about Gentzen's consistency proof of Peano's arithmetic.

Hope this helps.

Answer 3

David, if you are still confused, note that any ordinal under $\eplison_0$ can be converted into what is essentially a base-ω positional numeral system. There are more details here.

Answer 4

I now realize that a full answer to this question would be far longer than is appropriate for MathOverflow. So I wrote a blog post. Thanks to everyone who helped me understand what is going on here.