Hace un tiempo, sobre todo a raíz de algunos textos que leí acerca de la «aplicación» de los teoremas de incompletitud de Gödel a temas con los que no tienen ninguna relación, volvió a mi cabeza la idea de hablar sobre estos teoremas en el blog. Para ello preferí intentar contar con la colaboración de algún especialista en el tema, y casi automáticamente vino a mi mente el nombre de Gustavo Piñeiro, matemático argentino, autor junto a Guillermo Martínez del libro Gödel para Todos (editado en 2009 en Argentina y en 2010 en España y que ya os recomendé para el día del libro en 2012) y responsable del blog El Topo Lógico, dedicado a la divulgación de la matemática.

Gustavo accedió gustosamente a mi sugerencia de colaboración, y hoy, por fin, se publica el texto que escribió sobre el primer teorema de incompletitud de Gödel para Gaussianos. Espero que os aclare todas vuestras dudas sobre ello. Y si no es así ya sabéis que tenéis los comentarios de este post para plantearlas.


El Programa de Hilbert

Los dos teoremas de incompletitud de Gödel, publicados en 1931, forman parte de una larga polémica relativa a los fundamentos de las matemáticas. Esta polémica había comenzado a finales del siglo XIX a causa de los trabajos de Georg Cantor sobre los conjuntos infinitos, y se había exacerbado a principios del siglo XX con el descubrimiento de la Paradoja de Russell.

En esta polémica, la escuela intuicionista, encabezada por L.E.J. Brouwer, sostenía que el uso que había hecho Cantor del infinito en acto era absurdo e injustificado y que toda su teoría no era más que un juego de palabras sin sentido. Los únicos objetos matemáticos válidos, sostenía esta escuela, son aquellos que se pueden construir algorítmicamente en una cantidad finita de pasos.

David HilbertPero el gran matemático alemán David Hilbert no estaba para nada de acuerdo con la idea de descartar la teoría de Cantor y hacia 1920 intervino en la polémica para proponer una alternativa al intuicionismo. Fue así como, en una serie de artículos publicados a lo largo de los diez años siguientes, le dio forma al llamado Programa de Hilbert, el cual, en esencia, llevaba la exigencia de finitud y de constructividad de los objetos matemáticos 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 verificar la validez de los razonamientos matemáticos. Para evitar polémicas, y para asegurarse de que no surgieran nuevas paradojas, esta ciencia sería puramente finitista, es decir, 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 algorítmicamente.

Con más precisión, el Programa de Hilbert proponía dar un conjunto de axiomas para la aritmética que cumpliera estas cuatro condiciones:

1. 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 a partir de los axiomas.

2. La validez de cualquier demostración basada en esos axiomas debía ser verificable algorítmicamente en una cantidad finita de pasos.

3. Dado cualquier enunciado P, o bien él o bien su negación debía ser demostrable a partir de los axiomas.

4. La consistencia de los axiomas (es decir, la validez de la primera condición) debía ser verificable algorítmicamente en una cantidad finita de pasos.

(La aritmética es la teoría que habla de la suma y el producto de los números naturales. Hilbert consideraba que era ésta la teoría fundamental de la Matemática, y no la Teoría de Conjuntos.)

Los teoremas de Gödel

Kurt GödelEn un congreso sobre los fundamentos de las matemáticas celebrado en la ciudad de Königsberg en septiembre de 1930 Arend Heyting, en representación de la escuela intuicionista, dio por terminada la polémica al aceptar que el Programa de Hilbert era el camino que debía seguir el pensamiento matemático. Pero lamentablemente para Hilbert, en ese mismo momento un joven y aún desconocido Kurt Gödel pidió la palabra para decir que él acababa de demostrar dos teoremas que probaban que el Programa de Hilbert era completamente irrealizable.

Concretamente, el primer teorema de incompletitud de Gödel, el más famoso de los dos, dice que si se cumplen las dos primeras condiciones planteadas por Hilbert entonces la tercera nunca podrá cumplirse. Es decir, si el sistema de axiomas es consistente y sólo se admiten demostraciones que sean verificables algorítmicamente, entonces siempre habrá un enunciado P tal que ni él si su negación son demostrables. El segundo teorema, al que no nos referiremos aquí, dice que si se cumplen las dos primeras condiciones y una versión más débil de la tercera entonces es la cuarta condición la que no podrá cumplirse.

La demostración del primer teorema

Vamos a explicar las ideas principales de la demostración del primer teorema de incompletitud de Gödel. Imaginemos entonces que se ha dado un sistema de axiomas para la aritmética que es consistente y supongamos además que sólo admitimos demostraciones verificables algorítmicamente. Tenemos que demostrar entonces que existe un enunciado, al que llamaremos G, tal que ni él ni su negación son demostrables a partir de esos axiomas mediante las demostraciones admitidas.

El primer paso de la demostración consiste en asignar a cada enunciado aritmético un número natural, al que llamaremos el número de Gödel de ese enunciado. Por ejemplo, al enunciado “2 es par” podría corresponderle el número 19, mientras que al enunciado “9 es primo” podría corresponderle el número 44.

