La prueba de los teoremas de incompletitud contiene varias ideas brillantes de Gödel:
- La primera es la posibilidad de formalizar la lógica a través de fórmulas aritméticas (fórmulas que hablan sólo de números naturales) a través de los números de Gödel.
Esta idea no aparece en la versión que estamos probando aquí porque estamos formalizando la lógica en Z, lo cual no tiene ningún mérito, ya que en Z se puede formalizar cualquier cosa razonable (en ZFC, que hubiéramos podido usar si nos hubiera hecho falta) cualquier cosa. En particular, la numeración de Gödel la hemos reducido a su mínima expresión, al limitarla a asignar un número a cada signo del lenguaje, pero no a las fórmulas ni a las demostraciones.
- La segunda es la forma de justificar que a partir de los axiomas de Peano es posible demostrar todas las cosas que es necesario demostrar para probar los teoremas de incompletitud. Para ello Gödel se apoyó en la teoría de la recursión.
En nuestro contexto esto también desaparece, porque para demostrar que en Z se puede demostrar todo lo necesario no hace falta ninguna artillería. En particular, no hemos necesitado mencionar para nada la teoría de la recursión.
- La tercera es la posibilidad de aprovechar lo anterior para definir fórmulas autorreferentes, es decir, fórmulas que hablen de sí mismas en un sentido que precisaremos en el mensaje siguiente.
Esto requiere un resultado técnico previo al que dedicaremos este mensaje, resultado que en la prueba clásica no llama mucho la atención ya que se obtiene de forma inmediata a partir de las técnicas relacionadas con el punto anterior y que aquí no hemos necesitado. En cambio, aquí vamos a poner el foco sobre él.
- La cuarta y la quinta son los argumentos en sí que prueban los dos teoremas de incompletitud.
Para explicar el resultado que tenemos que demostrar aquí consideremos una sucesión finita metamatemática de números naturales, por ejemplo, \( \zeta = (3,5,1) \). Tenemos definida su formalización en Z, que representamos por \( \ulcorner(3, 5, 1)\urcorner \). Con precisión, esto no es nada en nuestro lenguaje formal, sino que lo que tenemos definido realmente es la fórmula
\( x=\ulcorner(3, 5, 1)\urcorner\equiv \forall u(u\in x\leftrightarrow u = (\ulcorner0\urcorner,\ulcorner3\urcorner)\lor u = (\ulcorner1\urcorner, \ulcorner5\urcorner)\lor u=(\ulcorner2\urcorner, \ulcorner1\urcorner)).
\)
Esto es una fórmula metamatemática, luego también tenemos definida su formalización \( \ulcorner x=\ulcorner(3, 5, 1)\urcorner\urcorner \), de modo que, según hemos visto en el mensaje anterior, en Z podemos demostrar que \( \ulcorner x=\ulcorner(3, 5, 1)\urcorner\urcorner\in \mathcal F \).
Lo que nos proponemos demostrar es que es posible definir en Z una aplicación \( \mathcal V\times S^1\longrightarrow \mathcal F \), que representaremos por \( (x, \zeta)\mapsto [x=\zeta] \), con la propiedad de que, para toda variable metamatemática \( x \) y toda sucesión finita metamatemática de números naturales \( \zeta \), se cumple que\( \color{blue}[\ulcorner x\urcorner=\ulcorner\zeta\urcorner] = \ulcorner x=\ulcorner\zeta\urcorner\urcorner, \)
es decir que, en el ejemplo que estábamos considerando, la fórmula \( \ulcorner x=\ulcorner(3, 5, 1)\urcorner\urcorner\in \mathcal F \) puede calcularse en Z aplicando una función (la que vamos a definir) a la variable \( \ulcorner x\urcorner \) y a la sucesión \( \ulcorner\zeta\urcorner \). En otras palabras, que en Z podemos describir el proceso que permite construir la formalización de \( x= \ulcorner\zeta\urcorner \) a partir de \( \ulcorner x\urcorner \) y de \( \ulcorner\zeta\urcorner \).
Nuestro objetivo es, pues, definir una cierta función \( \mathcal V\times S^1\longrightarrow \mathcal F \), para lo cual tendremos que definir algunas funciones previas.
Por ejemplo, empezamos considerando las funciones
\( \ulcorner=\urcorner: \mathcal V\times\mathcal V\longrightarrow \mathcal F,\qquad \ulcorner\in\urcorner:\mathcal V\times\mathcal V\longrightarrow \mathcal F
\)
dadas por
\( x\,\ulcorner=\urcorner\, y=(\ulcorner=\urcorner, x, y),\qquad x\,\ulcorner\in\urcorner\,y=(\ulcorner\in\urcorner, x, y). \)
Es importante entender esto: estamos definiendo una aplicación, exactamente igual que si definiéramos \( f:\mathbb N\times \mathbb N\longrightarrow \mathbb N \) mediante \( f(x, y) = xy^2 \). En este ejemplo, cuando a las variables (metamatemáticas) \( x, y \) les damos valores en los números naturales, la aplicación \( f \) nos da un número natural. En el ejemplo que nos interesa, cuando a la aplicación \( \ulcorner=\urcorner(x, y) \) le damos valores en \( \mathcal V \) a las dos variables (metamatemáticas) \( x,y \), obtenemos un elemento de \( \mathcal F \).
También es importante no confundir \( x\,\ulcorner=\urcorner\,y \) con \( \ulcorner x=y\urcorner \). La primera expresión es como \( xy^2 \). No es un número natural, sino que cuando damos a \( x,y \) diferentes valores naturales obtenemos distintos números naturales. Igualmente, \( x\,\ulcorner=\urcorner\,y \) no es una fórmula, sino que cuando sustituimos las variables metamatemáticas \( x,y \) por distintas variables (formalizadas) de \( \mathcal V \) (es decir, por números naturales mayores o iguales que \( 5 \)) obtenemos distintas fórmulas atómicas de \( \mathcal F \). Por el contrario, \( \ulcorner x=y\urcorner \) es una fórmula concreta de \( \mathcal F \).
La relación entre ambas es que si \( x,y \) son variables metamatemáticas, tenemos que
\( \ulcorner x\urcorner\,\ulcorner=\urcorner\,\ulcorner y\urcorner = (\ulcorner=\urcorner, \ulcorner,x\urcorner, \ulcorner y\urcorner) = \ulcorner x=y\urcorner,
\)
e igualmente \( \ulcorner x\urcorner\,\ulcorner\in\urcorner\,\ulcorner y\urcorner = \ulcorner x\in y\urcorner \).
Ahora recordamos otras funciones que ya teníamos definidas, sólo que ahora las representamos con ángulos de Quine:
\( \ulcorner\lnot\urcorner: \mathcal F\longrightarrow \mathcal F,\quad \ulcorner\rightarrow\urcorner:\mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\forall\urcorner:\mathcal V\times\mathcal F\longrightarrow \mathcal F,
\)
\( \ulcorner\lor\urcorner: \mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\land\urcorner: \mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\leftrightarrow\urcorner:\mathcal F\times\mathcal F\longrightarrow \mathcal F,\quad \ulcorner\exists\urcorner:\mathcal V\times\mathcal F\longrightarrow \mathcal F.
\)
Es inmediato que en Z se prueban las propiedades siguientes:
\( \ulcorner\lnot\urcorner\ulcorner\alpha\urcorner=\ulcorner\lnot\alpha\urcorner,\quad \ulcorner\alpha\urcorner\ulcorner\rightarrow\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\rightarrow\beta\urcorner,\quad \ulcorner\forall\urcorner\ulcorner x\urcorner\ulcorner\alpha\urcorner=\ulcorner\forall x \alpha\urcorner,
\)
\( \ulcorner\alpha\urcorner\ulcorner\lor\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\lor\beta\urcorner,\quad \ulcorner\alpha\urcorner\ulcorner\land\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\land\beta\urcorner,\quad \ulcorner\alpha\urcorner\ulcorner\leftrightarrow\urcorner\ulcorner\beta\urcorner=\ulcorner\alpha\leftrightarrow\beta\urcorner,\quad \ulcorner\exists\urcorner\ulcorner x\urcorner\ulcorner\alpha\urcorner=\ulcorner\exists x \alpha\urcorner.
\)
Por ejemplo, por definición de \( \ulcorner\lor\urcorner \):
\( \ulcorner\alpha\urcorner\ulcorner\lor\urcorner\ulcorner\beta\urcorner = (\ulcorner\lnot\urcorner\ulcorner\alpha\urcorner)\ulcorner\rightarrow\urcorner\ulcorner\beta\urcorner = \ulcorner\lnot\alpha\urcorner\ulcorner\rightarrow\urcorner\ulcorner\beta\urcorner = \ulcorner\lnot\alpha\rightarrow\beta\urcorner=\ulcorner\alpha\lor \beta\urcorner.
\)
Números naturales Como primer paso para demostrar el resultado que perseguimos probaremos el hecho análogo para números naturales. Empezamos con el caso del \( 0 \). Por definición,
\( x=\ulcorner0\urcorner\equiv \forall u\, u\notin x, \)
donde \( u \) es una variable distinta de \( x \). En general no importa cuál sea, pero en este contexto necesitamos precisarlo, y podemos convenir en que \( u \) es la menor variable distinta de \( x \) (teniendo en cuenta que estamos identificando las variables con los números naturales mayores o iguales que \( 5 \)).
Así, \( x=\ulcorner0\urcorner \) no es una única fórmula, sino una fórmula distinta para cada elección de \( x \). Esto determina una función que podemos formalizar en Z como la aplicación
\( \mathcal V\longrightarrow \mathcal F \)
dada por
\( [x=\ulcorner0\urcorner]=\ulcorner\forall\urcorner u\ulcorner\lnot\urcorner\, u\ulcorner\in\urcorner x, \)
donde \( u \) es el menor elemento de \( \mathcal V \) distinto de \( x \).
Entendamos esto: Acabamos de definir una función en Z como podríamos haber definido \( f:\mathbb N\longrightarrow \mathbb N \) dada por \( f(x)=x^u \), donde \( u \) es el menor natural distinto de \( x \). Así, por ejemplo, \( f(3)=3^4 = 81 \).
Igual que, cuando la variable \( x \) recorre los números naturales, la expresión \( f(x) \) recorre algunos números naturales, cuando la variable (metamatemática) \( x \) recorre las variables (formalizadas) de \( \mathcal V \), la expresión \( [x= \ulcorner0\urcorner] \) recorre algunos elementos de \( \mathcal F \).
En particular, no es lo mismo \( [x=\ulcorner0\urcorner] \) que \( \ulcorner x=0\urcorner \). Lo segundo es un elemento concreto de \( \mathcal F \), mientras que lo primero es una expresión que recorre distintos elementos de \( \mathcal F \) cuando la variable \( x \) adopta diferentes valores en \( \mathcal V \). La relación entre ambas expresiones es que, si \( x \) es una variable metamatemática y \( u \) es la menor variable distinta de \( x \), entonces, por definición,
\( [\ulcorner x\urcorner=\ulcorner 0\urcorner]=\ulcorner\forall\urcorner\ulcorner u\urcorner\ulcorner\lnot\urcorner\ulcorner u\urcorner\ulcorner\in\urcorner\ulcorner x\urcorner=\ulcorner\forall u\,u\notin x\urcorner=\ulcorner x=\ulcorner0\urcorner\urcorner.
\)
Ahora vamos a definir una función \( \mathcal V\times \mathbb N\longrightarrow \mathcal F \), que representaremos por \( [x=n] \), por recurrencia sobre \( n \), es decir, la definiremos para \( n=\ulcorner0\urcorner \) y, supuesta definida para los números naturales \( \leq n \), la definiremos para \( n+1 \). Concretamente, \( [x=\ulcorner0\urcorner]\in \mathcal F \) es la fórmula que hemos definido previamente, y
\( [x=n+1]=\ulcorner\forall\urcorner \ulcorner u\urcorner(u\,\ulcorner\in\urcorner\, x\,\ulcorner\leftrightarrow\urcorner\, [u=\ulcorner0\urcorner]\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner[u=n]),
\)
donde \( u \) es el menor elemento de \( \mathcal V \) distinto de \( x \).
Nota técnica
Los puntos suspensivos de la definición precedente esconden a su vez una definición por recurrencia. Definimos:
\( F(u,\ulcorner0\urcorner)=[u=\ulcorner0\urcorner],\quad F(u, n+1)=F(u,n)\ulcorner\lor \urcorner\,[u=n+1]. \)
Así, \( [u=\ulcorner0\urcorner]\,\ulcorner\lor\urcorner\cdots \ulcorner\lor\urcorner\,[u=n] \) es una forma de representar \( F(u, n) \). Una simple inducción sobre \( n \) prueba que
\( F(u, \ulcorner n\urcorner) = [u=\ulcorner0\urcorner]\ulcorner\lor \urcorner\,\cdots \ulcorner\lor\urcorner\,[u=\ulcorner n\urcorner].
\)
Así, si \( x \) es una variable metamatemática y \( n \) es un número natural, en Z se demuestra que
\( [\ulcorner x\urcorner=\ulcorner n\urcorner]=\ulcorner x=\ulcorner n\urcorner\urcorner. \)
Demostración
Razonamos por inducción sobre \( n \). Para \( n=0 \) ya lo hemos probado, y si se cumple para todo número natural \( \leq n \), resulta que, llamando \( u \) a la menor variable distinta de \( x \),
\( [\ulcorner x\urcorner=\ulcorner n+1\urcorner]=\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\,\ulcorner\leftrightarrow\urcorner\,[\ulcorner u\urcorner=\ulcorner 0\urcorner]\ulcorner\lor\urcorner\cdots \ulcorner\lor\urcorner[\ulcorner u\urcorner=\ulcorner n\urcorner])
\)
Por hipótesis de inducción:
\( [\ulcorner x\urcorner=\ulcorner n+1\urcorner]=\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\ulcorner\leftrightarrow\urcorner\,\ulcorner u=\ulcorner0\urcorner\urcorner\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\ulcorner u=\ulcorner n\urcorner\urcorner
\)
\( =\ulcorner\forall u(u\in x\leftrightarrow u=0\lor \cdots \lor u=n)\urcorner=\ulcorner x=\ulcorner n+1\urcorner\urcorner. \)
Pares desordenados Para pasar de aquí al caso de sucesiones finitas de números naturales necesitamos formalizar la formalización de los pares ordenados. Empezamos con los pares desordenados. Teniendo en cuenta que
\( z=\{x,y\}\equiv \forall u(u\in z\leftrightarrow u=x\lor u=y), \)
donde podemos convenir en que \( u \) es la menor variable distinta de \( x, y, z \), definimos en Z una función \( \mathcal V\times\mathcal V\times\mathcal V\longrightarrow \mathcal F \) dada por
\( [z=\{x,y\}] = \ulcorner\forall\urcorner u(u\,\ulcorner\in\urcorner\,z\ \ \ulcorner\leftrightarrow\urcorner\ \ u\,\ulcorner=\urcorner\,x\ \ \ulcorner\lor\urcorner\ \ u\,\ulcorner=\urcorner\,y),
\)
donde \( u\in \mathcal V \) es la menor variable distinta de \( x, y, z \).
Si aplicamos la función que acabamos de definir a \( \ulcorner x\urcorner, \ulcorner y\urcorner, \ulcorner z\urcorner\in \mathcal V \) obtenemos
\( [\ulcorner z\urcorner=\{\ulcorner x\urcorner, \ulcorner y\urcorner\}]= \ulcorner\forall\urcorner \ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner z\urcorner\ \ \ulcorner\leftrightarrow\urcorner\ \ \ulcorner u\urcorner\,\ulcorner=\urcorner\,\ulcorner x\urcorner\ \ \ulcorner\lor\urcorner\ \ \ulcorner u\urcorner\,\ulcorner=\urcorner\,\ulcorner y\urcorner)
\)
\( =\ulcorner\forall x(u\in z\leftrightarrow u=x\lor u=y\urcorner = \ulcorner z=\{x,y\}\urcorner. \)
Pares ordenados Similarmente, como \( (x, y)=\{\{x\},\{x,y\}\} \), tenemos que
\( z=(x, y)\equiv \forall u(u\in z\leftrightarrow u=\{x, x\}\lor u=\{x,y\}), \)
lo que nos lleva a definir una función $\mathcal V\times\mathcal V\times \mathcal V\longrightarrow \mathcal F$ mediante
\( [z=(x, y)]= \ulcorner\forall\urcorner u(u\,\ulcorner\in\urcorner\,z\ \ \ulcorner\leftrightarrow\urcorner\ \ [u=\{x,x\}]\,\ulcorner\lor\urcorner\,[u=\{x,y\}]),
\)
donde \( u \) es la menor variable distinta de \( x, y, z \). Así, si \( x, y, z \) son variables metamatemáticas y \( u \) es la menor variable distinta de ellas, tenemos que
\( [\ulcorner z\urcorner=(\ulcorner x\urcorner, \ulcorner y\urcorner)]=\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner z\urcorner\,\ulcorner\leftrightarrow\urcorner[\ulcorner u\urcorner=\{\ulcorner x\urcorner,\ulcorner x\urcorner\}]\,\ulcorner\lor\urcorner\,[\ulcorner u\urcorner=\{\ulcorner x\urcorner, \ulcorner y\urcorner\}])
\)
\( =\ulcorner\forall \urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner z\urcorner\,\ulcorner\leftrightarrow\urcorner\,\ulcorner u=\{x\}\urcorner\,\ulcorner\lor\urcorner\,\ulcorner u=\{x,y\}\urcorner)
\)
\( =\ulcorner\forall u(u\in z\leftrightarrow u=\{x\}\lor u=\{x,y\})\urcorner=\ulcorner z=(x, y)\urcorner. \)
Pares de números naturales Seguidamente definimos una función \( \mathcal V\times \mathbb N\times \mathbb N\longrightarrow \mathcal F \), que representaremos por \( [x=(m,n)] \), mediante
\( [z=(m,n)]=\ulcorner\exists\urcorner xy([x=m]\,\ulcorner\land \urcorner\,[y=n]\,\ulcorner\land\urcorner\, [z=(x,y)]). \)
donde \( x,y \) son las menores variables distintas de \( z \). Así, si \( z \) es una variable metamatemática y \( m, n \) son dos números naturales, se cumple que
\( [\ulcorner z\urcorner=(\ulcorner m\urcorner, \ulcorner n\urcorner)]=\ulcorner\exists\urcorner\ulcorner x\urcorner\ulcorner y\urcorner([\ulcorner x\urcorner=\ulcorner m\urcorner]\ulcorner\land\urcorner[\ulcorner y\urcorner=\ulcorner n\urcorner]\ulcorner\land\urcorner [\ulcorner z\urcorner=(\ulcorner x\urcorner, \ulcorner y\urcorner)])
\)
\( =\ulcorner\exists \urcorner\ulcorner x\urcorner\ulcorner y\urcorner(\ulcorner x=\ulcorner m\urcorner\urcorner\ulcorner\land\urcorner\ulcorner y=\ulcorner n\urcorner\urcorner\ulcorner\land \urcorner\ulcorner z=(x,y)\urcorner)
\)
\( =\ulcorner \exists xy(x=\ulcorner m\urcorner\land y=\ulcorner n\urcorner\land z=(z, y))\urcorner=\ulcorner z=(\ulcorner m\urcorner, \ulcorner n\urcorner)\urcorner.
\)
Conclusión Finalmente, si \( x\in \mathcal V \) y \( \zeta\in S^1 \) es una sucesión de longitud \( n+1 \), ya podemos definir
\( [x=\zeta]=\ulcorner\forall\urcorner\, u\, (u\ \ulcorner\in \urcorner\,x\,\ulcorner\leftrightarrow\urcorner[u=(\ulcorner 0\urcorner, \zeta(\ulcorner0\urcorner))]\,\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\,[u=(n,\zeta(n))]),
\)
donde \( u \) es la menor variable distinta de \( x \).
Notas técnicas
Para la sucesión vacía de longitud \( 0 \) podemos definir \( [x=\emptyset]=[x=\ulcorner0\urcorner] \), aunque nunca necesitaremos este caso.
En el caso \( n>0 \), los puntos suspensivos de la definición precedente representan otra definición por recurrencia, análoga a la que hemos visto en la formalización de la formalización de los números naturales.
De este modo, si \( \zeta \) es una sucesión finita metamatemática, teniendo en cuenta que \( \ulcorner\zeta\urcorner(\ulcorner i\urcorner)=\ulcorner\zeta_i\urcorner \), se cumple que
\( [\ulcorner x\urcorner = \ulcorner\zeta\urcorner]=\ulcorner\forall \urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\,\ulcorner\leftrightarrow\urcorner\,[\ulcorner u\urcorner\,=(\ulcorner 0\urcorner,\ulcorner\zeta_0\urcorner)]\,\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\,[\ulcorner u\urcorner=(\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner)])
\)
\( =\ulcorner\forall\urcorner\,\ulcorner u\urcorner(\ulcorner u\urcorner\,\ulcorner\in\urcorner\,\ulcorner x\urcorner\,\ulcorner\leftrightarrow\urcorner\,\ulcorner u=(\ulcorner0\urcorner,\ulcorner\zeta_0\urcorner)\urcorner\,\ulcorner\lor\urcorner\cdots\ulcorner\lor\urcorner\ulcorner u=(\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner)\urcorner)
\)
\( =\ulcorner\forall u(u\in x\leftrightarrow u=(\ulcorner 0\urcorner,\ulcorner\zeta_0\urcorner)\lor\cdots\lor u=(\ulcorner n\urcorner,\ulcorner\zeta_n\urcorner))\urcorner=\ulcorner x=\ulcorner\zeta\urcorner\urcorner.
\)