thumb|upright|Kurt Gödel a los 19 años de edad, cinco años antes de la demostración de los teoremas. Los teoremas de incompletitud de Gödel son dos célebres 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.
Síntesis 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. Es decir, si los axiomas de dicha teoría no se contradicen entre sí, entonces existen enunciados que no se pueden probar ni refutar 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 se pueda llevar a cabo mediante un algoritmo.
La prueba del teorema es totalmente explícita y en ella se construye una fórmula, denotada habitualmente en honor a Gödel, para la que dada una demostración de la misma, se puede construir una refutación, y viceversa. Sin embargo, la interpretación natural de dicha sentencia en términos de números naturales es verdadera.Véase la parte dedicada a Gödel en la introducción de .
thumb|Segundo teorema de incompletitud de Gödel 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 problema de Hilbert. Los teoremas implican que los sistemas axiomáticos de primer orden tienen severas limitaciones para fundamentar las matemáticas, y supusieron un duro golpe para el llamado programa de Hilbert para la fundamentación de las matemáticas. Por otra parte, durante algún tiempo ni Hilbert ni otros de sus colaboradores fueron conscientes de la importancia del trabajo de Gödel para su programa.
Contexto Los teoremas de incompletitud de Gödel establecen ciertas limitaciones sobre lo que es posible demostrar mediante un razonamiento matemático. Para hablar con precisión sobre qué «puede demostrarse» o no, se estudia un modelo matemático denominado teoría formal. Una teoría formal consta de una serie de signos y un conjunto de reglas para manipularlos y combinarlos. Mediante estas reglas se pueden distinguir ciertas colecciones de signos como fórmulas, y ciertas sucesiones de fórmulas como demostraciones. Los teoremas de una cierta teoría son entonces todas las fórmulas que puedan demostrarse a partir de una cierta colección inicial de fórmulas que se asuman como axiomas.
A una teoría formal se le pueden adjudicar ciertas propiedades en función de lo que sea capaz de demostrar. Una teoría consistente no contiene contradicciones, es decir, no es posible demostrar a la vez una fórmula y su contraria. Una teoría que no sea consistente no tiene utilidad: debido al principio de explosión, a partir de una contradicción pueden demostrarse todas sus fórmulas, y no sirve para modelizar razonamientos matemáticos. Una teoría completa «responde cualquier pregunta», en el sentido de que para cada una de sus fórmulas o bien es demostrable, o bien existe una demostración de su contraria (es refutable). Una teoría completa es óptima, y se corresponde con la intuición sobre la verdad lógica: al igual que toda sentencia debe ser verdadera o falsa, en una teoría completa toda fórmula es demostrable o refutable.
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. La primera de ellas es que sea una teoría aritmética, es decir, que sus símbolos sirvan para describir los números naturales y sus operaciones y relaciones; y que sea capaz de demostrar algunas propiedades básicas sobre ellos. La segunda hipótesis es que sea una teoría recursiva, lo cual significa que las reglas para manipular sus signos y fórmulas en las demostraciones han de poder ejecutarse mediante un algoritmo: una serie precisa de pasos sin ambigüedad que pueda llevarse a cabo en un tiempo finito, e incluso implementarse mediante un programa informático.
Primer teorema El enunciado del primer teorema reza:
La demostración de este teorema pasa por construir una cierta fórmula, la «sentencia de Gödel» , que no puede ser probada ni refutada en la teoría aritmética recursiva : ni ni (la negación de ) son teoremas de . Se dice entonces que y son indecidibles o independientes en .
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 , tales como «estos signos constituyen una fórmula» o «estas fórmulas no son una demostración en », a propiedades aritméticas de dichos números. En particular, la sentencia de Gödel es una fórmula aritmética cuyo significado es «no existe una demostración de en la teoría », o en otras palabras, «no soy demostrable en la teoría ».
Consecuencias La sentencia de Gödel no es demostrable pero es cierta, pues afirma precisamente su propia indemostrabilidad.Esto solo es cierto en la interpretación natural en que las variables de la teoría se interpretan como los números naturales. 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 sea falsa (por afirmar lo contrario que ) no es refutable (puesto 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 . Los objetos descritos por una teoría así forman un modelo no estándar de la aritmética.Véase para una exposición de nivel intermedio sobre la aritmética no estándar.
Tomando (o su contraria) como axioma se obtiene una nueva teoría en la que (o su contraria) es demostrable automáticamente. Sin embargo esto no invalida el teorema, puesto que afirma su indemostrabilidad relativa a la teoría . La nueva teoría es también incompleta: puede encontrarse una nueva sentencia independiente , que afirma «no soy demostrable en ».
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 semántica se utilizan teorías consistentes y completas que no son recursivas.Véase . Por otro lado, la aritmética de Presburger es una colección de axiomas sobre los números naturales que omite varias de sus propiedades, a tal punto que una teoría basada en ellos puede ser consistente y completa.Véase .
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 . De nuevo, usando la numeración de Gödel, puede encontrarse una fórmula, denotada , cuyo significado es «no puede encontrarse una contradicción en », o en otras palabras, « es consistente».
La demostración del segundo teorema requiere traducir el primero a una fórmula. El primer teorema afirma, entre otras cosas, que si es consistente, entonces no es demostrable. La fórmula que afirma la consistencia de es , mientras que la fórmula que afirma la indemostrabilidad de es la propia . La fórmula que traduce el primer teorema (una parte de él) es , donde «» significa implicación. Gödel demostró que esta fórmula es un teorema,En realidad, la prueba original de Gödel omite ciertos detalles técnicos. y que por lo tanto no es un teorema: si lo fuera, de las reglas básicas de como teoría formal se deduciría que 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 , puesto que no puede hacerse utilizando únicamente la propia . Además, si se encuentra una teoría más fuerte en la que pueda demostrarse, la propia consistencia de no podrá demostrarse en ni tampoco en . 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.
Enunciados indecidibles
El primer teorema de incompletitud de Gödel demuestra la existencia de enunciados indecidibles o independientes en la aritmética de Peano, y tanto el primero como el segundo muestran ejemplos concretos de enunciados indecidibles. Desde entonces se han encontrado otros ejemplos de enunciados independientes de los axiomas de Peano, como por ejemplo el teorema de Ramsey «fuerte». Existen además numerosos ejemplos de enunciados independientes en otras teorías formales más fuertes que la aritmética, como la hipótesis del continuo o el axioma de elección en teoría de conjuntos; o incluso en teorías no directamente relacionadas con la aritmética, como en el caso de la geometría euclídea y el postulado de las paralelas.
Discusión e implicaciones Los resultados de incompletitud afectan a la filosofía de las matemáticas, particularmente a los puntos de vista tales como el formalismo, que usa la lógica formal para definir sus principios.
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.
La siguiente reformulación del segundo teorema es todavía más inquietante para los fundamentos de las matemáticas:
Si se puede demostrar que un sistema axiomático es consistente a partir de sí mismo, entonces es inconsistente.
Por tanto, para establecer la consistencia de un sistema se necesita utilizar otro sistema , pero una prueba en no es totalmente convincente a menos que la consistencia de ya se haya probado sin emplear . La consistencia de los axiomas de Peano para los números naturales por ejemplo se puede demostrar en la teoría de conjuntos, pero no en la teoría de los números naturales por sí sola. Esto proporciona una respuesta negativa al problema número dos de la famosa lista de cuestiones abiertas importantes en matemáticas de David Hilbert (llamada problemas de Hilbert).
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.