Teorema de Gödel
Introduccion
En 1931
apareci ́o en una publicaci ́on cient ́ıfica alemana un trabajo
relativamente
corto, que llevaba el impresionante tıtulo de
sobre las proposiciones formalmente indecidibles de los Principio
Matematica y
sistemas conexos.
Su autor eraKurt Godel, a la saz ́on un joven
matematico de
veinticinco
a ̃nos de la Universidad de Viena y, desde 1938,
miembro
permanente del Instituto de Estudios Avanzados de Princeton.
Los teoremas de incompletitud de Gödel son dos célebres teoremas de logicamente matematica demostrados por Kurt Godel en 1931. Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritmeticas.
El primer teorema de incompletitud afirma que, bajo ciertas
condiciones, ninguna teoría matemática formal capaz de describir los numeros naturales y la aritmética con suficiente expresividad, es a la vez consistentey 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.
Los teoremas de incompletitud de Gödel son uno de los grandes avances
de la lógica matemática, y supusieron —según la mayoría de la comunidad
matemática— una respuesta negativa al segundo teorema de Hiñbert.
Primer teorema
El enunciado del primer teorema reza:
Primer teorema de incompletitud de Gödel |
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 numeracion de Godel. 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».
Consecuencias
La sentencia de Gödel G no es demostrable pero es cierta, pues afirma precisamente su propia indemostrabilidad.
Esto significa que ninguna teoría aritmética en las condiciones del
teorema es capaz de demostrar todos los enunciados verdaderos de la
aritmética.
Además, aunque ¬G sea falsa (por afirmar lo contrario que G) no es refutable (puesto G
es indemostrable). Esta sentencia puede tomarse como axioma si se desea
y esto no produce una contradicción. La teoría resultante contiene
muchos de los enunciados verdaderos sobre los números naturales y
algunos falsos, empezando por ¬G. Los objetos descritos por una teoría así forman un modelo no estandar de la aritmética.
Tomando G (o su contraria) como axioma se obtiene una nueva teoría T' en la que G (o su contraria) es demostrable automáticamente. Sin embargo esto no invalida el teorema, puesto que G afirma su indemostrabilidad relativa a la teoría T. La nueva teoría T' es también incompleta: puede encontrarse una nueva sentencia independiente G', que afirma «no soy demostrable en T'».
En definitiva, en una teoría formal que sea consistente y completa
debe fallar alguna de las hipótesis: o bien no es recursiva y no hay un algoritmo
para distinguir los axiomas del resto de fórmulas; o bien no son
aritméticas, y no incluyen las propiedades básicas necesarias de los
números naturales. Por ejemplo, en la demostración del teorema de completitud semantica se utilizan teorías consistentes y completas que no son recursivas. Por otro lado, la aritmatica de Presburger
es una colección de axiomas sobre los números naturales que omite
varias de sus propiedades, hasta el punto de que una teoría basada en
ellos puede ser consistente y completa.
Segundo teorema
El segundo teorema de incompletitud muestra otro ejemplo explícito de
una fórmula que ninguna teoría aritmética puede demostrar, además de G. De nuevo, usando la numeración de Gödel, puede encontrarse una fórmula, denotada Consis T, cuyo significado es «no puede encontrarse una contradicción en T», o en otras palabras, «T es consistente».
Segundo teorema de incompletitud de Gödel |
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 implicacion. 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.
Consecuencias
El segundo teorema de incompletitud limita las posibilidades de demostrar la consistencia de una teoría formal T, puesto que no puede hacerse utilizando únicamente la propia T. Además, si se encuentra una teoría más fuerte T' en la que Consis T pueda demostrarse, la propia consistencia de T' no podrá demostrarse en T' ni tampoco en T. Por ello, el segundo teorema se considera una respuesta negativa al llamado Programa de Hilbert, que proponía demostrar la corrección de los razonamientos matemáticos basados en objetos infinitos usando tan solo razonamientos basados en objetos finitos, menos potentes que los primeros.
Demostración de los teoremas
La demostración de los teoremas de incompletitud se basa en tres conceptos:
- La numeración de Gödel, que permite traducir las teorías formales a operaciones de aritmetica pura.
- La potencia expresiva de las teorías formales aritméticas, cuyas expresiones recogen dichas operaciones.
- El lema diagonal, que permite que las fórmulas sean autorreferentes.
El enunciado original debido a Gödel, cuya demostración se esboza en
esta sección, es más débil que el presentado arriba, ya que en lugar de
la consistencia de la teoría T se exige una propiedad más fuerte, laW - consistencia
Una teoría aritmética es ω-inconsistente si, para alguno de sus teoremas formales de la forma ∃x, φ(x), puede refutarse cualquier caso particular, esto es, puede probarse ¬φ([n]), para cada numeral [n]. Una teoría que no es ω-inconsistente se dice ω-consistente. |
(Los numerales [n] son los
símbolos que utilice el lenguaje de la teoría para especificar los
números naturales concretos. En el ejemplo de la aritmética de Peano en
la sección siguiente, los numerales son los símbolos dados por: [0] ≡ 0, [1] ≡ S0, [2] ≡ SS0,
etc.) La ω-consistencia implica la consistencia (pero no al revés). El
enunciado «fuerte», en el que sólo se requiere la consistencia de la
teoría fue probado por J. B. Rosser mediante un método muy similar.
