¿Demostración de la proposición/teorema V del artículo de Gödel de 1931?

Question

La proposición V del famoso artículo de Gödel de 1931 es la siguiente:

Para cada relación recursiva $ R(x_{1},...,x_{n})$ hay un "predicado" n-ario $r$ (con "variables libres" $u_1,...,u_n$ ) tal que, para todas las n-parejas de números $(x_1,...,x_n)$ tenemos:

$$R(x_1,...,x_n)\Longrightarrow Bew[Sb(r~_{Z(x_1)}^{u_1}\cdot\cdot\cdot~_{Z(x_n)}^{u_n})] $$

$$\overline{R}(x_1,...x_n)\Longrightarrow Bew[Neg~Sb(r~_{Z(x_1)}^{u_1}\cdot\cdot\cdot~_{Z(x_n)}^{u_n})]$$

Gödel "indica el esquema de la prueba" y básicamente dice, en su paso inductivo, que la construcción de $r$ se puede imitar formalmente a partir de la construcción de la función recursiva que define la relación $R$ .

He intentado demostrar la proposición anterior con más rigor, pero sin éxito. Sin embargo, he consultado "On Undecidable Propositions of Formal Mathematical Systems", las notas de clase tomadas por Kleene y Rosser de la conferencia de Gödel de 1934, que han sido mucho más esclarecedoras; pero sigue omitiendo los detalles en el paso inductivo a partir de la definición recursiva, afirmando que "la prueba... es demasiado larga para darla aquí".

Así que, ¿alguien puede darme una pista útil para la demostración de la proposición anterior, o incluso mejor, una fuente donde pueda encontrar dicha demostración? Gracias.

Answer 1

Recuerda que lo que Gödel llamaba "recursivo" es lo que ahora llamamos primitivo recursivo el término "recursivo" se utiliza ahora para significar computable en su lugar. También el "predicado" $r$ se llama ahora fórmula.

La idea general que nos ocupa se llama "representabilidad de las funciones". Lo que estamos probando es que cada función recursiva primitiva es representable de una manera particular en nuestra teoría fija y suficientemente fuerte de la aritmética. Este tipo de cosas se tratan con gran detalle en los capítulos 12 y 13 del libro de Peter Smith Introducción a los teoremas de Gödel que en este momento es probablemente la mejor referencia rigurosa impresa a nivel de licenciatura.

Un método de demostración es por inducción sobre la definición de la función recursiva primitiva $R$ . He aquí un esquema de cómo definir la fórmula $r$ :

• Para la función de sucesión $R(x) = x+1$ dejar $r(x,y)$ sea $y = x+1$

• Para la función de proyección $R(x_1,\ldots, x_n) = x_i$ dejar $r(x_1, \ldots, x_n, y)$ sea $y = x_i$

• Para la función cero $R(x) = 0$ dejar $r(x,y)$ sea $y = 0$

• Si $R$ es una composición $f(g_1(x_1, \ldots, x_n), \ldots, g_k(x_1, \ldots, x_n))$ , dejemos que $r_f$ y $r_{g_i}$ , $i \leq k$ se obtiene por inducción. Entonces dejemos que $r(x_1,\ldots,x_n, y)$ sea $$(\exists y_1, \ldots, y_k)[ r_f(y_1, \ldots, y_k, y) \land r_{g_1}(x_1,\ldots,x_n,y_1) \land \cdots \land r_{g_k}(x_1,\ldots,x_n,y_k)]$$

• Si $R$ se define por recursión primitiva como $$R(0, x_1, \ldots, x_n) = f(x_1, \ldots, x_n)$$ $$R(k+1, x_1, \ldots , x_n) = g(k, x_1, \ldots, x_n, R(k, x_1, \ldots, x_n))$$ entonces deja que $r_f$ y $r_g$ se obtenga por inducción y que $$ r(z, x_1, \ldots, x_n, y) = (\exists \sigma)[|\sigma| = z+1 \land r_f(x_1,\ldots,x_n,\sigma(0)) \land (\forall i < z)[r_g(i, x_1, \ldots, x_n, \sigma(i+1)) \land y = \sigma(z)]$$ La cuantificación sobre una secuencia finita $\sigma$ puede convertirse en una cuantificación sobre números naturales utilizando la técnica de La función β de Gödel .

Entonces se puede demostrar por inducción que para cada primitiva recursiva $R$ para cada $x_1,\ldots, x_n$ hay un único $y$ tal que $r(\overline{x_1}, \ldots, \overline{x_n},\overline{y})$ es demostrable.

Answer 2

No estoy completamente familiarizado con la notación de Gödel, pero creo que esto es equivalente al teorema 60 del capítulo 2 de La Lógica de la Probabilidad de George Boolos, que tiene pruebas bastante detalladas de este tipo de cosas (todo en el capítulo 2).