¿Es esta teoría del conteo recursivo equiinterpretable con PA?

De un vistazo, la respuesta es sí .

Como límite superior de la fuerza, el argumento que da en su pregunta anterior funciona una vez que incluimos$\#$.

El límite inferior se proporciona entonces de la siguiente manera: si$M$es un modelo de PA, entonces$M$equipado con sus conjuntos internamente finitos "es" un modelo de su teoría (tenemos que masajear un poco el lenguaje, por supuesto). Aquí un conjunto internamente finito es un conjunto de la forma$\{x: n>x\wedge M\models\varphi(x)\}$para alguna fórmula con parámetros$\varphi$y algo$n\in M$.

Hay una sutileza con este límite inferior: para probar la comprensión, necesitamos mostrar que algo definible al cuantificar sobre conjuntos internamente finitos es definible en el sentido original. Esto se deduce de lo siguiente: para cada fórmula$\varphi(x; y_1,...,y_k)$, PA prueba lo siguiente:

Para todos$a_1,...,a_k, n$, hay un$c$tal que para todos$i$tenemos

$$p_i\vert c\iff i<n\wedge \varphi(i; a_1,...,a_k).$$

Es decir, en cualquier modelo de PA, todos los conjuntos internamente finitos son, de hecho, definibles libremente por cuantificadores, y podemos cuantificar sobre fórmulas de complejidad de cuantificadores acotados .