# What is induction up to epsilon_0?

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

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