Teoremas de la incompletitud de Gödel

En lógica matemática, los teoremas de la incompletitud de Gödel son dos célebres teoremas demostrados por Kurt Gödel en 1930. Simplificando, el primer teorema afirma:

En cualquier formalización consistente de las matemáticas que sea lo bastante fuerte para definir el concepto de números naturales, se puede construir una afirmación que ni se puede demostrar ni se puede refutar dentro de ese sistema.

Este teorema es uno de los más famosos fuera de las matemáticas, y uno de los peor comprendidos. Es un teorema en lógica formal, y como tal es fácil malinterpretarlo. Hay multitud de afirmaciones que parecen similares a este primer teorema de incompletud de Gödel, pero que en realidad no son ciertas. Éstas se comentan en Malentendidos en torno a los teoremas de Gödel.

El segundo teorema de la incompletitud de Gödel, que se demuestra formalizando parte de la prueba del primer teorema dentro del propio sistema, afirma:

Ningún sistema consistente se puede usar para demostrarse a sí mismo.

Este resultado fue devastador para la aproximación filosófica a las matemáticas conocida como el programa de formalización Hilbert. David Hilbert propuso que la consistencia de los sistemas más complejos, tales como el análisis real, se podía probar en términos de sistemas más sencillos. Finalmente, la consistencia de todas las matemáticas se podría reducir a la aritmética básica. El segundo teorema de la incompletud de Gödel demuestra que la aritmética básica no se puede usar para demostrar su propia consistencia, y por lo tanto tampoco puede demostrar la consistencia de nada más fuerte.

Significado del teorema de Godel:

Los teoremas de Gödel son teoremas en lógica de primer orden, y deben entenderse en ese contexto. En lógica formal, tanto las afirmaciones matemáticas como las demostraciones se escriben en un lenguaje simbólico en el que se puede comprobar mecánicamente la validez de las pruebas. De este modo no puede haber ninguna duda de que un teorema se deduce de nuestra lista inicial de axiomas. En teoría, este tipo de pruebas se puede verificar con un ordenador, y de hecho hay programas que lo hacen (se llama razonamiento automatizado).

Para poder realizar este proceso se necesita saber cuáles son estos axiomas. Se puede partir de un conjunto finito de axiomas, como en la geometría euclídea, o más en general se puede permitir un número infinito de axiomas con el requisito de que dada una afirmación se pueda verificar mecánicamente si ésta es uno de los axiomas. Aunque pueda sonar extraño el uso de un número infinito de axiomas, esto es precisamente lo que se hace habitualmente con los números naturales, los axiomas de Peano.

El primer teorema de la incompletud de Gödel demuestra que cualquier sistema que permita definir los números naturales es necesariamente incompleto: contiene afirmaciones que ni se pueden demostrar ni refutar.

La existencia de un sistema incompleto no es en sí particularmente sorprendente. Por ejemplo, si se elimina el postulado del paralelismo de la geometría euclídea se obtiene un sistema incompleto. Un sistema incompleto puede significar simplemente que no se han descubierto todos los axiomas necesarios.

Lo que mostró Gödel es que en la mayoría de los casos, como en la teoría de números o en análisis real, nunca se puede descubrir el conjunto completo de axiomas. Cada vez que se añada un nuevo axioma siempre habrá otro que quede fuera de alcance.

También se puede añadir un conjunto infinito de axiomas. Por ejemplo, todas las afirmaciones verdaderas sobre los números naturales, pero esa lista no será un conjunto recursivo. Dada una afirmación cualquiera, no habrá forma de saber si es un axioma en el sistema o no. Dada una prueba no habrá en general una manera de verificar que esa prueba es válida.

El teorema de Gödel tiene otra interpretación en el contexto de la informática. En lógica de primer orden, los teoremas son recursivamente enumerables: se puede construir un programa de ordenador que terminará por dar una demostración válida. Sin embargo, no cumplen la propiedad más fuerte de ser un conjunto recursivo: no se puede construir un programa que dada una afirmación cualquiera determine si ésta es cierta o no.

Muchos lógicos piensan que los teoremas de incompletud de Gödel asestaron un mazazo fatal al programa de formalización de Hilbert que apuntaba a un formalismo matemático universal. La postura aceptada generalmente es que fue el segundo teorema el que asestó este golpe. Algunos sin embargo piensan que fue el primero, e incluso hay quien piensa que ninguno de ellos lo hizo.