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 $\varepsilon\_0$, which has been expressed to me roughly as the claim that $\varepsilon\_0$ is well-ordered. I understand what ordinals are, and what $\varepsilon\_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 $\varepsilon\_0$ is well-ordered as a first order sentence in arithmetic. Would someone mind spelling this out for me?



What is induction up to $\varepsilon_0$?
Here's a more detailed answer:


The [above-mentioned](https://mathoverflow.net/questions/5065/what-is-induction-up-to-varepsilon-0#comment5716_5065) link (recreated below [1]) 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)$.


[1] P. Tosi, *Normal derivability and first-order arithmetic*,
Notre Dame J. Formal Logic 21(2): 449-466 (April 1980) doi:[10.1305/ndjfl/1093883058](https://doi.org/10.1305/ndjfl/1093883058).


