En Conferencia de Graham Priest en el seminario de teoría de conjuntos de la CUNY Ayer se planteó una cuestión relativa a la posibilidad (o imposibilidad) de una forma más fuerte de lo habitual del lema aritmético del punto fijo utilizado a menudo para demostrar el teorema de incompletitud de Gödel.
El lema del punto fijo, tratado en MO anteriores preguntas se describe comúnmente como la afirmación de que para cualquier fórmula $\varphi(x)$ en el lenguaje de la aritmética, con una variable libre $x$ hay una frase $\psi$ tal que $PA\vdash\psi\leftrightarrow\varphi({\ulcorner}\psi{\urcorner})$ donde ${\ulcorner}\psi{\urcorner}$ denota el código de Gödel de $\psi$ . Versiones más fuertes del lema del punto fijo debilitan la PA a la teoría de la Q de Robinson o hacen la conclusión para redes más complejas de puntos fijos, y estos reforzamientos son bien conocidos. El lema del punto fijo conduce fácilmente al primer teorema de incompletitud, ya que con él se puede producir una sentencia $\psi$ afirmando su propia indemostrabilidad, y tal afirmación no puede ser demostrable (o de lo contrario demostraríamos algo falso) y por lo tanto es a la vez verdadera e indemostrable.
La forma más fuerte de lo habitual del lema de punto fijo deseado en el contexto de uno de los argumentos del orador era encontrar una frase $\psi$ que no sólo era demostrablemente equivalente a $\varphi({\ulcorner}\psi{\urcorner})$ pero era sintácticamente idéntica a esta afirmación. Es decir, lo que se necesitaba era lo que podríamos llamar un fuerte punto fijo, una frase $\psi$ sintácticamente de la forma $\varphi({\ulcorner}\psi{\urcorner})$ .
Esto parece imposible para cualquiera de los métodos estándar de codificación de Gödel, ya que para cada uno de ellos el código ${\ulcorner}\psi{\urcorner}$ como número, es mucho mayor que la longitud de $\psi$ como fórmula. Por ejemplo, el código de una secuencia de longitud $k$ suele ser mucho mayor que $k$ . Para dicha codificación, si entendemos $\varphi(n)$ ser $\varphi(1+\cdots+1)$ donde el término sustituido es $n$ muchos $1$ s añadido, nunca podría ser que $\psi$ es literalmente lo mismo que $\varphi({\ulcorner}\psi{\urcorner})$ ya que esta última afirmación tiene una longitud estrictamente mayor que ${\ulcorner}\psi{\urcorner}$ y ésta es mayor que la longitud de $\psi$ . Carl Mummert hizo una observación similar en la última parte de su respuesta a la pregunta del modus operandi .
Mi pregunta es: ¿Existe algún método de codificación de Gödel que apoye el lema del punto fijo fuerte?
Y si no, ¿cómo se podría demostrar tal cosa?
Graham sugirió que en el trabajo original de Gödel, la versión de la sentencia de Gödel producida tenía la propiedad de punto fijo fuerte, de ser literalmente la misma que la afirmación de que esta sentencia no era demostrable.
Se me ocurrió que si uno hace el movimiento más allá de lo que ahora se considera el lenguaje habitual de la aritmética $\{+,\cdot,0,1,\lt\}$ por ejemplo, añadiendo los símbolos de función para funciones recursivas primitivas, entonces se puede conseguir algo muy parecido a un punto fijo fuerte. (¿Y quizás esto se acerque a lo que hizo Gödel?)
Teorema. Para cualquier fórmula $\varphi(x)$ con una variable libre, existe un término cerrado $t$ en el lenguaje de la aritmética aumentada por funciones recursivas primitivas, cuyo valor es precisamente ${\ulcorner}\varphi(t){\urcorner}$ . Así, $\varphi(t)$ es un punto fijo fuerte, en el sentido de que afirma que $\varphi$ tiene un término cuyo valor es su propio código de Gödel.
Pruebas. Sea $\text{Sub}(x,y)$ sea la función recursiva primitiva tal que $\text{Sub}({\ulcorner}\alpha(x){\urcorner},k)={\ulcorner}\alpha(k){\urcorner}$ sustituyendo $k$ como término $1+\cdots+1$ en cada aparición libre de $x$ en $\alpha(x)$ . Sea $n={\ulcorner}\varphi(\text{Sub}(x,x)){\urcorner}$ y que $t=\text{Sub}(n,n)$ como término sintáctico, utilizando $1+\cdots+1$ para representar $n$ . El valor real del término $t$ puede obtenerse evaluando $\text{Sub}(n,n)$ que, a la luz de la definición de $n$ es precisamente ${\ulcorner}\varphi(\text{Sub}(n,n)){\urcorner}$ y esto es lo mismo que ${\ulcorner}\varphi(t){\urcorner}$ según se desee. QED
Este lema proporciona esencialmente puntos fijos fuertes en el lenguaje expandido; pero una diferencia es que no tenemos $\psi=\varphi({\ulcorner}\psi{\urcorner})$ donde el número se sustituye por un término de la forma $1+\cdots+1$ de la longitud correcta, sino que tenemos $\psi=\varphi(t)$ donde $t$ es un término cuyo valor real es ${\ulcorner}\psi{\urcorner}$ .
¿Se puede demostrar un análogo de este teorema utilizando términos del lenguaje aritmético ordinario? $\{+,\cdot,0,1,\lt\}$ ?
