# 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 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.

-

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.

-