En 1931, el lógico austriaco Kurt Gödel consiguió uno de los logros intelectuales más sorprendentes de la historia.
Los matemáticos de la época buscaban un fundamento sólido para las matemáticas: un conjunto de hechos matemáticos básicos, o axiomas, que fuera a la vez consistente -que nunca condujera a contradicciones- y completo, que sirviera como los bloques de construcción de todas las verdades matemáticas.
Pero los impactantes teoremas de incompletitud de Gödel, publicados cuando sólo tenía 25 años, destrozaron ese sueño. Demostró que cualquier conjunto de axiomas que se pueda plantear como posible fundamento de las matemáticas será inevitablemente incompleto; siempre habrá hechos verdaderos sobre los números que no se puedan demostrar con esos axiomas. También demostró que ningún conjunto candidato de axiomas puede demostrar nunca su propia consistencia.
Sus teoremas de incompletitud significaron que no puede haber una teoría matemática del todo, ninguna unificación de lo que es demostrable y lo que es verdadero. Lo que los matemáticos pueden demostrar depende de sus supuestos de partida, no de ninguna verdad fundamental de la que surjan todas las respuestas.
En los 89 años transcurridos desde el descubrimiento de Gödel, los matemáticos han tropezado justo con el tipo de preguntas sin respuesta que preveían sus teoremas. Por ejemplo, el propio Gödel ayudó a establecer que la hipótesis del continuo, que se refiere a los tamaños del infinito, es indecidible, al igual que el problema de detención, que pregunta si un programa de ordenador alimentado con una entrada aleatoria se ejecutará para siempre o se detendrá finalmente. Las cuestiones indecidibles han surgido incluso en la física, lo que sugiere que la incompletitud gödeliana afecta no sólo a las matemáticas, sino también -de alguna manera mal entendida- a la realidad.
Aquí hay un resumen simplificado e informal de cómo Gödel demostró sus teoremas.
Numeración de Gödel
La principal maniobra de Gödel fue mapear afirmaciones sobre un sistema de axiomas en afirmaciones dentro del sistema, es decir, en afirmaciones sobre números. Este mapeo permite a un sistema de axiomas hablar de forma convincente sobre sí mismo.
El primer paso en este proceso es mapear cualquier posible enunciado matemático, o serie de enunciados, a un número único llamado número de Gödel.
La versión ligeramente modificada del esquema de Gödel presentada por Ernest Nagel y James Newman en su libro de 1958, La demostración de Gödel, comienza con 12 símbolos elementales que sirven como vocabulario para expresar un conjunto de axiomas básicos. Por ejemplo, la afirmación de que algo existe puede expresarse con el símbolo ∃, mientras que la suma se expresa con +. Es importante destacar que el símbolo s, que denota «sucesor de», da una forma de especificar números; ss0, por ejemplo, se refiere a 2.
A estos doce símbolos se les asignan los números de Gödel del 1 al 12.
| Signo constante | Número de Gödel | Significado usual |
| ~ | 1 | no | ∨ | 2 | o | ⊃ | 3 | si…entonces… | ∃ | 4 | hay es un… |
| = | 5 | equals | 6 | cero |
| s | 7 | el sucesor de |
| ( | 8 | signo de puntuación |
| ) | 9 | signo de puntuación |
| , | 10 | signo de puntuación |
| + | 11 | plus |
| × | 12 | veces |
Siguiente, las letras que representan las variables, empezando por x, y y z, se asignan a números primos mayores que 12 (es decir, 13, 17, 19, …).
Entonces, cualquier combinación de estos símbolos y variables -es decir, cualquier fórmula aritmética o secuencia de fórmulas que se pueda construir- obtiene su propio número de Gödel.
Por ejemplo, consideremos 0 = 0. Los tres símbolos de la fórmula corresponden a los números de Gödel 6, 5 y 6. Gödel necesita cambiar esta secuencia de tres números en un único número, un número que ninguna otra secuencia de símbolos generará. Para ello, toma los tres primeros números primos (2, 3 y 5), eleva cada uno de ellos al número de Gödel del símbolo que ocupa la misma posición en la secuencia y los multiplica. Así, 0 = 0 se convierte en 26 × 35 × 56, o 243.000.000.
El mapeo funciona porque no hay dos fórmulas que acaben con el mismo número de Gödel. Los números de Gödel son enteros, y los enteros sólo se factorizan en primos de una sola manera. Así que la única factorización en primos de 243.000.000 es 26 × 35 × 56, lo que significa que sólo hay una forma posible de descifrar el número de Gödel: la fórmula 0 = 0.
Gödel fue entonces un paso más allá. Una demostración matemática consiste en una secuencia de fórmulas. Así que Gödel dio a cada secuencia de fórmulas un único número de Gödel también. En este caso, comienza con la lista de números primos como antes – 2, 3, 5 y así sucesivamente. A continuación, eleva cada primo al número de Gödel de la fórmula que se encuentra en la misma posición de la secuencia (2243.000.000 × …, si 0 = 0 es el primero, por ejemplo) y lo multiplica todo junto.
Aritmetizando las metamatemáticas
La verdadera ventaja es que incluso los enunciados sobre fórmulas aritméticas, llamados enunciados metamatemáticos, pueden traducirse a su vez en fórmulas con números de Gödel propios.
Consideremos primero la fórmula ~(0 = 0), que significa «el cero no es igual a cero». Esta fórmula es claramente falsa. Sin embargo, tiene un número de Gödel: 2 elevado a la potencia de 1 (el número de Gödel del símbolo ~), multiplicado por 3 elevado a la potencia de 8 (el número de Gödel del símbolo del «paréntesis abierto»), y así sucesivamente, dando como resultado 2¹ × 38 × 56 × 75 × 116 × 139.
Debido a que podemos generar números de Gödel para todas las fórmulas, incluso las falsas, podemos hablar con sentido de estas fórmulas hablando de sus números de Gödel.
Consideremos la afirmación: «El primer símbolo de la fórmula ~(0 = 0) es una tilde». Este enunciado metamatemático (verdadero) sobre ~(0 = 0) se traduce en un enunciado sobre el número de Gödel de la fórmula, a saber, que su primer exponente es 1, el número de Gödel para una tilde. En otras palabras, nuestra afirmación dice que 2¹ × 38 × 56 × 75 × 116 × 139 sólo tiene un único factor de 2. Si ~(0 = 0) empezara con cualquier símbolo que no fuera una tilde, su número de Gödel tendría al menos dos factores de 2. Así que, más exactamente, 2 es un factor de 2¹ × 38 × 56 × 75 × 116 × 139, pero 22 no es un factor.
Podemos convertir la última frase en una fórmula aritmética precisa que podemos escribir* utilizando símbolos elementales. Esta fórmula, por supuesto, tiene un número de Gödel, que podríamos calcular mapeando sus símbolos en potencias de primos.
Este ejemplo, escribieron Nagel y Newman, «ejemplifica una idea muy general y profunda que se encuentra en el corazón del descubrimiento de Gödel: se puede hablar de las propiedades tipográficas de largas cadenas de símbolos de una manera indirecta pero perfectamente precisa, hablando en cambio de las propiedades de las factorizaciones primos de los enteros grandes.»
La conversión en símbolos también es posible para el enunciado metamatemático, «Existe alguna secuencia de fórmulas con el número x de Gödel que demuestra la fórmula con el número k de Gödel» – o, en pocas palabras, «La fórmula con el número k de Gödel se puede demostrar». La capacidad de «aritmetizar» este tipo de afirmaciones sentó las bases para el golpe.
G mismo
La idea extra de Gödel era que podía sustituir el propio número de Gödel de una fórmula en la fórmula misma, lo que llevaba a un sinfín de problemas.
Para ver cómo funciona la sustitución, considere la fórmula (∃x)(x = sy). (Se lee: «Existe alguna variable x que es la sucesora de y» o, en pocas palabras, «y tiene un sucesor»). Como todas las fórmulas, tiene un número de Gödel – algún número entero grande que llamaremos simplemente m.
Ahora introduzcamos m en la fórmula en lugar del símbolo y. Esto forma una nueva fórmula, (∃x)(x = sm), que significa, «m tiene un sucesor». ¿Cómo llamaremos al número de Gödel de esta fórmula? Hay que transmitir tres datos: Empezamos con la fórmula que tiene el número de Gödel m. En ella, sustituimos m por el símbolo y. Y según el esquema de mapeo introducido antes, el símbolo y tiene el número de Gödel 17. Así que designemos el número de Gödel de la nueva fórmula como sub(m, m, 17).
La sustitución constituye el quid de la prueba de Gödel.
Consideró una afirmación metamatemática del tipo «La fórmula con número de Gödel sub(y, y, 17) no se puede demostrar.» Recordando la notación que acabamos de aprender, la fórmula con número de Gödel sub(y, y, 17) es la que se obtiene tomando la fórmula con número de Gödel y (alguna variable desconocida) y sustituyendo esta variable y en cualquier lugar donde haya un símbolo cuyo número de Gödel sea 17 (es decir, en cualquier lugar donde haya una y).
Las cosas se están poniendo triposas, pero sin embargo, nuestro enunciado metamatemático – «La fórmula con número de Gödel sub(y, y, 17) no se puede demostrar»- se traduce con seguridad en una fórmula con un número de Gödel único. Llamémoslo n.
Ahora, una última ronda de sustitución: Gödel crea una nueva fórmula sustituyendo el número n en cualquier lugar donde haya una y en la fórmula anterior. Su nueva fórmula dice: «La fórmula con el número de Gödel sub(n, n, 17) no se puede demostrar». Llamemos a esta nueva fórmula G.
Naturalmente, G tiene un número de Gödel. ¿Cuál es su valor? He aquí que debe ser sub(n, n, 17). Por definición, sub(n, n, 17) es el número de Gödel de la fórmula que resulta de tomar la fórmula con número de Gödel n y sustituir n en cualquier lugar donde haya un símbolo con número de Gödel 17. Y G es exactamente esta fórmula. Debido a la unicidad de la factorización de primos, ahora vemos que la fórmula de la que habla G no es otra que la propia G.
G afirma de sí misma que no puede ser demostrada.
¿Pero puede demostrarse G? Si es así, esto significaría que hay alguna secuencia de fórmulas que prueban la fórmula con número de Gödel sub(n, n, 17). Pero eso es lo contrario de G, que dice que no existe tal prueba. Los enunciados opuestos, G y ~G, no pueden ser ambos verdaderos en un sistema axiomático consistente. Así que la verdad de G debe ser indecidible.
Sin embargo, aunque G es indecidible, es claramente verdadera. G dice: «La fórmula con el número de Gödel sub(n, n, 17) no puede demostrarse», ¡y eso es exactamente lo que hemos comprobado! Dado que G es verdadera pero indecidible dentro del sistema axiomático utilizado para construirla, ese sistema es incompleto.
Podrías pensar que podrías simplemente plantear algún axioma extra, utilizarlo para demostrar G y resolver la paradoja. Pero no se puede. Gödel demostró que el sistema axiomático aumentado permitirá la construcción de una nueva fórmula verdadera Gʹ (según un esquema similar al anterior) que no puede demostrarse dentro del nuevo sistema aumentado. Al esforzarse por conseguir un sistema matemático completo, nunca podrá atrapar su propia cola.
No hay prueba de consistencia
Hemos aprendido que si un conjunto de axiomas es consistente, entonces es incompleto. Ese es el primer teorema de incompletitud de Gödel. El segundo -que ningún conjunto de axiomas puede demostrar su propia consistencia- se deduce fácilmente.
¿Qué significaría que un conjunto de axiomas pudiera demostrar que nunca producirá una contradicción? Significaría que existe una secuencia de fórmulas construidas a partir de estos axiomas que prueban la fórmula que significa, metamatemáticamente, «Este conjunto de axiomas es consistente». Por el primer teorema, este conjunto de axiomas sería entonces necesariamente incompleto.
Pero «El conjunto de axiomas es incompleto» es lo mismo que decir: «Existe una fórmula verdadera que no se puede demostrar». Este enunciado es equivalente a nuestra fórmula G. Y sabemos que los axiomas no pueden demostrar G.
Así que Gödel ha creado una prueba por contradicción: Si un conjunto de axiomas pudiera demostrar su propia consistencia, entonces podríamos demostrar G. Pero no podemos. Por tanto, ningún conjunto de axiomas puede demostrar su propia consistencia.
La prueba de Gödel acabó con la búsqueda de un sistema matemático consistente y completo. El significado de la incompletitud «no ha sido completamente comprendido», escribieron Nagel y Newman en 1958. Sigue siendo cierto hoy en día.
*Para los curiosos, la afirmación dice: «Existe algún número entero x tal que x multiplicado por 2 es igual a 2¹ × 38 × 56 × 75 × 116 × 139, y no existe ningún número entero x tal que x multiplicado por 4 sea igual a 2¹ × 38 × 56 × 75 × 116 × 139.» La fórmula correspondiente es:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
donde sss … sss0 representa 2¹ × 38 × 56 × 75 × 116 × 139 copias del símbolo sucesor s. El símbolo ⋅ significa «y», y es la abreviatura de una expresión más larga en el vocabulario fundamental: p ⋅ q significa ~(~p ∨ ~q).
Este artículo fue reproducido en Wired.com.