Algunos conceptos relacionados con el Teorema de Gödel

1. El Programa de Hilbert

Los teoremas de Gödel, publicados en 1931, nacieron en el contexto de una larga polémica sobre los fundamentos de la matemática cuyos orígenes se remontan a la década de 1870 con el descubrimiento por parte de Georg Cantor de los cardinales transfinitos, y que se había intensificado a partir de 1902 tras el hallazgo de la paradoja de Russell.

El campo de batalla de esta polémica era nada menos que el infinito. La escuela constructivista, encabezada por L.E.J. Brouwer, sostenía que la introducción del infinito en acto en matemática era absurda e injustificada y que la teoría de los transfinitos de Cantor era solamente un juego de palabras sin sentido. Los únicos objetos matemáticos válidos, sostenía esta escuela, son aquellos que se pueden construir mecánicamente en una cantidad finita de pasos.

Hacia 1920, con el objetivo fundamental de defender a la teoría de Cantor (y bajo el lema “Del paraíso que Cantor creó para nosotros nadie podrá expulsarnos”), interviene en la polémica el matemático alemán David Hilbert quien, en una serie de artículos publicados a lo largo de siguientes diez años, propone el que hoy es conocido como el Programa de Hilbert y que, en esencia, quitaba la exigencia de finitud y de constructividad de los objetos matemáticos para desplazarla a los razonamientos matemáticos.

Con más precisión, Hilbert proponía la creación de una nueva ciencia a la que él llamaba metamatemática. Esta ciencia tendría como objetivo el verificar la validez de los razonamientos matemáticos. Para evitar polémicas, y para asegurarse de que no surgieran paradojas, esta ciencia sería puramente sintáctica: la metamatemática trataría a los enunciados y a los razonamientos matemáticos como si fueran simples secuencias de símbolos sin significado a los que manipularía mecánicamente.

Se ha dicho en muchos textos de divulgación que el Programa de Hilbert proponía reducir la matemática a un juego de símbolos carente de significado; se ha dicho también que para Hilbert el concepto de "verdad matemática" carecía de sentido. Nada de esto es correcto. Hilbert era ante todo un investigador matemático, el mejor de su tiempo, por lo que es inimaginable que pudiera pensar de esa manera. Hilbert atribuía la reducción a simples manipulaciones de símbolos a la metamatemática, no a la matemática en sí. Los matemáticos, para Hilbert, seguirían trabajando como siempre han hecho a nivel semántico, un nivel lleno de significados. El matemático, en el día a día, trabaja, crea, conjetura y demuestra, como si lo que tuviera entre manos fueran objetos reales. La metamatemática, según la idea de Hilbert, trabajaría a nivel sintáctico y sólo proveería los métodos para verificar si los razonamientos que el matemático ha hecho son correctos.
En concreto, el Programa de Hilbert proponía dar un conjunto de axiomas para la aritmética que cumpliera las siguientes cuatro condiciones:

a) El sistema debía ser consistente; es decir, no debía existir un enunciado P tal que P y su negación fueran simultáneamente demostrables.
b) La validez de cualquier demostración debía ser verificable por manipulaciones mecánicas en una cantidad finita de pasos. Traducida a un lenguaje moderno, esta condición dice que debía ser posible, al menos en teoría, programar una computadora de tal modo que fuese capaz de verificar la validez de los razonamientos matemáticos,
c) Dado cualquier enunciado P, o bien él o bien su negación debía ser demostrable.
d) La consistencia de los axiomas debía ser verificable mecánicamente en una cantidad finita de pasos.

Como se ha dicho, Hilbert fue dando forma a este programa a lo largo de la década de 1920; sin embargo, en 1931 los teoremas de Gödel demostraron que esas cuatro condiciones no pueden cumplirse a la vez.

Concretamente, el primer teorema de incompletitud de Gödel dice que si se cumplen las condiciones a) y b) entonces necesariamente la condición c) falla. Por su parte, el llamado segundo teorema de incompletitud de Gödel, del que no nos ocuparemos aquí, prueba que si se cumplen las condicoiones a) y b) entonces es la condición d) la que falla.

2. La numeración de Gödel

