Gödel en una cáscara de nuez: Segundo Teorema de Incompletitud, y Teorema de Completitud

Cuando empezamos a recorrer los resultados de Gödel y mencionamos el contexto histórico mereció especial atención el programa formalista de Hilbert. Hay que recordar que el objetivo de Hilbert era definir un sistema formal completo y consistente, dentro del cual poder razonar de manera mecánica sobre cualquier noción matemática. El primer teorema de incompletitud que vimos hace unos días asestó un golpe letal a esta pretensión: en cualquier sistema formal consistente lo suficientemente complejo como para englobar a la aritmética de Peano hay afirmaciones lógicas que son indemostrables e irrefutables. Dando por perdida pues la completitud, nos podemos aferrar a la consistencia: si somos capaces de probar que nuestro sistema es consistente, tendremos al menos una garantía de la solidez de las demostraciones que hagamos dentro de él. Aquí es donde entra el segundo teorema de incompletitud para rematar definitivamente las aspiraciones de Hilbert.

El segundo teorema de incompletitud de Gödel surge casi como un corolario del primero, aunque su trascendencia es sin embargo muy grande. Recordemos que el primer teorema de incompletitud afirmaba que había una fórmula G (realmente la fórmula G depende del sistema S, por lo que deberíamos emplear la notación G_S, pero mantendremos la G por simplificar), tal que ni G ni ~G eran demostrables dentro del sistema si éste era consistente. Siguiendo con la notación que empleamos:

Recordemos también que G se define como:

por lo que es fácil ver que si tenemos una demostración de la consistencia del sistema, tenemos también una demostración de la indemostrabilidad de G, y por la propia definición de G esto significa que hemos demostrado G. Dado que sabemos que tal demostración nos lleva a la inconsistencia, hemos de concluir que nuestra suposición de partida -la existencia de una demostración de consistencia- es falsa. No podemos por lo tanto demostrar la consistencia del sistema dentro del mismo.

Aunque en su momento los teoremas de incompletitud supusieron un gran impacto, y de hecho acabaron con las ambiciones formalistas de Hilbert, vistos con retrospectiva son la consecuencia evidente de la metodología que se pretendía seguir, basada en la manipulación mecánica de símbolos y fórmulas mediante unos ciertos procedimientos bien definidos. Esto se puede apreciar más claramente si nos fijamos en un resultado anterior del propio Gödel que -quizás para complicar la cosa- se ha venido a denominar el teorema de completitud de Gödel. Este teorema captura muy bien la pretensión de Hilbert, y explica por qué ésta no es posible (o al menos se puede extraer una interpretación a posteriori del porqué).

La clave del teorema de completitud de Gödel es la idea de modelo. Básicamente, cuando definimos el sistema formal especificamos una sintaxis para expresar las fórmulas, así como unos ciertos axiomas y reglas de inferencia. Lo que tenemos ahí es una mera descripción sintáctica, que una vez dotada de una interpretación semántica, da lugar a un modelo del sistema. Por ejemplo, podemos considerar un sistema definido sobre la base de un conjunto de objetos X, y una operación interna binaria que es asociativa, conmutativa, tiene elemento neutro, y cada elemento de X tiene un inverso. Como puede apreciarse, lo que estamos definiendo aquí es un grupo abeliano. Podemos ahora dar una interpretación del conjunto X y de la operación binaria, por ejemplo, los números enteros y la suma, o los reales (menos el 0) y la multiplicación. Si demostramos algo sin hacer uso de una interpretación concreta, entonces eso debera ser cierto para todas las interpretaciones (o modelos) posibles. Decimos entonces que ese algo es universalmente válido para ese sistema.

El teorema de completitud de Gödel afirma que toda fórmula universalmente válida es demostrable. Esto puede comprobarse como sigue: supongamos que tenemos un sistema S y que hay una fórmula F que es universalmente válida para él pero que no es demostrable en él. Podemos construir ahora un sistema S’ en el que incluimos ~F como axioma, lo cual no nos ocasiona contradicción sintáctica ya que F no es demostrable. Según el teorema de existencia de modelos de Henkin, si un sistema es consistente, entonces tiene un modelo M. En dicho modelo será cierto ~F (que es un axioma) y F (que era universalmente válido en S, del que M es también modelo). Llegamos a una contradicción, luego F ha de ser demostrable.

A la luz de lo anterior, puede verse claramente que si algo es universalmente válido debe ser demostrable, y por lo tanto si algo no es demostrable es porque no es universalmente válido. No debe entonces sorprendernos que un sistema consistente sea incompleto: hay formulas que serán ciertas en unos modelos y falsas en otros, por lo que no podemos esperar demostrarlas o refutarlas abstrayéndonos de su interpretación. Esto que puede parecer evidente ahora, no lo era tanto en la época de Gödel (el trabajo de Henkin es de hecho muy posterior al de Gödel).

La noción de validez universal es el eslabón que nos va a permitir enlazar el trabajo de Gödel con la idea de computabilidad. No es la única conexión, pero sí es el enlace histórico que nos lleva por ejemplo al trabajo de Turing. Ésa será la próxima parada.