most recent 30 from http://mathoverflow.net 2013-05-22T16:48:04Z http://mathoverflow.net/feeds/question/5065 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5065/what-is-induction-up-to-epsilon-0 David Speyer 2009-11-11T16:02:09Z 2009-12-07T16:25:29Z

<p>This is a question asked out of curiosity, and because I can't understand the wikipedia page.</p> <p>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. </p> <p>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?</p>

http://mathoverflow.net/questions/5065/what-is-induction-up-to-epsilon-0/5073#5073 B S 2009-11-11T17:14:31Z 2009-11-11T17:14:31Z

<p>Maybe it's spelled out in a more convenient way in Wikipedia <a href="http://en.wikipedia.org/wiki/Goodstein%27s%5Ftheorem" rel="nofollow">here</a> (about Goodstein sequences), or in the page about Gentzen's consistency proof of Peano's arithmetic.</p> <p>Hope this helps.</p>

http://mathoverflow.net/questions/5065/what-is-induction-up-to-epsilon-0/5076#5076 Ori Gurel-Gurevich 2009-11-11T17:18:53Z 2009-11-11T17:18:53Z

<p>Here's a more detailed answer:</p> <p>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)$.</p>

http://mathoverflow.net/questions/5065/what-is-induction-up-to-epsilon-0/6105#6105 Jason Dyer 2009-11-19T14:55:24Z 2009-11-19T14:55:24Z

<p>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 <a href="http://en.wikipedia.org/wiki/Ordinal%5Farithmetic#Cantor%5Fnormal%5Fform" rel="nofollow">here</a>.</p>

http://mathoverflow.net/questions/5065/what-is-induction-up-to-epsilon-0/8109#8109 David Speyer 2009-12-07T16:25:29Z 2009-12-07T16:25:29Z

<p>I now realize that a full answer to this question would be far longer than is appropriate for MathOverflow. So I wrote a <a href="http://sbseminar.wordpress.com/2009/12/07/the-technical-part-of-godels-proof/" rel="nofollow">blog post</a>. Thanks to everyone who helped me understand what is going on here.</p>