En lo que sigue, expondremos las ideas principales de la demostración del primer teorema de Gödel. Supongamos, entonces, que se ha dado un conjunto de axiomas para la aritmética que cumple las condiciones a) y b). En realidad, a los efectos de nuestro desarrollo, y para evitar tecnicismos, supondremos que todos los axiomas propuestos son enunciados verdaderos.

Estrictamente hablando, esta última hipótesis no es necesaria para demostrar el primer teorema de Gödel, sin embargo, por una parte, es obvio que se trata de una suposición perfectamente razonable (nadie propondría seriamente basar la aritmética en axiomas falsos). Por otra parte, además, suponer que los axiomas son enunciados verdaderos implica inmediatamente que estos satisfacen la condición a); en efecto, si todos los axiomas son verdaderos entonces los teoremas que se deducen de ellos son también enunciados verdaderos. En otras palabras, es imposible demostrar un enunciado falso, por lo que, tal como pide la condición a), nunca sucederá que exista un enunciado P tal que él y su negación sean a la vez demostrables.

Como se ha dicho más arriba, supondremos también que se cumple la condición b), es decir, que la validez de toda demostración basada en los axiomas elegidos es verificable algorítmicamente en una cantidad finita de pasos.

El comienzo de la demostración del primer teorema de Gödel consiste en asignar a cada enunciado aritmético un número natural, llamado el número de Gödel de ese enunciado. Por ejemplo, al enunciado “2 es un número par” podría corresponderle el número de Gödel 23.627; o al enunciado “22 es un número primo” podría corresponderle el número de Gödel 11.705.

Debemos hacer aquí varias aclaraciones. La primera es que el enunciado “22 es un número primo” es evidentemente falso; en efecto, Gödel le asigna un número a cada enunciado aritmético, tanto a los verdaderos como a los falsos. La segunda aclaración, muy importante, es que la asignación de los números de Gödel no se hace al azar; los ejemplos mostrados más arriba son puramente hipotéticos y tienen el único objetivo de ejemplificar la idea de que a cada enunciado se le asigna un número. Estos ejemplos no deben ser tomados de ninguna manera como representativos del modo en que los números de Gödel son asignados. En realidad, antes de hacer la asignación cada enunciado debe ser traducido a un lenguaje formal estrictamente definido; sólo después de que esa traducción se ha completado el número de Gödel correspondiente al enunciado en cuestión es calculado mediante un procedimiento algorítmico rigurosamente especificado. En la práctica, de hecho, el número de Gödel de cualquier enunciado, aun de los más simples, tiene siempre una gran cantidad de cifras.

Una vez que se ha asignado un número de Gödel a cada enunciado, queda bien definido el conjunto de los números de Gödel de todos los enunciados que son demostrables a partir de los axiomas propuestos. El grueso de la demostración del primer teorema de Gödel consiste en probar que ese conjunto de números puede definirse apelando únicamente a propiedades aritméticas (que son las propiedades referidas a los números naturales que son expresables en términos de la suma, el producto y las operaciones lógicas usuales). Es decir, la propiedad lógica “Es el número de Gödel de un enunciado demostrable” puede traducirse a una propiedad puramente aritmética (aunque no siempre lo explicitemos, debe entenderse en todo momento que “demostrable” significa “demostrable a partir de los axiomas aritméticos propuestos”). Por ejemplo, podría suceder que los números de Gödel de los enunciados demostrables sean exactamente los números primos terminados en 7. Una vez más debemos aclarar que este último ejemplo es puramente hipotético y sólo tiene la intención de mostrar lo que entendemos por “propiedad aritmética”. En la práctica, la propiedad aritmética que define a los números de Gödel de los enunciados que son demostrables a partir de un cierto conjunto de axiomas es siempre muy compleja de enunciar.

Es importante destacar también que es en este punto de la demostración donde entra en juego la hipótesis b). En efecto, puede probarse que si se admiten métodos de demostración que no son verificables algorítmicamente  entonces no es necesariamente cierto que la propiedad de ser el código de Gödel de un enunciado demostrable sea expresable mediante propiedades aritméticas.

3. El método de autorreferencia

