¿Esta teoría del recuento recursivo es equi-interpretable con la AP?

Question

A la teoría presentada en este enlace añadir un símbolo de función de dos posiciones $\#$ que denota una función de conteo sobre números en conjuntos, a la lista de primitivas de ese lenguaje, y añadir el axioma:

$\#^K (x) = n \leftrightarrow [x=min(K) \land n=1] \lor [x \in K \land min(K) < x \land n= S[\#^K(P^K(x))]$

Definir $P^K(x) = y \iff x \in K \land y \in K \land y < x \land \not \exists z \in K (y < z < x)] $

Define Sucesor como: $x=S(y) \iff y < x \land \not \exists z (y < z < x)$

Definir: $ x = min(K) \iff x \in K \land \forall y \in K (x \leq y)$

¿La teoría resultante sería equi-interpretable con la "PA" aritmética de Peano? Y, por tanto, amplía conservadoramente la PA.

Answer 1

A simple vista, la respuesta es sí .

Como límite superior de la fuerza, el argumento que das en tu 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 algunos $n\in M$ .

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

Para todos $a_1,...,a_k, n$ Hay un $c$ tal que para todo $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 sin cuantificadores, y podemos cuantificar sobre fórmulas de limitado complejidad del cuantificador.