Los teoremas de incompletitud de Gödel

Los teoremas de incompletitud de Kurt Gödel, publicados en 1931, establecen dos límites a lo que cualquier sistema formal puede hacer con la aritmética. El primero dice que en todo sistema consistente, con axiomas reconocibles por un procedimiento mecánico y con fuerza suficiente para expresar la aritmética elemental, existen enunciados verdaderos sobre los números que el sistema no puede demostrar ni refutar. El segundo dice que entre esos enunciados indemostrables está precisamente el que afirma la consistencia del propio sistema. Fueron el golpe más duro que ha recibido un programa de investigación en matemáticas, y su autor tenía veinticinco años.

Lo que estaba en juego era el programa de David Hilbert. Tras un siglo de sustos, los infinitesimales sin fundamento, las geometrías no euclídeas, las paradojas de la teoría de conjuntos, Hilbert había propuesto poner la casa en orden de una vez. Su plan tenía tres piezas: axiomatizar toda la matemática, demostrar que el sistema resultante es completo, es decir que decide toda afirmación bien formada, y demostrar que es consistente, es decir que nunca deduce una cosa y su contraria. Esa última demostración debía hacerse solo con razonamientos finitarios y elementales que nadie pudiera poner en duda. En 1930, en un congreso en Königsberg, Hilbert pronunció su célebre «debemos saber, sabremos». El día anterior, en una mesa redonda del mismo congreso, Gödel había anunciado de pasada su primer teorema, y casi nadie reparó en ello.

La demostración tiene tres piezas. La primera es la aritmetización de la sintaxis, hoy llamada numeración de Gödel: a cada símbolo, cada fórmula y cada demostración del sistema se le asigna un número natural de forma sistemática, de modo que preguntas sobre fórmulas se convierten en preguntas sobre números. La segunda es mostrar que la relación «la demostración con número $m$ demuestra la fórmula con número $n$» es ella misma expresable dentro del sistema, porque es una relación puramente mecánica sobre dígitos. La tercera es la construcción diagonal. Con las dos piezas anteriores se puede escribir una fórmula aritmética que, leída a través de la numeración, dice de sí misma que no es demostrable. Si el sistema la demostrara, demostraría algo falso y sería inconsistente. Si el sistema demostrara su negación, también habría problema. Luego, si el sistema es consistente, ni ella ni su negación son demostrables, y ella además es verdadera, porque dice exactamente lo que ocurre.

De ahí sale el segundo teorema casi de regalo. El razonamiento anterior, que parte de la consistencia del sistema y concluye que la fórmula no es demostrable, puede formalizarse dentro del propio sistema. Si el sistema pudiera demostrar su consistencia, encadenando esa demostración con la formalización obtendría la fórmula indecidible, lo cual es imposible. Un sistema solo puede demostrar su propia consistencia si no la tiene. Esto cerró el programa de Hilbert en su forma original. No cerró la teoría de la demostración: Gerhard Gentzen probó en 1936 la consistencia de la aritmética usando inducción transfinita hasta el ordinal $\varepsilon_0$, un recurso más fuerte que los finitarios que Hilbert quería, pero perfectamente legítimo.

El enunciado de Gödel es confesadamente artificial, y durante décadas pudo pensarse que la incompletitud afectaba solo a frases autorreferentes que a nadie le importan. Eso dejó de ser cierto en 1977, cuando Jeff Paris y Leo Harrington encontraron una variante finita del teorema de Ramsey, un enunciado combinatorio natural, que es verdadera y no demostrable en la aritmética de Peano. Poco después Laurie Kirby y Paris probaron lo mismo del teorema de Goodstein, que trata de unas sucesiones de enteros que siempre acaban en cero aunque crezcan de forma monstruosa por el camino. Son enunciados que un matemático podría haber formulado sin saber nada de lógica.

Hay un segundo tipo de independencia que suele confundirse con esta. La hipótesis del continuo, que pregunta si hay algún infinito estrictamente entre el de los naturales y el de los reales, tampoco se decide a partir de los axiomas habituales de la teoría de conjuntos: Gödel demostró en 1940 que no se puede refutar y Paul Cohen en 1963 que no se puede demostrar. Eso también es incompletitud, pero no es el teorema de 1931, y nada obliga a que todo enunciado indecidible tenga la forma de la fórmula autorreferente.

Conviene decir qué no dicen los teoremas, porque es donde más se los maltrata. No dicen que haya verdades incognoscibles: la fórmula de Gödel de un sistema se demuestra sin dificultad en un sistema algo más fuerte. No dicen que la matemática sea inconsistente, ni que no se pueda confiar en ella. No dicen nada sobre teorías físicas, sistemas jurídicos, lenguajes naturales ni organizaciones humanas, que no son sistemas formales con aritmética dentro. Y el argumento de John Lucas y Roger Penrose según el cual la mente humana supera a toda máquina, porque nosotros vemos que la fórmula de Gödel es verdadera, se topa con que esa verdad es condicional: lo que se ve es que si el sistema es consistente, la fórmula es verdadera, y de la consistencia de nuestro propio razonamiento no tenemos ninguna garantía privilegiada.

La máquina de Turing – Axioma – Lógica formal – Aquiles y la tortuga