Así funciona el teorema de Gödel

Los teoremas de incompletitud de Kurt Gödel acabaron con la búsqueda de una teoría matemática del todo. Noventa años después, seguimos tratando de entender sus consecuencias.

En 1931, Kurt Gödel demostró que todo sistema matemático contendrá afirmaciones imposibles de demostrar. [OLENA SHMAHALO/QUANTA MAGAZINE]

En  1931, el lógico austriaco Kurt Gödel llevó a cabo el que probablemente podamos calificar como uno de los logros intelectuales más asombrosos de la historia. Por aquel entonces, los matemáticos se habían lanzado a buscar los fundamentos de su disciplina: un conjunto de hechos matemáticos básicos, o axiomas, que fueran al mismo tiempo coherentes (que nunca condujeran a contradicciones) y completos (es decir, a partir de los cuales pudieran construirse todas las verdades matemáticas).

Sus teoremas de incompletitud, publicados cuando contaba solo 25 años, frustraron ese sueño. Gödel demostró que cualquier conjunto de axiomas que podamos postular como base de las matemáticas será irremediablemente incompleto: siempre habrá hechos verdaderos sobre los números que jamás podremos demostrar a partir de esos axiomas. Además, Gödel también probó que ninguno de esos conjuntos de axiomas podría demostrar jamás su propia coherencia.

Los teoremas de incompletitud implican que no puede existir una teoría matemática del todo; ninguna unificación de lo que es demostrable y lo que es cierto. Lo que los matemáticos puedan demostrar dependerá siempre de los supuestos de los que partan, no de una verdad fundamental a partir de la cual emanen todas las respuestas.

En los noventa años transcurridos desde el hallazgo de Gödel, los matemáticos se han topado con el tipo de preguntas sin respuesta que pronosticaban sus teoremas de incompletitud. Por ejemplo, el propio Gödel contribuyó a establecer que la hipótesis del continuo, relativa a los tamaños del infinito, era indecidible. Lo mismo ocurre con el problema de la parada, o la pregunta de si un programa informático que recibe una entrada aleatoria continuará calculando para siempre o acabará deteniéndose antes o después.

Las cuestiones indecidibles han aparecido incluso en física, lo que parece indicar que la incompletitud de Gödel no solo se circunscribe al mundo de las matemáticas puras, sino que, de algún modo que no acabamos de entender, afectaría también a la propia realidad. Lo que sigue es un resumen simplificado e informal de los argumentos que empleó Gödel para demostrar sus teoremas.

La numeración de Gödel

La estrategia clave de Gödel fue encontrar una manera para expresar las afirmaciones sobre un sistema de axiomas en términos de las afirmaciones contenidas en dicho sistema; esto es, en términos de afirmaciones relativas a los números. Esta correspondencia permite que un sistema de axiomas «hable» sobre sí mismo. Para ello, el primer paso consiste en asignar un número único, denominado «número de Gödel», a cualquier posible enunciado o serie de enunciados matemáticos.

En 1958, Ernest Nagel y James Newman presentaron una versión ligeramente modificada de dicho esquema en su libro El teorema de Gödel. Esta 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 mediante el símbolo $, mientras que la suma se denota mediante +. Un símbolo importante es s, que significa «sucesor de» y ofrece una manera de especificar los números: ss0, por ejemplo, hace referencia al número 2. A estos 12 símbolos se les asignan los números de Gödel del 1 al 12 (véase la tabla adjunta).

Números de Gödel asociados a un conjunto de símbolos básicos empleados para formular enunciados matemáticos.

A continuación, las letras que representan variables, como X, Y o Z, se asocian a los números primos mayores que 12 (13, 17, 19, etcétera). A partir de aquí, es posible asignar un número de Gödel propio a cualquier combinación de símbolos y variables; es decir, a toda fórmula o secuencia de fórmulas aritméticas que podamos construir.

Para verlo, consideremos la fórmula 0 = 0. Los tres símbolos que aparecen en ella tienen asociados los números de Gödel 6, 5 y 6, respectivamente. Ahora hemos de convertir esta secuencia de tres números en uno solo. Este deberá además ser único, en el sentido de que ninguna otra secuencia de símbolos pueda generarlo. Para ello, tomamos los tres primeros números primos (2, 3 y 5), elevamos cada uno de ellos al número de Gödel del símbolo que ocupa la misma posición en la secuencia, y por último los multiplicamos. De esta manera, 0 = 0 se convierte en 26 × 35 × 56, o 243.000.000.