Planteemos un nuevo ejemplo hipotético; imaginemos que al enunciado “23.409 es un número par” le correspondiera el número de Gödel 23.409. Podríamos entonces parafrasear este enunciado como diciendo, falsamente, que “Mi número de Gödel es par”.

Ahora bien ¿es razonable suponer que existe un enunciado que se refiera a su propio número de Gödel? En realidad sí es razonable, porque Gödel probó que, dada cualquier propiedad aritmética, como por ejemplo “Es un número par” o “Es un número primo”, siempre existe un enunciado aritmético que puede parafrasearse como diciendo que su propio número de Gödel cumple esa propiedad. Es decir, existe necesariamente un número n tal que al enunciado “n es par” le corresponde el número de Gödel n y un número m tal que al enunciado “m es primo” le corresponde el número de Gödel m. En otras palabras, Gödel mostró un método para obtener enunciados autorreferentes.

Dijimos antes que la propiedad “Es el número de Gödel de un enunciado demostrable” es traducible a una propiedad aritmética; de la misma forma, también es traducible la propiedad “No es el número de Gödel de un enunciado demostrable” (en el contexto del ejemplo hipotético dado más arriba, “No es el número de Gödel de un enunciado demostrable” equivaldría a “No es cierto que es un número primo terminado en 7”).
En consecuencia, por lo dicho más arriba, existe necesariamente un número k tal que al enunciado “k no el número de Gödel de un enunciado demostrable” (que en el ejemplo hipotético equivale a “No es cierto que k es un número primo terminado en 7”) le corresponde el número k. En otras palabras, ese enunciado dice, “Mi número de Gödel no corresponde a un enunciado demostrable” o, dicho más simplemente, el enunciado afirma “Yo no soy demostrable”. Veamos a continuación que este enunciado es verdadero, pero no es demostrable a partir de los axiomas propuestos.

Para probar que “Yo no soy demostrable” es verdadero pero no demostrable supongamos, en primer lugar, que fuera falso. En ese caso, lo que enuncia es incorrecto, por lo que sí sería demostrable. Es decir, sería falso y demostrable a la vez, pero esto es imposible porque los axiomas son enunciados verdaderos.

Entonces “Yo no soy demostrable” es necesariamente verdadero, pero entonces lo que enuncia es verdad y, por lo tanto, es verdadero y no demostrable.

Notemos que esto implica, tal como queríamos probar, que la condición c) falla. En efecto, el enunciado aritmético que expresa que “Yo no soy demostrable” no es demostrable, pero tampoco lo es su negación, ya que esta negación es un enunciado falso, y si los axiomas son enunciados verdaderos entonces ningún enunciado falso puede ser demostrable. Hemos probado así que, contradiciendo lo que pide condición c), existe siempre un enunciado P tal que ni él, ni su negación, son demostrables. De este modo, termina nuestra exposición de las ideas centrales de la demostración del primer teorema de Gödel.

4. Conclusión

El programa de Hilbert proponía que se diera un conjunto de axiomas aritméticos que cumpliera las condiciones a), b), c) y d) enunciadas más arriba. La condición a) puede parafrasearse diciendo que el sistema no debe permitir que se demuestren enunciados falsos, en otras palabras, los axiomas nunca deben conducir a una paradoja; la condición d) pide, además, que la validez de la condición a) sea verificable de un modo claro y objetivo. La condición b), por su parte, pide que también exista un método claro, objetivo y concreto para verificar la validez de los razonamientos matemáticos. La condición c), finalmente, pide esencialmente que todas las verdades aritméticas sean demostrables.

Los teoremas de Gödel prueban que estas cuatro condiciones no pueden cumplirse simultáneamente. En particular, el primer teorema demuestra que si sólo admitimos razonamientos cuya validez sea verificable objetivamente entonces siempre habrá verdades matemáticas que no podamos demostrar. En otras palabras, tenemos que elegir entre la certeza absoluta de que no cometeremos errores y la certeza absoluta de que podremos resolver todos los problemas matemáticos. Tenemos que elegir, dice Gödel, entre una de esas dos certezas porque nunca podemos tener ambas al mismo tiempo.