Los Teoremas de Incompletitud de Gödel
David Baños Abril
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.
Recopilación de los trabajos de Gödel
En el artículo previo introdujimos los conceptos de recursión y de gödelización. El primero es de una importancia fundamental en la posterior Teoría de la Computación (que no existía aún en 1931), dado que describe formalmente lo que intuitivamente entendemos por operar mecánicamente. Además, la recursión primitiva es la formalización de lo que Hilbert denominó en su día razonamiento finitista, el cual debe realizarse en un número finito de pasos y no involucrar razonamientos sobre cantidades infinitas de objetos. El programa de Hilbert buscaba la demostración de las bases de la Aritmética aplicando única y exclusivamente métodos finitistas.
El segundo concepto de gödelización es la clave del argumento de Gödel, pues es la herramienta que nos permite levantar un reflejo numérico del sistema formal evaluado.
Teoremas de Incompletitud y Metamatemática
Sistema formal
El sistema formal desde el que partimos, que Gödel denomina P, no supone ninguna novedad: se trata de los Principia Mathematica de Russell y Whitehead. Recordemos que los Principia no solo son una formalización de la Lógica de Segundo Orden, sino que contiene un conjunto de axiomas que permiten la deducción de los fundamentos de la Aritmética -es posible dentro del sistema demostrar los números naturales-. Esto es muy importante, puesto que los Teoremas de Incompletitud refieren a todo sistema formal que contenga los recursos suficientes para permitir el fundamento de la Aritmética. Ya hemos visto desde Frege que la fundamentación de los números es un asunto mucho más complejo de lo que podría aparecer).
Gödel combina los axiomas de los Principia con los Axiomas de Peano. Toda la demostración de los Teoremas de Incompletitud es aplicable a cualquier sistema que permita decidir la veracidad de una relación definida de forma recursiva primitiva, es decir, en un número finito de pasos. Esto incluye también la Teoría de Conjuntos de Zermel-Fraenkel.
Propiedades recursivas
Los Números de Gödel designan símbolos y fórmulas. Denotemos con letras minúsculas de la forma f(x_{1}, x_{2}….x_{n}) a las propiedades de los números que reflejan entidades lógicas.
Así, por ejemplo, un número x designa una variable del sistema formal de tipo 1 (aquí «tipo» tiene la connotación dada en la Teoría de Tipos de Russell; tipo 1 variables sobre individuos, 2 variables sobre clases de individuos, etc…) si se cumple que:
Esta propiedad var_{1}(x) está definida recursivamente, lo que quiere decir que es posible chequear uno a uno todos los números z menores que x y comprobar, en un número finito de pasos si tal propiedad se cumple para x. Tal propiedad, aun siendo definida haciendo uso de propiedades aritméticas, podemos interpretarla metamatemáticamente como «x es una variable», o, más precisamente, «x es el Número de Gödel que designa una variable».
Siguiendo esto un número como x= 17= 17^{1} designa una variable de tipo 1 .
Gödelizar secuencias
La gödelización no solo nos permite crear un espejo aritmético de cada símbolo y cada fórmula, sino también representar metateoremas generales acerca del secuencias de fórmulas. Esto nos permite crear propiedades como por ejemplo «x es una fórmula demostrada en y» o «a es la fórmula que cuantifica la variable x en y«. Estos enunciados entrecomillados son realmente interpretaciones dadas a posteriori, dado que, como hemos dicho, las propiedades como tal se declaran como relaciones aritméticas entre números.
Es por ello que «x es una fórmula demostrada en y» (dem(x,y)) representa una relación lógica en el sistema P que será cierta sí y solo sí existe una determinada proporción entre el número x y el número y, una que es perfectamente comprobable en un número finito de pasos con tan solo factorizar y.
Algunas de estas definiciones recursivas son operaciones de concatenación. Por ejemplo, la función neg(x) devuelve el Número de Gödel de la fórmula que designa x después de que se le ha añadido al inicio el símbolo ¬.
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 da la posibilidad de definir relaciones y operaciones aritméticas entre esos números que son decidibles y que pueden ser interpretadas como relaciones y operaciones lógicas. La demostración de los Teoremas de Incompletitud de Gödel depende de estas propiedades. Muchas de ellas son complejas y algo tediosas así que nosotros no nos pararemos aquí. Baste el ejemplo sencillo de definición de variable que hemos indicado arriba.
Para una fórmula cualquiera A, \left [ A \right ] indica su numeral, es decir, su número de Gödel expresado dentro del sistema formal en forma de secuencia de la forma s(s(s….s(0))). En este artículo utilizaremos letras minúsculas para designar variables numéricas, tanto las que se encuentran en los conceptos metamatemáticos como las de las fórmulas del propio sistema P, las cuales son sustituibles por numerales.
Primero de los Teoremas de Incompletitud
La demostración del Primer Teorema de Incompletitud (el Segundo sería tan solo un corolario de este) implica la construcción de una sentencia recurriendo a estos conceptos metamatemáticos. Mostraremos como podemos definir una relación aritmética que puede ser interpretada como una expresión lógica pero que no es decidible en el sistema formal P.
Consistencia y completitud
Gödel expone la propiedad metamatemática de consistencia de una forma más estricta que la que hemos manejado previamente, una que ha venido a denominarse ω-consistencia. Afirma que para cada propiedad A no puede darse el caso que A(x) es deducible para todo número natural x al mismo tiempo que es deducible ¬∀x(A(x)). Los sistemas formales ω-consistentes son consistentes en el sentido tradicional, pero no a la inversa. La ω-consistencia por tanto introduce una limitación que solo sale a la luz cuando se extiende a proposiciones infinitas.
En cuanto a la completitud esta se define como un sistema, para el cual, toda fórmula bien formada A, o bien A o no ¬A son demostrables. Recordemos que todo sistema inconsistente es completo, por lo tanto solo tiene sentido intentar demostrar la completitud en un sistema consistente. La consistencia es una metapropiedad que limita las fórmulas que puedan ser demostradas.
Recursividad y demostración
Antes de pasar al enunciado del Primer Teorema (Teorema VI en el artículo original), Gödel añade un proposición fundamental, la Proposición V: a toda propiedad recursivamente definida le corresponde el Número de Gödel de una expresión que o bien es «z es demostrable» si la relación es cierta, o «¬z es demostrable» si no es el caso. z es el Número de Gödel de una fórmula Z que se encontraría por tanto demostrada en el sistema formal. Esta proposición enlaza las definiciones recursivas con el sistema formal, confirmando que sistema formal P.
Enunciado del primer teorema
Enunciamos el Primer Teorema de Incompletitud tal y como lo indica Gödel: dado un conjunto de fórmulas definidas de forma recursiva que sean ω-consistentes entre sí, existe una formula A, tal que ni A ni ¬A pueden ser inferidas a partir de dichas fórmulas.
Gödel generaliza no solo al sistema P de los Principia, sino a cualquier conjunto de fórmulas que cumplan tales características. Esto significa que ningún sistema de axiomas consistentes y recursivamente definidos se libra de la incompletitud.
Autorreferencia
Expongamos ahora la demostración. Pongamos una fórmula cualquiera A(x), la cual acoge una sola variable numérica libre x (Gödel las denomina «signo de clase»). Aquí la variable x es un número. A misma es una fórmula traducible a la numeración de Gödel así que es perfectamente posible construir la fórmula autorreferente A(\left [ A \right ]).
Aquí simplemente aplicamos una operación de sustitución del Número de Gödel de la variable libre en A por el Número de Gödel de la fórmula A(x). Esta operación de sustitución es una de las propiedades metamatemáticas que expusimos antes.
Expresar la demostrabilidad
Otro de los conceptos metamatemáticos que nos interesa es «x es una fórmula demostrada en y» que hemos visto antes y que denotamos dem(x,y) (x B y en la notación original, de Beweis, o «prueba» en alemán).
Combinando ambos podemos definir una nueva propiedad, «y autorreferente no es demostrable en x» que llamaremos q(x,y). Tal propiedad, definida desde las recursivas de negación, autorreferencia y demostrabilidad, es igualmente recursivamente primitiva y por la proposición V, existe una fórmula deducible en el sistema formal P. Tal fórmula es Q(x,y) con dos variables libres y, como no, esta tiene su propio Número de Gödel: \boldsymbol{q}.
\boldsymbol{q} ⇒ «una autorreferencia no es demostrable en x«
Continuamos generalizando \boldsymbol{q} para todo x, lo cual es una operación recursivamente definida (gen(x,\boldsymbol{q}), pensémosla como la función que devuelve el Número de Gödel de la fórmula resultado de haber añadido los símbolos ∀x a la fórmula \boldsymbol{q}). Así construimos el número \boldsymbol{p} (17 Gen q en la publicación original):
\boldsymbol{p} ⇒ «una autorreferencia no es demostrable»
\boldsymbol{p} aquí es el Número de Gödel de una fórmula que afirma que de todas las x ninguna demuestra la fórmula y, la cual es autorreferente.
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 de la historia sea la conocida como Paradoja de Epiménides, esa que parafraseamos como «esto es mentira». La demostración de los Teoremas de Incompletitud juega con esa premisa.
\boldsymbol{p} es el número que representa una propiedad, la cual tiene aún una variable libre y que es la fórmula autorreferente. Así que es posible pasarle como argumento a tal fórmula el propio número \boldsymbol{p}. Así, la propiedad \boldsymbol{p} que asegura que una autorreferencia es no demostrable, se aplica a sí misma, convirtiéndose ella misma en una autorreferencia. La autorreferencia de \boldsymbol{p} la llamaremos \boldsymbol{p}.
\boldsymbol{r} ⇒ » ‘una autorreferencia no es demostrable’ no es demostrable en x«
El último paso sería generalizar \boldsymbol{r} para todas las x. Se trata de la famosa proposición 17 Gen r en el lenguaje del propio Gödel, también conocida como «G».
gen(x,\boldsymbol{r}) ⇒ «‘una autorreferencia no es demostrable’ no es demostrable»
es decir, ‘una autorreferencia no es demostrable’ no puede ser demostrado por ninguna x. Podemos darnos cuenta que tal propiedad es aquella que resulta de aplicar la propiedad \boldsymbol{p} sobre sí misma.
Si analizamos esta expresión, comprobamos que ella misma es autorreferente y por tanto designa nada más y nada menos que su propia indemostrabilidad. La fórmula en sí no es contradictoria desde una perspectiva semántica. Y de hecho, si la interpretamos como hemos indicado es realmente una afirmación verdadera.
Recordemos que para que nuestro sistema sea completo, o bien gen(x,\boldsymbol{r}) o ¬gen(x,\boldsymbol{r}) deben ser demostrables. ¿Está nuestro sistema P capacitado para demostrar alguna de estas opciones? o en otras palabras… ¿Existe alguna n que o bien dem(n,gen(x,\boldsymbol{r})) o bien dem(n,¬gen(x,\boldsymbol{r}))?
La paradoja
Volvamos a la propiedad \boldsymbol{q}, la cual sentenciaba que una determinada cadena de fórmulas no demostraba una autorreferencia. Su generalización para todas las cadenas posibles es \boldsymbol{p}. Ocurre entonces que:
dem(n,gen(x,\boldsymbol{r})) ⇒ ¬q(n,\boldsymbol{p}) es demostrable
Puesto que gen(x,\boldsymbol{r}) es equivalente a una aplicación de \boldsymbol{p} sobre sí misma, si la primera es demostrable en n, entonces esa misma cadena de fórmulas n demostrará la autorreferencia de \boldsymbol{p}, lo cual es equivalente a decir que ¬q(n,\boldsymbol{p}) es demostrable. Ahora bien, esto es incompatible con la generalización de \boldsymbol{r} dado que habría un caso, el de n que demostraría la autorreferencia: «‘una autorreferencia no es demostrable’ es demostrable en n«, por lo tanto gen(x,\boldsymbol{r}) no podría ser demostrable si nuestro sistema es consistente. Pero, la petición inicial de todo el teorema supone que el sistema es consistente, así que debemos encontrar otra salida.
Supongamos ahora que fuese demostrable ¬gen(x,\boldsymbol{r}). Entonces, la autorreferencia de \boldsymbol{p} no es demostrable, propiedad que es expresada por \boldsymbol{q}:
dem(n,¬gen(x,\boldsymbol{r})) ⇒ q(n,\boldsymbol{p}) es demostrable
Esto sería así para cualquier número que fuese n: ningún n demuestra \boldsymbol{p} autorreferente. Pero hemos dicho que ¬gen(x,\boldsymbol{r}) es demostrable, es decir, debe existe alguna cadena de fórmulas que demuestra \boldsymbol{r}: «‘una autorreferencia no es demostrable’ es demostrable en n«.
Consecuencias
Cualquiera de las dos opciones, tanto gen(x,\boldsymbol{r}) como ¬gen(x,\boldsymbol{r}) no pueden ser demostradas en el sistema si este es ω-consistente, pues vemos que sería posible encontrar un número particular que contradijese la generalización. Los resultados de este teorema se ciñen exclusivamente a esta definición más rígida de consistencia. Algunos años más tarde, estos resultados de Gödel se extenderían a la concepción más amplia de consistencia que hemos manejado en esta serie.
Conclusión: un sistema lo suficientemente potente como para desplegar los rudimentos de la Aritmética básica y que sea consistente, presenta fórmulas que no son decidibles, es decir, ni la fórmula ni su negación forman parte de los teoremas demostrables por el sistema.
Segundo de los Teoremas de Incompletitud
Para la demostración del Segundo Teorema de Incompletitud (Proposición XI en el artículo original), Gödel se apoya en el resultado previo: si el sistema formal P es consistente, entonces gen(x,\boldsymbol{r}) es indemostrable.
Enunciado del segundo teorema
El Segundo Teorema de Incompletitud se enuncia como: en todo sistema deductivo que permita expresar funciones recursivas primitivas que sea consistente no es posible deducir en él la sentencia que anuncia la consistencia del propio sistema.
No solo nuestro sistema es incapaz de enunciar todas los teoremas aritméticos, sino que es incapaz de afirmar su propia consistencia.
Demostración del segundo teorema
Como indicamos antes, si el sistema es consistente, entonces gen(x,\boldsymbol{r}) no puede ser demostrado. Expresamos esto tal que:
wid(x) es la propiedad del sistema de ser consistente. Gödel no aclara como puede construirse tal enunciado pero sabemos que la consistencia es una metapropiedad restrictiva que limita las fórmulas que son deducibles y a partir de aquí podemos construir una sentencia que anuncie la consistencia del sistema. nodem(x) es una propiedad recursivamente definida que declara que la fórmula con el número x no es demostrable.
Sea W la fórmula dentro del sistema que expresa wid(x), su propia consistencia. Además, por la definición de q(x,y) que expusimos antes (y autorreferente no es demostrable en x), y sabiendo que gen(x,\boldsymbol{r}) es equivalente a \boldsymbol{p} aplicada sobre sí misma, decimos que:
en otras palabras, si la fórmula W es demostrable, también lo será la generalización de \boldsymbol{r} (recordemos que\boldsymbol{r} es igual a q(x,\boldsymbol{p})).
Conclusión del segundo teorema
Fijémonos que el teorema no renuncia a la posibilidad de una demostración de consistencia del sistema, sino que impide que esta provenga de sistema mismo. Un metasistema capaz de reflejar el sistema P puede alcanzar una demostración de su consistencia. Pero entonces dicho sistema también sufrirá las consecuencias del Segundo Teorema de Incompletitud. Podemos continuar el razonamiento ad infinitum, sin posibilidad de alcanzar una demostración de consistencia universal.
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 cuales podían ser sus consecuencias variaban en cada autor. Von Neumann rápidamente argumentó que los teoremas cerraban definitivamente el proyecto formalista con un rotundo fracaso. El propio Gödel fue inicialmente mucho menos concluyente. En el mismo artículo donde desarrolla los teoremas nos advierte de que estos en sí no cerraban el debate. La exigencia de Hilbert era una demostración de la consistencia de la Aritmética por fines finitistas. Lo que los teoremas de incompletitud estipulaban es que tal demostración no podía ser lograda dentro de la propia Aritmética.
De hecho, unos años después de la publicación de Gödel, el matemático Gerhard Gentzen expuso una demostración de la consistencia de la Aritmética (de los Axiomas de Peano de primer orden). Eso sí, lo hizo desde un sistema completamente distinto al de los teoremas de Gödel, el cual incluye razonamientos transfinitos sobre entidades infinitas.
Hilbert mismo intentaría continuar con el proyecto formalismo con un finitismo menos rígido, aunando tanto los mecanismos de inducción finitaria de los Axiomas de Peano, como la inducción sobre entidades infinitas.
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 tratan esta temática. El tema es tan absolutamente basto que no lo desarrollaremos aquí. Dejaremos simplemente una reflexión del propio Gödel, realizada unos cuantos años 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)
Lecturas Recomendadas
– Gödel, K. (2006) Obras completas. Edición de Jesús Mosterín.
