Al fin veo la luz

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.

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.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.