It is well-known that $\mathbf{PRA}$ plus $\epsilon\_0$-induction on bounded formulas cannot prove all $\mathbf{PA}$ theorems ([essentially because $I\Sigma\_1$ plus $\epsilon\_0$-induction on bounded formulas is finitely axiomatizable while the latter isn't](https://math.stackexchange.com/questions/3130538/how-do-we-know-pa-is-incomparable-with-pra-epsilon-0)). Are there any concrete examples known (preferable "natural")?


(This is an exact copy of [my question on MSE](https://math.stackexchange.com/questions/3769889/concrete-examples-of-statements-not-provable-in-pra-epsilon-0-induction-tha), but I expect I won't get any answer there, so I hope I'm allowed to cross-post it here)



Concrete examples of statements not provable in PRA + $\epsilon_0$-induction that are provable in PA?
One example is $I\Sigma\_2$ (or rather, the conjunction of its finite axiomatization).


Notice that the theory $I\Sigma\_1+\epsilon\_0$-*induction for bounded formulas* is axiomatized by $\Pi\_3$ sentences: in particular, the $\epsilon\_0$-induction schema can be written in prenex form as
$$\forall u\,\forall x\,\exists y\,\forall z\,\bigl[\bigl(\neg\theta(u,y)\land(z\prec y\to\theta(u,z))\bigr)\lor\theta(u,x)\bigr],$$
where $\theta\in\Delta\_0$ and $\prec$ is the order representing $\epsilon\_0$. By a theorem of Leivant [1], $I\Sigma\_2$ is not provable from any set of $\Pi\_3$ (or even $\Sigma\_4$) sentences consistent with $Q$. More generally, for $n\ge1$, $I\Sigma\_n$ is not provable from any set of $\Sigma\_{n+2}$ sentences consistent with $Q$.


The reason is that $I\Sigma\_n$ proves the uniform $\Sigma\_{n+1}$-reflection schema for $Q$:
$$\mathrm\forall x\,\bigl(\mathrm{Pr}\_Q(\ulcorner\phi(\dot x)\urcorner)\to\phi(x)\bigr),\qquad\phi\in\Sigma\_{n+1},$$
where $\mathrm{Pr}\_Q$ denotes the formalized provability predicate for $Q$. This schema is equivalent to the single sentence
$$\def\rfn{\mathrm{RFN}}\rfn\_Q(\Sigma\_{n+1})=\forall x\,\bigl(\mathrm{Pr}\_Q(x)\to\mathrm{Tr}\_{n+1}(x)\bigr),$$
where $\mathrm{Tr}\_{n+1}$ is the truth definition for $\Sigma\_{n+1}$-formulas (defined so that it is vacuously true for non-$\Sigma\_{n+1}$-formulas). Moreover, it is easy to see that
$$\rfn\_Q(\Sigma\_{n+1})\equiv\rfn\_Q(\Pi\_{n+2}).$$
Now, if we assume for contradiction that $\rfn\_Q(\Pi\_{n+2})$ is provable from a consistent extension of $Q$ by $\Sigma\_{n+2}$ sentences, there is a single $\Sigma\_{n+2}$ sentence $\phi$ consistent with $Q$ such that
$$Q+\phi\vdash\rfn\_Q(\Pi\_{n+2})\vdash\mathrm{Pr}\_Q(\ulcorner\neg\phi\urcorner)\to\neg\phi,$$
that is,
$$Q+\phi\vdash\mathrm{Con}\_{Q+\phi},$$
contradicting the second incompleteness theorem.


**Reference:**


[1] Daniel Leivant: *The optimality of induction as an axiomatization of arithmetic*, Journal of Symbolic Logic 48 (1983), no. 1, pp. 182–184, doi: [10.2307/2273332](https://doi.org/10.2307/2273332).


