ERA, PRA, PA, inducción transfinita y equivalencias

Question

Estoy bastante seguro de que no entiendo muy bien los vínculos entre los ordinales teóricos de prueba de las teorías, los axiomas de la inducción transfinita y los objetos que una teoría puede demostrar que existen.

Por ejemplo, estoy considerando Axiomas de Peano ( $\mathbf{PA}$ ), del ordinal de la teoría de la prueba $\epsilon_0$ , Aritmética recursiva primitiva ( $\mathbf{PRA}$ ) de la teoría de la prueba ordinal $\omega^\omega$ y Aritmética recursiva elemental ( $\mathbf{ERA}$ ), que es un fragmento de $\mathbf{PRA}$ .

Me preguntaba si $\mathbf{PRA}+TI\{\alpha\in\epsilon_0\}$ (donde $TI$ significa inducción transfinita) era equivalente en cierto sentido a $\mathbf{PA}+TI\{\alpha\in\epsilon_0\}$ o/y a $\mathbf{ERA}+TI\{\alpha\in\epsilon_0\}$ ?

Y más generalmente, si fuera cierto que para cualquier conjunto $A$ de ordinales (contables) tales que $\epsilon_0 \subset A$ , $\mathbf{ERA}+TI\{\alpha\in A\} = \mathbf{PRA}+TI\{\alpha\in A\} = \mathbf{PA}+TI\{\alpha\in A\}$ ?

Cualquier aclaración será bienvenida :) Gracias de antemano.

Answer 1

Esto depende totalmente de lo que se entienda exactamente por $TI$ ya que hay varias opciones (la verdad es que no entiendo qué es el $\{\alpha\in\epsilon_0\}$ parte de la notación se supone que significa cualquiera de las dos cosas, pero voy a suponer que sólo significa la inducción transfinita hasta $\epsilon_0$ ):

1. $TI\{\alpha\in\epsilon_0\}$ es el esquema $$\forall x\,(\forall y\prec x\,\phi(y)\to\phi(x))\to\forall x\,\phi(x),$$ donde $\phi$ es una fórmula arbitraria, y $\prec$ la ordenación estándar del tipo $\epsilon_0$ . Es fácil ver que la inducción transfinita implica la inducción ordinaria sobre una teoría de base débil (digamos, $I\Delta_0$ ), por lo que en este caso, $I\Delta_0+TI\{\alpha\in\epsilon_0\}=\mathrm{PA}+TI\{\alpha\in\epsilon_0\}$ (y lo mismo vale para cualquier teoría de base intermedia).

2. $TI\{\alpha\in\epsilon_0\}$ es el mismo esquema restringido a fórmulas de complejidad acotada $\Gamma$ . Opciones típicas utilizadas para $\Gamma$ incluye $\Pi^0_2$ , $\Pi^0_1$ o fórmulas abiertas en el lenguaje de la ARP o la EA (también llamadas ERA o EFA). En todos estos casos, $\mathrm{PRA}+TI\{\alpha\in\epsilon_0\}$ es estrictamente más débil que $\mathrm{PA}+TI\{\alpha\in\epsilon_0\}$ ya que la primera teoría puede ser axiomatizada por fórmulas de complejidad acotada, y ningún conjunto consistente de fórmulas de complejidad acotada puede implicar la inducción ordinaria completa (que es equivalente al esquema de reflexión uniforme completo). En el caso de que $\Gamma$ son fórmulas abiertas de EA, $\mathrm{EA}+TI\{\alpha\in\epsilon_0\}$ también es estrictamente más débil que $\mathrm{PRA}+TI\{\alpha\in\epsilon_0\}$ . Por otro lado, si $\Gamma\supseteq\Pi^0_1$ entonces $TI\{\alpha\in\epsilon_0\}$ implica $I\Sigma_1\supseteq\mathrm{PRA}$ sobre una teoría de base débil.

3. $TI\{\alpha\in\epsilon_0\}$ es el axioma de inducción de segundo orden $$\forall X\,\forall x\,(\forall y\prec x\,y\in X\to x\in X)\to\forall x\,x\in X.$$ Entonces hay que incluir algún esquema de comprensión en la teoría base para que tenga sentido, y su fuerza determina la fuerza del $TI\{\alpha\in\epsilon_0\}$ . En particular, si tomamos al menos $\Sigma^0_1$ -comprensión, estamos en la misma situación que en 1. Si tomamos la comprensión recursiva, es lo mismo que 2 con $\Gamma=\Delta^0_1$ .