Teoremas de incompletitud de Gödel
El primer teorema de incompletitud afirma que, bajo ciertas condiciones, ninguna teoría matemática formal capaz de describir los números naturales y la aritmética con suficiente expresividad es a la vez consistente y completa.
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 se pueda llevar a cabo mediante un algoritmo.
[cita requerida] 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, se puede construir una refutación, y viceversa.
Para hablar con precisión sobre qué «puede demostrarse» o no, se estudia un modelo matemático denominado teoría formal.
Sin embargo, el primer teorema de incompletitud establece que, bajo ciertas hipótesis, una teoría formal no puede tener ambas propiedades a la vez.
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».
La sentencia de Gödel G no es demostrable pero es cierta, pues afirma precisamente su propia indemostrabilidad.
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 estándar de la aritmética.
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'».
Por ejemplo, en la demostración del teorema de completitud semántica se utilizan teorías consistentes y completas que no son recursivas.
El primer teorema afirma, entre otras cosas, que si T es consistente, entonces G no es demostrable.
Se puede parafrasear el primer teorema diciendo que «nunca se podrá encontrar un sistema axiomático que sea capaz de demostrar todas las verdades matemáticas y ninguna falsedad».
Por otra parte, desde una perspectiva estrictamente formalista esta paráfrasis se consideraría sin significado porque presupone que la «verdad» y «falsedad» matemáticas están bien definidas en un sentido absoluto, en lugar de ser relativas a cada sistema formal.
En principio, los teoremas de Gödel todavía dejan alguna esperanza: podría ser posible producir un algoritmo general que para una afirmación dada determine si es indecidible o no, permitiendo a los matemáticos evitar completamente los problemas indecidibles.
Sin embargo, la respuesta negativa al Entscheidungsproblem demuestra que no existe tal algoritmo.
Esto crea un sistema que es completo, consistente y suficientemente potente, pero no recursivamente enumerable.
En un trabajo publicado en 1957 en Journal of Symbolic Logic, Raymond Smullyan mostró que los resultados de incompletitud de Gödel pueden obtenerse para sistemas mucho más elementales que los considerados por Gödel.
Si el sistema axiomático es consistente, la prueba de Gödel muestra que
a los axiomas del sistema no resolvería el problema: habría otra sentencia de Gödel para la teoría ampliada.
También John R. Lucas se ha ocupado de esta cuestión en Mentes, Máquinas y Gödel.
[7] Esta perspectiva no está ampliamente aceptada, porque tal y como lo plantea Marvin Minsky, la inteligencia humana es capaz de errar y de comprender declaraciones que son en realidad inconsistentes o falsas.
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].
(Los numerales [n] son los símbolos que utilice el lenguaje de la teoría para especificar los números naturales concretos.
La numeración de Gödel es una herramienta que permite relacionar las teorías formales con la aritmética.
En particular la relación Ax x ha de construirse teniendo en cuenta un cierto conjunto de axiomas concreto, luego la relación Dem hace referencia a una teoría concreta que no se ha especificado.
Es posible ir más allá, ya que T es una teoría aritmética y se pueden «recodificar» las mencionadas operaciones mediante el lenguaje formal de T, al igual que se puede hacer con otras funciones y relaciones aritméticas como por ejemplo: Cada una de estas relaciones es expresada por su fórmula correspondiente, en el sentido de que si dos números están relacionados, puede demostrarse la expresión formal correspondiente; y cuando no lo están, puede refutarse.
Esto es posible en toda teoría aritmética recursiva, ya que verifican unas ciertas condiciones de demostrabilidad.
