Transfinite Induction in Peano Arithmetic I have heard that Peano Arithmetic (PA) cannot perform transfinite induction up to $\varepsilon_0$. This seems to imply that it can induct up to smaller ordinals, like $\omega$ or $\omega^\omega$ or $\omega^{\omega^\omega}$. How does that work? I thought PA couldn't even talk about ordinals, much less induct on them.
I suppose that PA can probably induct on $\{(a,b)\ |\ a,b\in\mathbb N\}$ with lexicographical ordering, which is equivalent to inducting up to $\omega^2$, but I'm not sure.
 A: You're on the right track.  We can "talk about" a recursive transfinite ordinal $\alpha$ by defining a recursive relation $R$ on $\mathbb{N}$ such that $\{\mathbb{N},R\}$ is a well-ordered set with order type $\alpha$.  We can then define $\text{TI}(R)$ as the schema $\forall \alpha (\forall \beta (\beta \ R \ \alpha \implies \varphi(\beta)) \implies \varphi(\alpha))\implies \forall \alpha \ \varphi(\alpha) $, and let $\text{TI}(\alpha)$ mean $\text{TI}(R)$ for some recursive relation $R$ such that $\{\mathbb{N},R\}$ is a well-ordered set with order type $\alpha$.
For PA, we have that for any $\alpha < \varepsilon_0$ there is a recursive relation $R$ of order type $\alpha$ such that $\text{PA} \vdash \text{TI}(R)$, but for no recursive relation $R$ or order type $\varepsilon_0$ do we have $\text{PA} \vdash \text{TI}(R)$.  
Note that the situation is quite different if we require $\text{PA} \vdash \text{TI}(R)$ for all recursive relations of order type $\alpha$; there exists a relation $R$ of order type $\omega$ such that PA does not prove $\text{TI}(R)$.  In fact, G. Kreisel constructed, for any true $\Pi^0_1$ sentence $\pi$, a primitive recursive relation $R$ of order type $\omega$ such that $\text{PRA}+\text{TI}(R,\Pi^0_0) \vdash \pi$. As I understand it, the idea is to "encode" the sentence $\pi$ into the construction $R$, but I do not know the details; for more information, I suggest reading Kreisel's paper "A Survey of Proof Theory". Of course, the previous result means there is a primitive recursive relation $R$ of order type $\omega$ such that $\text{PRA}+\text{TI}(R,\Pi^0_0) \vdash \text{Con(PA)}$, so by Godel's Second Incompleteness Theorem, PA cannot prove $\text{TI}(R,\Pi^0_0)$.
