# What is induction up to epsilon_0?

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?

• Does what you're looking for start on page 456 of this paper? projecteuclid.org/… – Jason Dyer Nov 11 '09 at 16:40
• Maybe, but if it is there I don't understand it. This seems to be explaining how to label trees by ordinals below $\epsilon_0$. I'm trying to figure out how to pack epsilon_0 into positive integers, which are the objects PA is allowed to talk about. – David E Speyer Nov 11 '09 at 16:52
• This reference explains how to encode $\epsilon_0$ into $\omega$. You just split $\omega$ into infinitely many countable sets and embed $S_i$ into the $i$-th set (all in a recursive manner). – Ori Gurel-Gurevich Nov 11 '09 at 17:04
• Every ordinal under epsilon_0 has a unique Cantor normal form which can then be encoded as a natural. – Dan Piponi Nov 12 '09 at 2:22

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)$.

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.

• @DavidE.Speyer: Since on your blog post, $\omega^{\omega}$ is represented by the list (((()))), is there some reason why $\epsilon_0$ cannot have a 'finitary' representation of a similar sort? – Thomas Benjamin Jul 24 at 20:55

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.

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