La correspondencia funciona porque dos fórmulas distintas nunca podrán generar el mismo número de Gödel. Todos los números de Gödel son enteros, y solo existe una forma de descomponer un número entero en factores primos. La única descomposición en factores primos de 243.000.000 es 26 × 35 × 56, lo que significa que solo hay una manera posible de descodificar este número de Gödel: la fórmula 0 = 0.

Gödel fue un paso más allá. Dado que una demostración matemática consta de una secuencia ordenada de fórmulas, definió también una manera de asociar un número de Gödel único a cada una de esas secuencias. A tal fin, comenzamos una vez más con la lista de números primos: 2, 3, 5... Luego elevamos cada uno al número de Gödel de la fórmula que ocupa la misma posición en la secuencia (por ejemplo, si 0 = 0 aparece en primer lugar, escribiremos 2243.000.000 × ···), y por último lo multiplicamos todo.

Aritmetizar la metamatemática

La gran ventaja de este procedimiento es que incluso los enunciados metamatemáticos, aquellos que versan sobre las fórmulas aritméticas mismas, pueden traducirse en fórmulas con sus propios números de Gödel.

Empecemos considerando la fórmula ∼(0 = 0), que significa «cero no es igual a cero». Esta fórmula es claramente falsa, pero aun así tiene un número de Gödel: 2 elevado a 1 (el número de Gödel del símbolo ∼), multiplicado por 3 elevado a 8 (el número de Gödel del paréntesis de apertura), etcétera. El proceso nos da como resultado 21 × 38 × 56 × 75 × 116 × 139. Dado que es posible generar números de Gödel para todas las fórmulas, aunque sean falsas, podemos decir cosas sobre ellas a partir de sus respectivos 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) puede traducirse en un enunciado sobre el número de Gödel asociado a la fórmula: a saber, que su primer exponente es 1 (el número de Gödel asociado a la tilde). En otras palabras, nuestra afirmación dice que el número 21 × 38 × 56 × 75 × 116 × 139 solo tiene un factor 2. Si ∼(0 = 0) empezara con cualquier otro símbolo que no fuera una tilde, su número de Gödel tendría al menos dos factores 2. Así que, siendo más precisos, lo que queremos decir es que 2 es un factor de 21 × 38 × 56 × 75 × 116 × 139, pero 22 no lo es.

De igual modo, también podemos convertir la última frase en una expresión aritmética precisa («existe un número entero X tal que X multiplicado por 2 es igual a 21 × 38 × 56 × 75 × 116 × 139, y no existe ningún entero X tal que X multiplicado por 4 sea igual a 21 × 38 × 56 × 75 × 116 × 139») y escribirla mediante símbolos elementales. Y por supuesto, dicha fórmula tendrá también un número de Gödel, el cual podremos calcular transformando sus símbolos en potencias de números primos.

Este ejemplo, escribieron Nagel y Newman, «ilustra una idea muy general y profunda que constituye el núcleo del descubrimiento de Gödel: es posible hablar, de un modo indirecto pero perfectamente preciso, sobre las propiedades tipográficas de una larga cadena de símbolos analizando, en su lugar, las propiedades de la descomposición en factores primos de un número entero grande».

También podemos convertir en símbolos el enunciado metamatemático «existe una secuencia de fórmulas con número de Gödel X que demuestra la fórmula con número de Gödel K». O, de manera más sucinta, «es posible demostrar la fórmula con número de Gödel K». Fue la posibilidad de «aritmetizar» este tipo de enunciados lo que abrió las puertas a los teoremas de incompletitud.

Kurt Gödel durante su época de estudiante en Viena. Gödel publicó sus teoremas de incompletitud cuando contaba 25 años, justo después de finalizar su doctorado. [Centro Documental Shelby White y Leon Levy/Instituto de Estudios Avanzados de Princeton (dominio público)]

G habla sobre G

Fue aquí donde Gödel tuvo una idea brillante. Se percató de que podía tomar el número de Gödel de una fórmula y sustituirlo en la propia fórmula.

Para entender cómo funciona esta sustitución, consideremos la fórmula (∃X)(X = sY), que significa «existe alguna variable X que es el sucesor de Y»; o, en pocas palabras, «Y tiene un sucesor». Como todas las fórmulas, esta posee un número de Gödel: algún número entero grande al que llamaremos M.

Ahora, tomemos la fórmula de partida y sustituyamos el símbolo Y por M. Esto genera una nueva fórmula, (∃X)(X=sM), que significa «M tiene un sucesor». ¿Cómo podemos llamar al número de Gödel de esta expresión? Hay que reflejar tres cosas: hemos empezado con la fórmula que tiene número de Gödel M; en ella, hemos sustituido el símbolo Y por M; y, de acuerdo con el esquema de asignación que hemos introducido al principio, el símbolo Y es el que tiene número de Gödel 17. Así pues, designemos el número de Gödel de la nueva fórmula como sust(M, M, 17). Este tipo de sustitución encierra el quid de la demostración de Gödel.

