What is induction up to epsilon_0?

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.

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

The answer to your question can be found in Maria Hameen-Anttila's paper, "Nominalistic Ordinals, Recursion on Higher Types, and Finitism", Bulletin of Symbolic Logic,25(1), 101-124 (2019). Since the version I have immediate free access to is the Accepted author manuscript version found on the University of Helsinki research portal (www.researchportal.helsinki.fi/publications/nominalistic-ordinals-recursion-on-higher-types-and-finitism), I will be using that version's pagination rather than the published version's pagination when referring to the pages on which the answer to your question can be found.

To begin with, the answer to your question can be found on pp. 4-14 (these pages also provide the historical context regarding the answer--the actual answer can be found on pp. 12-14 in the Accepted author manuscript on the Web). I hope this helps.

As regards the statement, "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", you might consider Noah Schweber's nice answer to my mathoverflow question, "What does 'can almost be proven in $PA$' mean regarding Theorem 2 of Timothy Chow's expository article, 'The Consistency of Arithmetic' ":

We have an arithmetic statement of the form

$(*)$ $\forall$$x$$\varphi$($x$)

which while not provable in $PA$ has the property that for each natural number $n$ the instance

$(*)_{n}$ $\varphi$($\mathfrak n$)

is provable in $PA$ (where "$\mathfrak n$" is the numeral corresponding to the natural number $n$)...

...Note that we also have the same phenomenon with respect to consistency: for each natural number $n$, $PA$ proves "there is no $PA$-proof of '0=1' of length $\lt$ $n$." So $PA$ almost proves $Con$($PA$).

It should be noted that this same phenomenon holds for defining $\epsilon_0$ as well. As is known, $\epsilon_0$ can be defined as follows:

{$\omega$, $\omega^{\omega}$, $\omega^{\omega^{\omega}}$,...} = $\epsilon_0$ for a countably infinite number of iterations of $\omega^{\alpha}$.

Since it is known that $PA$ proves that each of the elements of $\epsilon_0$ is well-ordered, but doesn't prove that the set of ordinals that is itself $\epsilon_0$ is well-ordered, one can see that the aforementioned set is well-ordered since each of its members is well-ordered. Here we have a early concrete example of Godel's First Incompleteness Theorem before Paris-Harrington or Goodstein sequences. I hope this clarifies things at least somewhat.