TEOREMA DE GÖDEL

               

TEOREMA DE KURT GÖDEL

 Los teoremas de lógica matemática demostrados por Kurt Gödel en 1931.

 Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritméticas.

El primer teorema de incompletitud afirma que, bajo ciertas condiciones, ninguna teoría matemática formal capaz de describir losnúmeros naturales y la aritmética con suficiente expresividad, es a la vez consistente y completa. Es decir, si los axiomas de dicha teoría no se contradicen entre sí, entonces existen enunciados que no pueden probarse ni refutarse a partir de ellos. En particular, la conclusión del teorema se aplica siempre que la teoría aritmética en cuestión sea recursiva, esto es, una teoría en la que el proceso de deducción pueda llevarse a cabo mediante un algoritmo.

La prueba del teorema es totalmente explícita y en ella se construye una fórmula, denotada habitualmente G en honor a Gödel, para la que dada una demostración de la misma, puede construirse una refutación, y viceversa. Sin embargo, la interpretación natural de dicha sentencia en términos de números naturales es verdadera.

El segundo teorema de incompletitud es un caso particular del primero: afirma que una de las sentencias indecidibles de dicha teoría es aquella que «afirma» la consistencia de la misma. Es decir, que si el sistema de axiomas en cuestión es consistente, no es posible demostrarlo mediante dichos axiomas.

PRIMER TEOREMA DE INCOMPLETITUD DE GÖDEL

Cualquier teoría aritmética recursiva que sea consistente es incompleta.

La demostración de este teorema pasa por construir una cierta fórmula, la «sentencia de Gödel» G, que no puede ser probada ni refutada en T: ni G ni ¬G (la negación de G) son teoremas de T. Se dice entonces que G y ¬G son indecidibles o independientes en T.

Para llegar a esta, Gödel desarrolló un método para codificar signos y fórmulas mediante números, llamado numeración de Gödel. Usando esta numeración, es posible traducir las propiedades de una teoría formal T, tales como «estos signos constituyen una fórmula» o «estas fórmulas no son una demostración en T», a propiedades aritméticas de dichos números. En particular, la sentencia de Gödel G es una fórmula aritmética cuyo significado es «no existe una demostración de G en la teoría T», o en otras palabras, «no soy demostrable en la teoría T».

SEGUNDO TEOREMA DE INCOMPLETITUD DE GÖDEL En toda teoría aritmética recursiva consistente T, la fórmula Consis T no es un teorema.

La demostración del segundo teorema requiere traducir el primero a una fórmula. El primer teorema afirma, entre otras cosas, que si T es consistente, entonces G no es demostrable. La fórmula que afirma la consistencia de T es Consis T, mientras que la fórmula que afirma la indemostrabilidad de G es la propia G. La fórmula que traduce el primer teorema (una parte de él) es Consis T ⇒ G, donde «⇒» significa implicación. Gödel demostró que esta fórmula es un teorema, y que por lo tanto Consis T no es un teorema: si lo fuera, de las reglas básicas de T como teoría formal se deduciría que G es demostrable, en contradicción con el enunciado del primer teorema de incompletitud.

La numeración de Gödel es una herramienta que permite relacionar las teorías formales con la aritmética. El lenguaje de una teoría formal de primer orden está compuesto por una cantidad —a lo sumo— numerable de signos, como por ejemplo:

∃ , ⇒ , ¬ , |, =, x , y , z , ... , 0 , + , × , S

en el caso del lenguaje de la aritmética de Peano, donde además de los símbolos lógicos y las variables, aparecen algunos símbolos adicionales para la arimética (donde S es el símbolo para denotar «el número siguiente a»). También el conjunto de todas las cadenas (sucesiones finitas de signos) es numerable, así como el conjunto de las sucesiones finitas de cadenas.

Una numeración de Gödel es una asignación de un único número natural para cada elemento de cada uno de estos tres conjuntos: signos, cadenas de signos y sucesiones de cadenas.