¿Caracterización prueba teórica de las funciones primitivas recursivas?

Question

El total de las funciones recursivas son exactamente las mismas que el número de la teoría de funciones que pueden ser representadas por una $\Sigma_1$ fórmula de primer orden de la aritmética.

Hay una similar caracterización de la primitiva recursiva funciones? Estoy buscando algo como por ejemplo

silvestre (conjetura) de Las primitivas funciones recursivas son aquellas que pueden ser representados por un $\Sigma^0_1$ fórmula que puede ser demostrado su total y de un solo valor por $\Delta^0_0$ inducción.

Answer 1

El demostrablemente total de funciones en $\mathrm I\Sigma_1$ son exactamente las funciones recursivas primitivas. Este es un teorema de Parsons a partir de la década de 1970; véase, por ejemplo, el Teorema 3 en la página 34 del libro de Prueba de la Teoría editado por Aczel, Simmons y Wainer para el estándar de la prueba.

La teoría de la $\mathrm I\Delta_0$ habitual en el lenguaje de la aritmética $\{0,1,{+},{\times},{<}\}$ no es suficiente para demostrar que el conjunto de todas las primitivas de funciones recursivas. Por ejemplo, se ha demostrado por Parikh en su papel de "la Existencia y la viabilidad de la aritmética" que la totalidad de la exponenciación no es comprobable en $\mathrm I\Delta_0$.