Gödel consideró un enunciado metamatemático del tipo «la fórmula con número de Gödel sust(Y, Y, 17) no se puede demostrar». De acuerdo con la notación que acabamos de introducir, la fórmula con número de Gödel sust(Y, Y, 17) es la que se obtiene al tomar la fórmula con número de Gödel Y (una variable desconocida) y, en cualquier lugar donde aparezca el símbolo con número de Gödel 17 (es decir, en cualquier lugar donde haya una Y), reemplazarlo por dicha variable Y.

La cosa está empezando a complicarse, pero lo que es seguro es que nuestra afirmación metamatemática «la fórmula con número de Gödel sust(Y, Y, 17) no se puede demostrar» se traduce en una fórmula con un número de Gödel único. Llamémoslo N.

Hagamos ahora una última sustitución: Gödel creó una nueva fórmula insertando el número N en cualquier lugar donde hubiera una Y en la fórmula anterior. Esa nueva fórmula dice «la fórmula con número de Gödel sust(N, N, 17) no se puede demostrar». Llamemos G a esta última fórmula.

Por supuesto, G tiene un número de Gödel. ¿Cuál es? He aquí la sorpresa: dicho número de Gödel solo puede ser sust(N, N, 17). Por definición, sust(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, en cualquier lugar donde haya un símbolo con número de Gödel 17, reemplazarlo por N. ¡Y esa fórmula resultante es justo G! Debido a la unicidad de la descomposición en factores primos, ahora vemos que la fórmula de la que habla G no es sino la propia G. Y G está afirmando sobre sí misma que es indemostrable.

Pero ¿es posible demostrar G? Si así fuera, querría decir que hay alguna secuencia de fórmulas que demuestra la fórmula con número de Gödel sust(N, N, 17). Pero eso es lo contrario de lo que afirma G, que nos asegura que no existe tal demostración. En un sistema coherente de axiomas, no es posible que dos enunciados opuestos, G y ∼G, sean ambos verdaderos. Por tanto, la verdad de G solo puede ser indecidible.

Sin embargo, aunque G sea indecidible, está claro que es cierta. G afirma que «la fórmula con número de Gödel sust(N, N, 17) no se puede demostrar». ¡Y eso es justamente lo que hemos hallado! Dado que G es verdadera pero indecidible dentro del sistema de axiomas que hemos usado para construirla, dicho sistema es necesariamente incompleto.

Cabe pensar que tal vez podríamos postular algún axioma adicional, usarlo para demostrar G y resolver la paradoja. Sin embargo, algo así no es posible. Gödel demostró que, siguiendo un esquema similar al que acabamos de emplear, ese sistema extendido de axiomas permitiría construir una nueva fórmula verdadera, G', la cual no podría demostrarse dentro del nuevo sistema extendido. Así pues, todo intento de obtener un sistema matemático completo será siempre como una pescadilla que se muerde la cola.

El segundo teorema

Hemos visto que, si un conjunto de axiomas es coherente, entonces es incompleto. Este es el primer teorema de Gödel. El segundo —que ningún conjunto de axiomas puede demostrar su propia coherencia— puede deducirse fácilmente a partir de él.

¿Qué significaría que un conjunto de axiomas pudiera demostrar que nunca conduce a una contradicción? Querría decir que existe una secuencia de fórmulas construida a partir de esos axiomas que demuestra la fórmula que, desde un punto de vista metamatemático, dice «este conjunto de axiomas es coherente». Por el primer teorema, ese conjunto de axiomas sería entonces necesariamente incompleto.

Pero «el conjunto de axiomas es incompleto» es lo mismo que decir «existe alguna fórmula verdadera que no se puede demostrar». Esta afirmación es equivalente a nuestra fórmula G. Y sabemos que los axiomas no pueden demostrar G.

Así que Gödel construyó una demostración por contradicción: si un conjunto de axiomas pudiera demostrar su propia coherencia, entonces seríamos capaces de demostrar G. Pero no podemos, de modo que ningún conjunto de axiomas puede demostrar su propia coherencia.

Los teoremas de Gödel acabaron con la búsqueda de un sistema matemático coherente y completo. El significado de la incompletitud «sigue sin comprenderse del todo», escribieron Nagel y Newman en 1958. Hoy en día, eso continúa siendo cierto.

 

Este artículo apareció originalmente en QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión pública de la ciencia.

Puedes obtener el artículo en...

Los boletines de Investigación y Ciencia

Elige qué contenidos quieres recibir.