Teoremas de Incompletitud de Gödel
En este segundo artículo tomaremos los temas expuestos en la publicación anterior y nos detendremos en la demostración como tal de los Teoremas de Incompletitud de Gödel, uno de los logros matemáticos más importantes del siglo XX.
Recapitulación: recursión y gödelización
En el artículo previo introdujimos los conceptos de recursión y de gödelización. El primero posee una importancia fundamental para la posterior Teoría de la Computación, que todavía no existía como disciplina independiente en 1931, pues permite describir formalmente determinadas operaciones mecánicas y efectivas.
Las funciones recursivas primitivas se encuentran estrechamente relacionadas con los procedimientos finitistas empleados por la escuela de Hilbert. Sin embargo, no deben identificarse sin más con la totalidad del finitismo hilbertiano, cuya delimitación exacta constituye una cuestión histórica y filosófica más compleja. El Programa de Hilbert buscaba demostrar la consistencia de la Aritmética y de otras teorías matemáticas recurriendo exclusivamente a métodos elementales y seguros.
El segundo concepto, la gödelización, es la clave del argumento de Gödel, pues constituye la herramienta que permite levantar un reflejo numérico del sistema formal estudiado. Los símbolos, las fórmulas y las demostraciones pasan a estar representados mediante números naturales.
La combinación de ambas herramientas permitirá traducir ciertas afirmaciones metamatemáticas —afirmaciones acerca de fórmulas y demostraciones— en relaciones aritméticas formulables dentro del propio sistema.
Teoremas de Incompletitud y Metamatemática
Los Teoremas de Incompletitud no aparecen simplemente al construir una oración autorreferente. Su demostración depende de que el sistema formal sea capaz de representar mediante fórmulas aritméticas propiedades como «ser una fórmula», «ser una demostración correcta» o «ser una fórmula demostrable».
Gödel logra así que una teoría aritmética hable indirectamente acerca de sus propias expresiones. La metamatemática, que en el Programa de Hilbert estudiaba los sistemas formales desde el exterior, queda parcialmente representada dentro de la propia Aritmética.
Sistema formal
El sistema formal del que parte Gödel, al que denomina \(P\), se basa en la teoría de tipos de los Principia Mathematica de Russell y Whitehead, enriquecida con axiomas y recursos suficientes para desarrollar la Aritmética de los números naturales.
No se trata simplemente de los Principia Mathematica sin modificación. Gödel define un sistema concreto que combina una jerarquía de tipos con axiomas aritméticos semejantes a los de Peano. Dentro de él pueden representarse los números naturales, sus operaciones fundamentales y las relaciones aritméticas necesarias para la demostración.
Esto es muy importante, puesto que los Teoremas de Incompletitud se aplican a sistemas formalizados que contienen suficientes recursos para expresar una parte elemental de la Aritmética. Como hemos visto desde Frege, la fundamentación de los números es un asunto mucho más complejo de lo que podría parecer inicialmente.
La demostración no queda restringida al sistema \(P\). Se extiende a cualquier teoría que cumpla ciertas condiciones: debe estar axiomatizada de manera efectiva, ser capaz de representar las relaciones recursivas primitivas relevantes y contener una cantidad suficiente de Aritmética elemental.
Esto incluye, entre otros sistemas, la Aritmética de Peano y teorías más potentes como la Teoría de Conjuntos de Zermelo-Fraenkel, que puede interpretar la Aritmética dentro de su propio lenguaje.
Propiedades recursivas
Los números de Gödel designan símbolos, fórmulas y secuencias de fórmulas. Denotaremos mediante expresiones como \(r(x_{1},x_{2},\ldots,x_{n})\) las relaciones aritméticas entre estos números que reflejan propiedades sintácticas del sistema formal.
Así, por ejemplo, un número \(x\) designa una variable del sistema formal de tipo \(n\) —donde «tipo» posee el sentido dado en la Teoría de Tipos de Russell— cuando existe un número primo \(p\), mayor que \(13\), tal que \(x=p^{n}\):
$$\operatorname{Var}_{n}(x)\leftrightarrow\exists p\left[p>13\land\operatorname{Primo}(p)\land x=p^{n}\right]$$
Esta propiedad está definida aritméticamente. Para comprobarla basta con examinar un número finito de posibles divisores y verificar si \(x\) es una potencia de un primo mayor que \(13\). Su interpretación metamatemática es: «\(x\) es el Número de Gödel correspondiente a una variable de tipo \(n\)».
Por ejemplo:
$$17=17^{1}$$
Por tanto:
$$\operatorname{Var}_{1}(17)$$
El número \(17\) puede interpretarse así como el código de una variable individual o de primer tipo.
Gödelizar secuencias
La gödelización no solo nos permite crear un reflejo aritmético de cada símbolo y cada fórmula, sino también representar propiedades generales acerca de secuencias de fórmulas. Esto nos permite definir relaciones como «\(x\) es el Número de Gödel de una demostración cuya última fórmula posee el Número de Gödel \(y\)» o «\(z\) es el resultado de sustituir en una fórmula la variable \(x\) por cierto numeral».
Estos enunciados entrecomillados son interpretaciones metamatemáticas. Las relaciones como tales se definen mediante propiedades aritméticas de los números.
Denotaremos mediante:
$$\operatorname{Prf}_{P}(x,y)$$
la relación «\(x\) es el Número de Gödel de una demostración válida en \(P\) cuya fórmula final posee el Número de Gödel \(y\)».
Esta relación es recursiva primitiva en el sistema de Gödel. Dado un número concreto \(x\), podemos comprobar en un número finito de pasos si codifica una secuencia de fórmulas, si cada fórmula es un axioma o se obtiene mediante una regla permitida y si la última de ellas posee el código \(y\).
No basta con factorizar \(x\): tras recuperar la secuencia codificada es necesario verificar la corrección de cada uno de sus pasos. Pero todo este procedimiento puede realizarse de manera efectiva.
Algunas definiciones recursivas representan operaciones de concatenación. Por ejemplo, una función \(\operatorname{Neg}(x)\) puede devolver el Número de Gödel de la fórmula obtenida al añadir el símbolo \(\neg\) delante de la fórmula codificada por \(x\).
Metamatemática
En resumen, la gödelización nos permite transformar fórmulas y secuencias de fórmulas en números, mientras que la recursión nos permite definir relaciones y operaciones aritméticas decidibles entre esos números que pueden interpretarse como relaciones y operaciones sintácticas.
La demostración de los Teoremas de Incompletitud depende de numerosas relaciones de esta clase. Muchas de ellas son complejas y técnicamente tediosas, por lo que no las desarrollaremos aquí. El ejemplo de las variables y la relación de prueba resultan suficientes para comprender el procedimiento general.
Para una fórmula cualquiera \(A\), utilizaremos \(\ulcorner A\urcorner\) para designar externamente su Número de Gödel. El numeral que representa dicho número dentro del sistema será:
$$\overline{\ulcorner A\urcorner}$$
Este numeral es una expresión del lenguaje aritmético formada mediante el símbolo \(0\) y la aplicación reiterada de la función sucesor:
$$s(s(s(\ldots s(0)\ldots)))$$
Conviene distinguir el Número de Gödel, que es un número natural considerado desde la metamatemática, del numeral mediante el que ese número aparece representado dentro del sistema.
Primero de los Teoremas de Incompletitud
La demostración del Primer Teorema de Incompletitud implica la construcción de una sentencia que, bajo su interpretación metamatemática, afirma su propia indemostrabilidad.
No se trata de una fórmula carente de significado ni de una paradoja semejante a la Paradoja de Russell. Se trata de una sentencia aritmética bien formada que establece cierta propiedad de números naturales y que, gracias a la gödelización, puede interpretarse también como una afirmación acerca de su propia demostrabilidad.
Consistencia y completitud
Para comprender la formulación original de Gödel debemos distinguir entre consistencia y \(\omega\)-consistencia.
Un sistema \(P\) es consistente cuando no existe ninguna sentencia \(A\) tal que sean demostrables simultáneamente \(A\) y \(\neg A\).
La \(\omega\)-consistencia exige algo más. No puede existir una fórmula \(A(x)\) tal que el sistema demuestre individualmente:
$$A(0),\quad A(1),\quad A(2),\quad\ldots$$
para cada numeral concreto y, al mismo tiempo, demuestre:
$$\neg\forall x\,A(x)$$
De manera equivalente, no puede demostrar \(\exists x\,B(x)\) mientras demuestra \(\neg B(n)\) para cada numeral concreto \(n\).
Todo sistema \(\omega\)-consistente es consistente, pero un sistema consistente no tiene por qué ser \(\omega\)-consistente.
En cuanto a la completitud, un sistema es sintácticamente completo cuando, para cada sentencia cerrada \(A\) formulable en él, puede demostrar \(A\) o puede demostrar \(\neg A\).
Un sistema inconsistente demuestra todas las sentencias y es, en ese sentido trivial, completo. Por tanto, la propiedad relevante es la completitud de un sistema consistente.
Recursividad y demostración
Antes de presentar el Primer Teorema, Gödel demuestra un resultado fundamental, conocido como Proposición V de su artículo: toda relación recursiva puede ser representada mediante una fórmula del sistema \(P\).
Esto significa que, dada una relación recursiva \(R(x_{1},\ldots,x_{n})\), existe una fórmula \(\mathcal{R}(x_{1},\ldots,x_{n})\) tal que, para cada combinación concreta de números naturales:
- si \(R(n_{1},\ldots,n_{n})\) es verdadera, el sistema demuestra \(\mathcal{R}(\overline{n_{1}},\ldots,\overline{n_{n}})\);
- si \(R(n_{1},\ldots,n_{n})\) es falsa, el sistema demuestra \(\neg\mathcal{R}(\overline{n_{1}},\ldots,\overline{n_{n}})\).
Así, la relación aritmética \(\operatorname{Prf}_{P}(x,y)\) puede ser representada dentro de \(P\) mediante una fórmula que expresa que un número codifica una demostración de la fórmula codificada por otro número.
A partir de esta relación definimos el predicado de demostrabilidad:
$$\operatorname{Prov}_{P}(y)\equiv\exists x\,\operatorname{Prf}_{P}(x,y)$$
\(\operatorname{Prov}_{P}(y)\) significa que existe algún número que codifica una demostración en \(P\) de la fórmula cuyo Número de Gödel es \(y\).
Comprobar si un número concreto codifica una prueba concreta es un procedimiento decidible. Determinar si existe alguna prueba entre una cantidad ilimitada de posibles secuencias no es, en general, un problema decidible.
Enunciado del primer teorema
En su formulación original, el Primer Teorema de Incompletitud afirma que, si el sistema \(P\) es \(\omega\)-consistente, existe una sentencia \(G\) tal que ni \(G\) ni \(\neg G\) son demostrables en \(P\).
El resultado se extiende a otros sistemas formalizados cuyos axiomas sean reconocibles de manera efectiva y que posean suficientes recursos para representar la Aritmética elemental.
La formulación moderna es más fuerte: todo sistema consistente, efectivamente axiomatizado y suficientemente expresivo para desarrollar una parte elemental de la Aritmética es incompleto. Esta mejora se debe a J. Barkley Rosser, quien en 1936 eliminó la necesidad de presuponer \(\omega\)-consistencia.
Autorreferencia
La construcción de la sentencia \(G\) se apoya en un procedimiento de diagonalización. Supongamos una fórmula \(A(x)\) que contiene una única variable numérica libre \(x\). La sustitución permite introducir en ella el numeral correspondiente al Número de Gödel de otra fórmula.
No basta, sin embargo, con escribir directamente \(A(\ulcorner A\urcorner)\). El Número de Gödel es un objeto metamatemático, mientras que la fórmula debe contener su numeral. Además, necesitamos construir una fórmula que reciba exactamente su propio código.
El procedimiento se recoge actualmente en el Lema Diagonal: para cualquier fórmula \(A(x)\) con una variable libre existe una sentencia \(G\) tal que el sistema demuestra:
$$G\leftrightarrow A\left(\overline{\ulcorner G\urcorner}\right)$$
La sentencia \(G\) constituye un punto fijo de la propiedad expresada por \(A\): afirma de sí misma aquello que \(A\) afirma del Número de Gödel que recibe como argumento.
Expresar la demostrabilidad
Aplicamos ahora el Lema Diagonal a la propiedad:
$$A(x)\equiv\neg\operatorname{Prov}_{P}(x)$$
Esta fórmula afirma que la expresión cuyo Número de Gödel es \(x\) no es demostrable en \(P\).
El Lema Diagonal garantiza entonces la existencia de una sentencia \(G\) para la cual \(P\) demuestra:
$$G\leftrightarrow\neg\operatorname{Prov}_{P}\left(\overline{\ulcorner G\urcorner}\right)$$
Bajo su interpretación metamatemática, \(G\) afirma:
«La sentencia \(G\) no es demostrable en \(P\)».
Esta no es una traducción literal de sus signos aritméticos, sino la interpretación que adquieren gracias a la representación de la relación de demostrabilidad.
Epiménides y los Teoremas de Incompletitud
Hemos visto a lo largo de esta serie algunas de las paradojas más famosas. Probablemente la más reconocible sea la Paradoja de Epiménides, que suele parafrasearse mediante la oración «esta oración es falsa».
La construcción de Gödel guarda una semejanza superficial con ella, pues ambas expresiones parecen hablar de sí mismas. Pero existe una diferencia fundamental. La oración del mentiroso afirma su propia falsedad y conduce a una contradicción semántica. La sentencia de Gödel afirma su propia indemostrabilidad dentro de un sistema formal concreto.
La sentencia \(G\) no dice «soy falsa», sino «no existe en \(P\) una secuencia de fórmulas que constituya una demostración de mí».
Por ello no se produce una paradoja. La posibilidad coherente es que \(G\) sea verdadera respecto de los números naturales y, sin embargo, no sea demostrable en \(P\).
La demostración
Supongamos en primer lugar que \(P\) demuestra \(G\). Entonces existe una demostración concreta de \(G\), cuyo Número de Gödel podemos denotar mediante \(n\):
$$\operatorname{Prf}_{P}\left(\overline{n},\overline{\ulcorner G\urcorner}\right)$$
Como la relación de prueba está correctamente representada dentro del sistema, \(P\) puede demostrar que \(n\) codifica una prueba de \(G\). Por tanto, puede demostrar:
$$\operatorname{Prov}_{P}\left(\overline{\ulcorner G\urcorner}\right)$$
Pero \(G\) afirma precisamente lo contrario:
$$\neg\operatorname{Prov}_{P}\left(\overline{\ulcorner G\urcorner}\right)$$
Si \(P\) demostrara \(G\), demostraría tanto la existencia como la inexistencia de una prueba de \(G\). El sistema sería inconsistente.
Por tanto, si \(P\) es consistente:
$$P\nvdash G$$
Consideremos ahora la posibilidad de que \(P\) demuestre \(\neg G\). A partir de la equivalencia construida mediante diagonalización, esto equivale a demostrar:
$$\operatorname{Prov}_{P}\left(\overline{\ulcorner G\urcorner}\right)$$
Es decir:
$$\exists x\,\operatorname{Prf}_{P}\left(x,\overline{\ulcorner G\urcorner}\right)$$
Sin embargo, por la consistencia de \(P\), sabemos desde la metamatemática que ningún número natural concreto codifica una demostración de \(G\). Para cada numeral \(\overline{n}\), el sistema puede comprobar:
$$\neg\operatorname{Prf}_{P}\left(\overline{n},\overline{\ulcorner G\urcorner}\right)$$
El sistema estaría demostrando que ninguno de los numerales concretos representa una prueba de \(G\), mientras afirmaría al mismo tiempo que existe algún número que representa una prueba de \(G\). Esto constituye precisamente una forma de \(\omega\)-inconsistencia.
Por tanto, si \(P\) es \(\omega\)-consistente:
$$P\nvdash\neg G$$
Concluimos que, bajo la condición original de \(\omega\)-consistencia, ni \(G\) ni su negación son demostrables en \(P\).
Consecuencias
La demostración original de Gödel emplea dos supuestos diferentes. La consistencia ordinaria basta para demostrar que \(G\) no es demostrable. La condición más fuerte de \(\omega\)-consistencia permite concluir además que \(\neg G\) tampoco es demostrable.
Rosser modificaría posteriormente la construcción de la sentencia autorreferente para demostrar que la consistencia ordinaria basta para obtener una sentencia indecidible.
La conclusión moderna del Primer Teorema puede expresarse así: todo sistema formal consistente, efectivamente axiomatizado y suficientemente potente para representar la Aritmética elemental contiene sentencias que no puede demostrar ni refutar.
La palabra indecidible se utiliza aquí en relación con una teoría concreta: ni la sentencia ni su negación son teoremas del sistema. No significa necesariamente que ninguna teoría más fuerte pueda resolverla ni que la mente humana sea incapaz de comprenderla.
Si \(P\) es consistente, la sentencia \(G\) es verdadera en la interpretación habitual de los números naturales. Afirma que no existe una demostración de \(G\) en \(P\), y la argumentación metamatemática acaba de establecer precisamente que tal demostración no existe.
Segundo de los Teoremas de Incompletitud
El Segundo Teorema de Incompletitud se apoya en el resultado anterior, pero no es simplemente una repetición de este. Es necesario formalizar dentro del propio sistema una parte suficiente de la argumentación metamatemática utilizada para construir \(G\).
El sistema puede representar su relación de demostrabilidad y expresar mediante una sentencia aritmética que no existe una demostración de una contradicción.
Enunciado del segundo teorema
Sea \(P\) un sistema consistente, efectivamente axiomatizado y suficientemente potente para representar la Aritmética elemental. El Segundo Teorema de Incompletitud afirma que \(P\) no puede demostrar su propia consistencia, expresada mediante la formulación aritmética habitual.
Podemos representar la consistencia de \(P\) mediante la sentencia:
$$\operatorname{Con}(P)\equiv\neg\operatorname{Prov}_{P}\left(\overline{\ulcorner 0=1\urcorner}\right)$$
Esta expresión afirma que no existe ningún número que codifique una demostración en \(P\) de la contradicción \(0=1\).
El teorema establece:
$$P\nvdash\operatorname{Con}(P)$$
siempre que \(P\) sea efectivamente consistente y satisfaga las condiciones técnicas necesarias para representar correctamente su predicado de demostrabilidad.
Demostración del segundo teorema
La argumentación utilizada para demostrar que \(G\) es indemostrable puede formalizarse parcialmente dentro del propio sistema. \(P\) puede demostrar que, si no existe una prueba de una contradicción, entonces no existe una prueba de \(G\):
$$P\vdash\operatorname{Con}(P)\rightarrow G$$
La intuición es la siguiente: si \(G\) fuera demostrable, también lo sería la afirmación de que \(G\) es demostrable; pero \(G\) afirma que no lo es. De una prueba de \(G\) podría obtenerse una contradicción.
Supongamos ahora que \(P\) pudiera demostrar su propia consistencia:
$$P\vdash\operatorname{Con}(P)$$
Como el sistema demuestra también \(\operatorname{Con}(P)\rightarrow G\), mediante modus ponens obtendríamos:
$$P\vdash G$$
Pero el Primer Teorema establece que, si \(P\) es consistente, \(G\) no puede ser demostrable. Por tanto, un sistema consistente no puede demostrar su propia consistencia.
Conclusión del segundo teorema
El teorema no afirma que sea imposible demostrar la consistencia de un sistema. Impide que un sistema suficientemente potente demuestre su propia consistencia mediante su formulación aritmética habitual, suponiendo que el sistema sea realmente consistente.
Una teoría más fuerte \(P^{+}\) puede demostrar la consistencia de una teoría más débil \(P\). Pero, si \(P^{+}\) reúne las condiciones de los Teoremas de Incompletitud, no podrá demostrar su propia consistencia:
$$P^{+}\nvdash\operatorname{Con}(P^{+})$$
Podemos construir sucesivamente teorías cada vez más fuertes añadiendo principios de consistencia, pero cada nuevo sistema planteará una nueva cuestión acerca de la legitimidad de sus propios axiomas.
Esto no conduce a una contradicción ni demuestra que toda justificación matemática sea imposible. Muestra que no puede existir, bajo las condiciones del teorema, una justificación interna y definitiva de todo el sistema mediante los mismos recursos que ese sistema pretende legitimar.
Conclusión de los Teoremas de Incompletitud
La publicación de los Teoremas de Incompletitud no dejó a nadie indiferente, aunque las opiniones acerca de sus consecuencias variaron según cada autor. John von Neumann comprendió rápidamente que los resultados imponían una limitación decisiva al Programa de Hilbert.
El propio Gödel fue inicialmente menos concluyente. Sus teoremas no demostraban por sí solos que ninguna forma revisada del programa formalista pudiera sobrevivir. La exigencia original de Hilbert consistía en ofrecer una demostración finitista de la consistencia de la Aritmética. El Segundo Teorema establecía que una demostración de la consistencia de la Aritmética no podía formalizarse completamente dentro de la propia teoría, suponiendo que esta fuera consistente.
La cuestión decisiva era entonces si los métodos finitistas aceptados por Hilbert podían representarse dentro del sistema aritmético estudiado. Si así fuera, la demostración finitista esperada quedaría excluida por el Segundo Teorema. Esta es la interpretación que terminó imponiéndose respecto del programa original.
Unos años después, Gerhard Gentzen presentó una demostración de la consistencia de la Aritmética de Peano. Su demostración utilizaba inducción transfinita hasta el ordinal \(\varepsilon_{0}\), un principio que excedía los métodos finitistas estrictos que Hilbert había esperado emplear.
El resultado de Gentzen no contradice el Segundo Teorema: la demostración recurre a recursos que no pueden ser formalizados íntegramente dentro de la Aritmética de Peano cuya consistencia pretende establecer.
El programa original de Hilbert no pudo completarse en los términos previstos. Sin embargo, la Teoría de la Prueba no desapareció. Se transformó en un campo dedicado a comparar la fuerza de los sistemas formales, estudiar qué principios son necesarios para demostrar su consistencia y analizar las diferentes formas de razonamiento matemático.
Consecuencias filosóficas de los Teoremas de Incompletitud
Respecto al impacto filosófico de estos teoremas, el propio Gödel era muy aficionado a la filosofía y gran parte de sus escritos trata esta temática. El asunto es tan vasto que no lo desarrollaremos aquí. Dejaremos simplemente una reflexión del propio Gödel, realizada varias décadas después de la publicación de los Teoremas de Incompletitud.
– Mis teoremas sólo muestran que la mecanización de las matemáticas, es decir, la eliminación de la mente y de las entidades abstractas, es imposible, si uno quiere tener una base y un sistema de matemáticas satisfactorios. No he probado que haya cuestiones matemáticas indecidibles para la mente humana, sino sólo que no hay máquina (o formalismo ciego) que pueda decidir todas las cuestiones teóricas de números (incluso de un tipo muy especial). Del mismo modo, de mis teoremas no se sigue que no haya pruebas de consistencia convincentes para los formalismos matemáticos usuales, a pesar de que tales pruebas deben usar modos de razonamiento no contenidos en esos formalismos.
Lo que es prácticamente seguro es que para los formalismos clásicos no hay pruebas combinatorias de consistencia concluyentes (como las que esperaba dar Hilbert), es decir, no hay pruebas de consistencia que utilicen sólo conceptos que se refieran a combinaciones finitas de símbolos y que no se refieran a ninguna totalidad infinita de tales símbolos. –
– Kurt Gödel. Carta a Leon Rappaport (1962).
Los Teoremas de Incompletitud no demuestran que la mente humana sea superior a toda máquina ni que existan verdades que ningún ser humano pueda conocer. Tampoco afirman que todas las teorías matemáticas sean incompletas. Se aplican a sistemas efectivamente axiomatizados, consistentes y suficientemente potentes para representar la Aritmética.
Su enseñanza fundamental es más precisa: ningún sistema formal de esas características puede reunir simultáneamente la consistencia, la completitud y la capacidad de demostrar mediante sus propios recursos su consistencia.
La formalización permite convertir las demostraciones en objetos matemáticos y someterlas a un análisis exacto. Pero ese mismo análisis revela que todo sistema suficientemente expresivo encuentra límites que no puede superar desde su interior.
Lecturas recomendadas
– Gödel, K. (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.
– Gödel, K. (2006). Obras completas. Edición de Jesús Mosterín.
– Nagel, E. y Newman, J. R. (1958). Gödel’s Proof.
– Smullyan, R. M. (1992). Gödel’s Incompleteness Theorems.
