I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exist.


For instance I'm considering *Peano Axioms* ($\mathbf{PA}$), of proof theoretic ordinal $\epsilon\_0$, *Primitive Recursive Arithmetic* ($\mathbf{PRA}$) of proof theoretic ordinal $\omega^\omega$ and *Elementary Recursive Arithmetic* ($\mathbf{ERA}$), which is a fragment of $\mathbf{PRA}$.


I was wondering if $\mathbf{PRA}+TI\{\alpha\in\epsilon\_0\}$ (where $TI$ stands for transfinite induction) was equivalent in some sense to $\mathbf{PA}+TI\{\alpha\in\epsilon\_0\}$ or/and to $\mathbf{ERA}+TI\{\alpha\in\epsilon\_0\}$ ?


And more generally, if it was true that for any set $A$ of (countable) ordinals such that $\epsilon\_0 \subset A$, $\mathbf{ERA}+TI\{\alpha\in A\} = \mathbf{PRA}+TI\{\alpha\in A\} = \mathbf{PA}+TI\{\alpha\in A\}$ ?


Any enlightenment would be most welcome :)
Thanks in advance.



ERA, PRA, PA, transfinite induction and equivalences
This entirely depends on what exactly you mean by $TI$, as there are several options (I actually do not understand what the $\{\alpha\in\epsilon\_0\}$ part of the notation is supposed to mean either, but I will assume it just means transfinite induction up to $\epsilon\_0$):


1. $TI\{\alpha\in\epsilon\_0\}$ is the schema
$$\forall x\,(\forall y\prec x\,\phi(y)\to\phi(x))\to\forall x\,\phi(x),$$
where $\phi$ is an arbitrary formula, and $\prec$ the standard ordering of type $\epsilon\_0$. It is easy to see that transfinite induction implies ordinary induction over a weak base theory (say, $I\Delta\_0$), hence in this case, $I\Delta\_0+TI\{\alpha\in\epsilon\_0\}=\mathrm{PA}+TI\{\alpha\in\epsilon\_0\}$ (and the same holds for any base theory in between).
2. $TI\{\alpha\in\epsilon\_0\}$ is the same schema restricted to formulas of bounded complexity $\Gamma$. Typically used choices for $\Gamma$ include $\Pi^0\_2$, $\Pi^0\_1$, or open formulas in the language of PRA or EA (also called ERA or EFA). In all these cases, $\mathrm{PRA}+TI\{\alpha\in\epsilon\_0\}$ is strictly weaker than $\mathrm{PA}+TI\{\alpha\in\epsilon\_0\}$, since the former theory can be axiomatized by formulas of bounded complexity, and no consistent set of formulas of bounded complexity can imply full ordinary induction (which is equivalent to the full uniform reflection schema). In the case where $\Gamma$ are open EA-formulas, $\mathrm{EA}+TI\{\alpha\in\epsilon\_0\}$ is likewise strictly weaker than $\mathrm{PRA}+TI\{\alpha\in\epsilon\_0\}$. On the other hand, if $\Gamma\supseteq\Pi^0\_1$, then $TI\{\alpha\in\epsilon\_0\}$ implies $I\Sigma\_1\supseteq\mathrm{PRA}$ over a weak base theory.
3. $TI\{\alpha\in\epsilon\_0\}$ is the second-order induction axiom
$$\forall X\,\forall x\,(\forall y\prec x\,y\in X\to x\in X)\to\forall x\,x\in X.$$
Then one needs to include some comprehension schema in the base theory to make any sense, and its strength determines the strength of the $TI\{\alpha\in\epsilon\_0\}$. In particular, if we take at least $\Sigma^0\_1$-comprehension, we are in the same situation as in 1. If we take recursive comprehension, it is the same as 2 with $\Gamma=\Delta^0\_1$.


