Gödel en una cáscara de nuez: Primer Teorema de Incompletitud

Tras haber visto anteriormente el corte diagonal de Cantor, podemos hacer ya una incursión en el terreno de los teoremas de incompletitud de Gödel. Para ello, hay que empezar por enmarcar el contexto en el que estos teoremas se formulan, tanto desde el punto de vista histórico, como desde el punto de vista formal. Con respecto a lo primero, hay que hacer mención sin duda a la enorme figura de David Hilbert, y en particular a su programa formalista. De acuerdo con la visión de Hilbert, todas las ramas de las matemáticas se podrían llegar formalizar en un sistema completo (en el que todo lo que fuera cierto fuera demostrable), consistente (en el que no se pudieran demostrar cosas falsas), y decidible (la verdad o falsedad de una afirmación matemática sería demostrable mediante un procedimiento mecánico bien definido). Esta última parte -la decibilidad- hace evidentemente referencia a la noción de algoritmo, que no obstante no estaba aún formalizada tal como la entendemos actualmente. Éste será precisamente el vínculo que nos permitirá enlazar los resultados de Gödel con los de Turing más adelante.

Fue en pleno apogeo del programa de Hilbert en el que Gödel presentó los teoremas de incompletitud que dieron al traste con el mismo. El marco formal en el que dichos teoremas se encuadran es el de la lógica de primer orden. En dicho marco empleamos predicados para razonar acerca de un conjunto de objetos. Mediante estos predicados podemos realizar afirmaciones sobre objetos concretos (por ejemplo, par(2), que podríamos interpretar como «2 es par»), o expresar afirmaciones más genéricas mediante el uso de variables y cuantificadores. Por ejemplo:

Por supuesto, debemos disponer también de unos axiomas, que establezcan verdades básicas de partida, y un conjunto de reglas de inferencia que nos permitan demostrar la verdad o falsedad de una afirmación como la anterior. De hecho, si la ambición de Hilbert fuera factible, dada una afirmación cualquiera (y no sólo en el marco de la lógica de primer orden) se podrían aplicar de forma mecánica las reglas de inferencia hasta o bien demostrar dicha afirmación (en cuyo caso sería cierta) o su negación (en cuyo caso sería falsa). Gödel demostró que esto no es posible, ya que un sistema lo suficientemente complejo como para permitir expresar y demostrar verdades aritméticas sobre los números naturales (esto es, un superconjunto de la aritmética de Peano), será o bien inconsistente (en cuyo caso se podrá demostrar cualquier cosa), o incompleto (en cuyo caso habrá afirmaciones indemostrables e irrefutables).

La base de los teoremas de incompletitud es lo que se conoce como aritmetización, numeración de Gödel, o simplemente gödelización. Gödel definió un procedimiento que permite codificar una secuencia de símbolos en un número natural. Los detalles de como conseguir esto no son importantes en este momento, pero a grandes rasgos se basan en el hecho de que la descomposición en factores primos de un número es única. De esta forma, se puede asociar a cualquier fórmula lógica (o secuencia de fórmulas lógicas) F un número natural g(F). Esta posibilidad resulta crucial aquí, ya que es la que nos va a permitir expresar la auto-referencia y en última instancia aplicar el corte diagonal.

Una vez tenemos formulas y demostraciones codificadas mediante números naturales, es fácil expresar la noción de demostrabilidad mediante una fórmula lógica D(x,y), que interpretaremos como «x es el número de Gödel de una demostración de la fórmula cuyo número de Gödel es y«. Por lo tanto, una fórmula F será demostrable (cosa que indicaremos por P(x), donde x=g(F)) si tiene al menos una demostración, esto es:

Ya estamos listos para aplicar el corte diagonal. Definamos para ello la noción de auto-indemostrabilidad Q(x) como

,

es decir, una formula F es auto-indemostrable si no se puede demostrar F(g(F)). ¿Qué ocurre cuando F=Q, esto es, es demostrable que no hay demostración para G=Q(g(Q))? Analicemos las posibilidades:

• Supongamos que sí es demostrable, esto es, que P(g(G)) es cierto, y por lo tanto existe un y tal que D(y,g(G)) es cierto. En este caso, nótese que D(y,g(G)) = D(y,g(Q(g(Q)))). Sin embargo, que Q(g(Q)) sea cierto implica por su propia definición que no existe ningún y para el que D(y,g(Q(g(Q)))) sea cierto. Luego habríamos demostrado algo falso, y el sistema sería inconsistente.
• Supongamos que no es demostrable. Volvamos entonces nuestra atención hacía su negación. Si existe un y tal que D(y,g(~G)) es cierto quiere decir que ~Q(g(Q)) es cierto, esto es, que existe un z tal que D(z,g(Q(g(Q)))) = D(z,g(G)) es cierto. Esto contradice nuestra suposición de partida de que G era indemostrable, y en cualquier caso produce una inconsistencia al haber una demostración de G y de ~G.

El razonamiento anterior puede ser algo farragoso, pero en esencia se reduce al hecho de que G afirma su propia indemostrabilidad. Si G es demostrable, entonces es falso y al haber demostrado algo falso nuestro sistema es inconsistente. Si su negación es demostrable, entonces por definición G es demostrable, con lo que el sistema es nuevamente inconsistente (ya que hemos demostrado algo y su negación). Por lo tanto, si el sistema es consistente, ni G ni ~G son demostrables, luego el sistema es incompleto.

Es importante notar el hecho de que en ningún momento se afirma que G sea cierta o no, sólo que ella y su negación son indemostrables si el sistema es consistente. Sin embargo, si analizamos la situación podemos llegar a la conclusión de que sí es cierta: desde nuestro punto de vista externo al sistema, está claro que no hay demostración de G, que es lo que G afirma, por lo que debe ser cierta. Que podamos percibir este hecho es uno de los argumentos más frecuentemente invocados para sostener que nuestra mente no es algorítmica, y por lo tanto negar la posibilidad de que pueda ser representada mediante un modelo computacional equivalente a una máquina de Turing. Esto merece comentario aparte en un futuro artículo.