Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.