Que no es la función recursiva primitiva ' t $\Delta_0$

Question

¿Qué es el ejemplo más simple/más lindo (o ejemplo con el más respetuoso con el estudiante la prueba de ello es un ejemplo) de una función primitiva recursiva que no es representable por un $\Delta_0$ wff?

Answer 1

Si $\phi(x,y)$ $\Delta^0_0$ fórmula que define una función de $y = f(x)$, entonces para cada a $x$ hay un $y$ tal que $\phi(x,y)$ mantiene. Por lo tanto, considerar la primitiva de la función recursiva que, en la entrada de $e$, hace lo siguiente:

• Interpretar $e$ como un código para un $\Delta^0_0$ fórmula $\phi_e(x,y)$ en la forma canónica.

• Compruebe si $\phi_e(e,0)$ mantiene. Si sí, regresar $1$. En caso contrario, devuelve $0$.

Por el argumento habitual, esta función no puede ser definida por cualquiera de $\Delta^0_0$ fórmula. Sin embargo, en virtud de la costumbre de codificación de fórmulas, es una primitiva de la función recursiva, porque la verdad predicado por $\Delta^0_0$ frases es primitiva recursiva. La prueba de este último hecho es sólo una formalización del hecho de que la primitiva recursiva de los predicados incluyen las fórmulas atómicas y son cerrados bajo todos los conectivos lógicos y bajo delimitada universal y cuantificación existencial.

En particular, este ejemplo muestra que no es necesario que una primitiva de la función recursiva para crecer rápidamente en orden para que no ser$\Delta^0_0$.