Debemos hacer aquí dos aclaraciones importantes. La primera es que la asignación de números de Gödel alcanza a todos los enunciados, tanto a los verdaderos como a los falsos. La segunda aclaración es que ; los ejemplos dados más arriba son meramente hipotéticos y sirven solamente para facilitar la comprensión de la idea. Para asignar realmente los números de Gödel a los enunciados estos deben estar previamente escritos en un lenguaje formal específico y la asignación en sí se hace mediante fórmulas claramente definidas. Además, los números de Gödel, en general, tienen una enorme cantidad de cifras (más detalles pueden verse en este enlace).

Segunda parte de la demostración

Una vez que se han asignado todos los números de Gödel queda perfectamente establecido cuál es el conjunto de estos números que corresponden a los enunciados que son demostrables a partir de los axiomas dados. La segunda parte de la demostración del primer teorema de incompletitud consiste en probar que este conjunto puede definirse usando solamente propiedades aritméticas. Es decir, el conjunto formado por los números de Gödel de los enunciados demostrables es definible mediante propiedades puramente numéricas.

Normalmente esa propiedad numérica es terriblemente compleja de expresar; pero para que se entienda la idea vamos a suponer que los números de Gödel de los enunciados demostrables son exactamente los números que se pueden escribir como suma o resta de tres primos consecutivos. Por ejemplo, dado que 3 – 5 + 7 = 5, entonces el número 5 es el número de Gödel de un enunciado demostrable; lo mismo sucede con el 13, que es -5 + 7 + 11. El 2, en cambio, no puede escribirse como suma o resta de tres primos consecutivos, por lo que 2 no es el código de un enunciado demostrable (siempre entendemos «demostrable a partir de los axiomas dados»).

Es interesante observar que es en esta parte del razonamiento donde interviene la suposición de que las demostraciones aceptadas por el programa de Hilbert son aquellas que son verificables algorítmicamente. En efecto, si esta condición no se cumpliera entonces no hay modo de garantizar que el conjunto de los números de Gödel de los enunciados demostrables puede caracterizarse aritméticamente.

El método de autorreferencia

La tercera parte de la demostración consiste en probar que, dada cualquier propiedad aritmética P, existe un número k tal que al enunciado “k cumple la propiedad P” le corresponde ese mismo número k. Podemos llamar a esta idea el método de autorreferencia, ya que el enunciado en esencia está diciendo “Mi número de Gödel cumple la propiedad P”.

Este método nos dice entonces que existe un número n tal que al enunciado «n no se puede escribir como suma o resta de tres primos consecutivos» le corresponde como número de Gödel precisamente el número n. Supongamos, para fijar ideas, que ese número n es el 43. Es decir, estamos suponiendo que al enunciado, que llamaremos G, que dice «43 no se puede escribir como suma o resta de tres primos consecutivos» le corresponde el número de Gödel 43.

Notemos que G dice “Mi número de Gödel no se puede escribir como suma o resta de tres primos consecutivos», y como estamos suponiendo que ésa es la propiedad que caracteriza a los números de Gödel de los enunciados demostrables entonces G está diciendo: “Mi número de Gödel no corresponde a un enunciado demostrable”. En definitiva, G dice: “Yo no soy demostrable”.

Conviene destacar aquí que la referencia a los números que se pueden escribir como suma o resta de tres primos consecutivos sólo sirve a modo de ejemplo hipotético y con fines puramente didácticos. En realidad Gödel demuestra que, sin importar cuáles sean los axiomas propuestos, si se cumplen las dos primeras condiciones del Programa de Hilbert siempre es posible hallar un enunciado aritmético que puede parafrasearse como “Yo no soy demostrable”.

La cuarta, y última parte, de la demostración del primer teorema de Gödel consiste en probar que ni G ni su negación son demostrables a partir de los axiomas dados. Para facilitar la explicación de esta última parte vamos a suponer que los axiomas que se han dado son todos enunciados verdaderos, una suposición que parece evidente, pero que la demostración que hizo Gödel en realidad no necesita (para Gödel es suficiente con que el sistema sea consistente; los axiomas, en la versión original del teorema, no necesitan se verdaderos).

Tenemos entonces que el enunciado G es un enunciado aritmético que dice esencialmente “G no es demostrable a partir de los axiomas dados”.

Observemos que si todos los axiomas son todos enunciados verdaderos entonces los enunciados que pueden demostrarse a partir de ellos también son verdaderos. Ahora bien, el enunciado G puede ser verdadero o falso. Si fuera falso, entonces, leyendo lo que dice, deduciríamos que G sí es demostrable. Tendríamos así un enunciado falso y demostrable, pero esto, por lo dicho más arriba, es imposible.

Luego G es verdadero, pero como es verdadero entonces, tomando en cuenta lo que dice de sí mismo, deducimos que no es demostrable a partir de los axiomas dados. Luego G es verdadero, pero no demostrable. Observemos que la negación de G, dado que es falsa, tampoco es demostrable. Es decir, ni G ni su negación son demostrables a partir de los axiomas dados. Esto completa la demostración del primer teorema de Gödel.


Esta es la tercera contribución de Gaussianos a la Edición 5.7: Alan Turing del Carnaval de Matemáticas, que en esta ocasión tiene como anfitrión a @cuantozombi en su blog El zombi de Schrödinger.

Print Friendly, PDF & Email