Ya podemos demostrar los teoremas de incompletitud de Gödel. Vamos a enunciarlos para ZFC, pero nos basaremos en los hechos que hemos probado también para Z y ZF y, que, en general, pueden probarse para toda teoría de conjuntos suficientemente potente (en particular para toda teoría que extienda a Z) cuyos axiomas sean "reconocibles" en el sentido de que podamos distinguir sin dudas lo que es un axioma y lo que no lo es, y que la justificación de si lo es o no lo es puede formalizarse en la propia teoría.
Recordemos que tenemos definido en Z lo que significa que una sucesión \( D\in S^2 \) sea una demostración de una fórmula \( \alpha\in \mathcal F \) a partir de los axiomas de ZFC. Lo representaremos por \( \mbox{ZFC}\vdash_D\alpha \).
En virtud del teorema demostrado en el mensaje anterior, podemos definir la sentencia de Gödel de ZFC como la sentencia \( G \) que resulta de aplicar dicho teorema a la fórmula
\( \phi(x)\equiv \lnot \exists D\in S^1\ \mbox{ZFC}\vdash_Dx \)
.
Se trata, pues, de una sentencia con la propiedad de que, en Z (luego en ZFC) puede probarse que
\( G\leftrightarrow \phi(\ulcorner G\urcorner)\equiv \lnot \exists D\in S^1\ \mbox{ZFC}\vdash_D \ulcorner G\urcorner \).
Así pues, \( G \) equivale a "yo no puedo ser demostrada en ZFC".
Recordemos que una teoría axiomática se dice
consistente si en ella no pueden demostrarse contradicciones.
Teorema ZFC es consistente si y sólo si \( G \) no es demostrable en ZFC.
Demostración
Supongamos que \( G \) es demostrable en ZFC y sea \( D \) una demostración. Según vimos en la respuesta #7, entonces en Z (luego en ZFC) se puede demostrar que
\( \mbox{ZFC}\vdash_{\ulcorner D\urcorner}\ulcorner G\urcorner \),
pero esto implica
\( \exists D\in S^1\mbox{ZFC}\vdash_D\ulcorner G\urcorner \),
lo cual es a su vez equivalente a \( \lnot G \). En resumen, si \( G \) es demostrable en ZFC, también lo es \( \lnot G \), con lo que ZFC es contradictorio.
El recíproco es trivial: si \( G \) no es demostrable en ZFC entonces ZFC es consistente, porque un hecho básico de la lógica matemática es que a partir de una contradicción se puede demostrar cualquier cosa, por lo que en una teoría contradictoria todas las sentenciaas son teoremas o, al revés, si una sentencia cualquiera no es un teorema de una teoría, entonces la teoría es consistente.
Gödel demostró que \( \lnot G \) tampoco es demostrable suponiendo en la teoría una propiedad más fuerte que la consistencia, pero que no es fácil de verificar. Sin embargo, ese argumento no es especialmente interesante, pues es posible construir una sentencia más fina que \( G \) para la cual el teorema se cumple sin hipótesis adicionales. Enseguida veremos este hecho, pero antes extraeremos una consecuencia fundamental del teorema anterior.
En Z puede probarse, por ejemplo, que \( \forall x\,x=x \), luego, si Z es consistente, no tiene que ser posible demostrar lo contrario, es decir, \( \lnot\forall x\,x=x \) y, recíprocamente, si no es posible demostrar esta sentencia, entonces Z es consistente, porque, como ya hemos señalado, si Z fuera contradictoria podríamos demostrar cualquier cosa a partir de sus axiomas. Lo mismo vale para ZFC o cualquier otra teoría "razonable".
Por consiguiente, podemos definir \( \mbox{Consis ZFC}\equiv \lnot \exists D\,\mbox{ZFC}\vdash_D\ulcorner\lnot\forall x\,x=x\urcorner \).
Ahora observamos que todos los razonamientos metamatemáticos que hemos hecho sobre Z o ZFC, en particular todos los que hemos empleado para concluir con la demostración del teorema anterior, son formalizables en Z. Si aceptamos que cualquier teorema demostrado con el nivel de formalización usual en un libro de matemáticas es un teorema de ZFC (o de Z, si no habla de cosas muy raras), entonces resulta que la demostración que hemos dado del teorema anterior está dada con el nivel de formalización usual en un libro de matemáticas, por lo que es un teorema de ZFC (y, aunque no es importante el matiz, realmente lo es de Z).
Enunciado como teorema de Z, el teorema anterior es la sentencia:
\( \mbox{Consis ZFC}\leftrightarrow \lnot\exists D\,\mbox{ZFC}\vdash_D\ulcorner G\urcorner \),
Pero el segundo miembro equivale a \( G \) en \( Z \), luego concluimos que en Z se puede demostrar:
\( \mbox{Consis ZFC}\leftrightarrow G \).
Por consiguiente, el teorema anterior admite este enunciado equivalente:
Segundo teorema de incompletitud de Gödel ZFC es consistente si y sólo si Consis ZFC no es demostrable en ZFC.En general, una teoría de conjuntos "razonable" es consistente si y sólo si no es capaz de demostrar la sentencia que firma su propia consistencia.
El chiste del presuntuoso
El segundo teorema de incompletitud queda perfectamente ilustrado por este chiste:
Yo antes era un presuntuoso, pero fui a un psicólogo y me curó. Ahora ya soy perfecto.
Del mismo modo que si alguien afirma de sí mismo ser perfecto ya podemos asegurar que no lo es, pues, al menos, tiene el defecto de la presunción, si una teoría matemática afirma de sí misma que es consistente, podemos asegurar que no lo es, por el segundo teorema de incompletitud. Si una teoría axiomática T es consistente, la afirmación Consis T será verdadera, pero no será demostrable en T, del mismo modo que podría ser verdad que alguien fuera perfecto, pero a condición de que no fuera por ahí presumiendo de serlo.
Para demostrar el primer teorema de incompletitud sin hipótesis adicionales definimos el tamaño de una sucesión finita de sucesiones finitas de números naturales como el máximo entre su longitud, la máxima longitud de sus términos, y el máximo número que aparece en ellos. Así, es claro que sólo hay un número finito de sucesiones finitas de sucesiones finitas de números naturales de tamaño a lo sumo \( n \). Más aún, es claro que, aunque sea por pura fuerza bruta, es posible enumerarlas todas, digamos \( D_0,\ldots, D_k \) y, más aún, que en Z es posible demostrar que no hay más, es decir, que en Z se puede demostrar:
\( \forall D(D\in S^2\land t(D)\leq \ulcorner n\urcorner\rightarrow D=\ulcorner D_0\urcorner\lor \cdots\lor D=\ulcorner D_k\urcorner), \)
donde representamos por \( t(D) \) el tamaño de \( D \).
Consideramos ahora la fórmula
\( \phi(x)\equiv \forall D(\mbox{ZFC}\vdash_Dx\rightarrow \exists E\in S^2(t(E)\leq t(D)\land \mbox{ZFC}\vdash_E\ulcorner\lnot\urcorner x)) \)
y llamamos sentencia de Rosser de ZFC a la sentencia \( R \) que resulta de aplicar a esta fórmula el teorema del mensaje anterior, de modo que en Z se demuestra que
\( R\leftrightarrow \forall D(\mbox{ZFC}\vdash_D\ulcorner R\urcorner\rightarrow \exists E\in S^2(t(E)\leq t(D)\land \mbox{ZFC}\vdash_E \ulcorner \lnot R\urcorner)) \).
Lo que afirma la sentencia de Rosser es: "Si tengo una demostración \( D \), entonces existe una demostración \( E \) de mi negación de tamaño menor que \( D \)".
Primer teorema de incompletitud de Gödel (versión de Rosser) Si ZFC es consistente, entonces ni \( R \) ni \( \lnot R \) son demostrables en ZFC.Demostración
Supongamos que \( R \) es demostrable en ZFC. Entonces en ZFC podemos probar que
\( \forall D(\mbox{ZFC}\vdash_D\ulcorner R\urcorner\rightarrow \exists E\in S^2(t(E)\leq t(D)\land \mbox{ZFC}\vdash_E \ulcorner \lnot R\urcorner)). \)
Sea \( D \) una demostración de \( R \), pongamos que de tamaño \( n \). Sabemos entonces que en Z (luego en ZFC) se puede demostrar que \( \mbox{ZFC}\vdash_{\ulcorner D\urcorner}\ulcorner R\urcorner \)
Uniendo los dos hechos, en ZFC podemos probar que
\( \exists E\in S^2(t(E)\leq \ulcorner n\urcorner\land \mbox{ZFC}\vdash_E \ulcorner \lnot R\urcorner)). \)
Sean \( D_0,\ldots, D_k \) todas las sucesiones finitas de sucesiones finitas de números naturales de tamaño menor o igual que \( n \). Entonces en ZFC se puede probar que
\( \forall E(E\in S^2\land t(E)\leq \ulcorner n\urcorner\rightarrow E=\ulcorner D_0\urcorner\lor \cdots \lor \ulcorner D_k\urcorner) \).
Uniendo los dos últimos hechos concluimos que en ZFC se demuestra que
\( \mbox{ZFC}\vdash_{\ulcorner D_0\urcorner}\ulcorner \lnot R\urcorner\lor \cdots \lor \mbox{ZFC}\vdash_{\ulcorner D_k\urcorner}\ulcorner \lnot R\urcorner \)
Si ZFC es consistente, como estamos suponiendo que es posible demostrar \( R \), tiene que ser imposible demostrar \( \lnot R \), luego ninguna de las sucesiones \( D_i \) será una demostración de \( \lnot R \), luego sabemos que en ZFC es posible demostrar
\( \lnot \mbox{ZFC}\vdash_{\ulcorner D_0\urcorner}\ulcorner\lnot R\urcorner\land \cdots \land \lnot \mbox{ZFC}\vdash_{\ulcorner D_k\urcorner}\ulcorner\lnot R\urcorner \),
pero esto es justo la negación de la fórmula precedente, lo que nos da que ZFC es contradictorio.
Concluimos, pues, que si ZFC es consistente, entonces \( R \) no es demostrable en ZFC. Supongamos ahora que \( \lnot R \) fuera demostrable. Por la equivalencia que satisface \( R \) por construcción, en ZFC podríamos demostrar que
\( \exists D(\mbox{ZFC}\vdash_D\ulcorner R\urcorner\land \forall E(t(E)\leq t(D)\rightarrow \lnot \mbox{ZFC}\vdash_E\ulcorner \lnot R\urcorner)) \)
Sea \( E \) una demostración de \( \lnot R \), digamos de tamaño \( n \). Sabemos que en ZFC se puede demostrar que
\( \mbox{ZFC}\vdash_{\ulcorner E\urcorner}\ulcorner\lnot R\urcorner \).
De las dos últimas afirmaciones se deduce que
\( \exists D(\mbox{ZFC}\vdash_D\ulcorner R\urcorner\land t(D)\leq \ulcorner n\urcorner) \).
Sean \( D_0,\ldots, D_k \) todas las sucesiones finitas de sucesiones finitas de números naturales de tamaño menor o igual que \( n \). Entonces en ZFC se demuestra que
\( \forall D\in S^1(t(D)\leq \ulcorner n\urcorner\rightarrow D=\ulcorner D_0\urcorner\lor \cdots \lor \ulcorner D_k\urcorner) \),
Luego de las dos últimas afirmaciones se deduce que
\( \mbox{ZFC}\vdash_{\ulcorner D_0\urcorner}\ulcorner R\urcorner \lor \cdots \lor \mbox{ZFC}\vdash_{\ulcorner D_k\urcorner}\ulcorner R\urcorner \).
Ahora bien, si ZFC es consistente, como en ZFC se puede demostrar \( \lnot R \), ninguna sucesión \( D_i \) puede ser una demostración de \( R \), luego en ZFC se puede demostrar que
\( \lnot\mbox{ZFC}\vdash_{\ulcorner D_0\urcorner}\ulcorner R\urcorner \land \cdots \land \lnot\mbox{ZFC}\vdash_{\ulcorner D_k\urcorner}\ulcorner R\urcorner \),
y las dos últimas afirmaciones forman una contradicción en ZFC.
En definitiva, si ZFC es consistente, ni es posible demostrar \( R \), ni es posible demostrar \( \lnot R \).
Con esto hemos llegado al objetivo de este hilo. Los lectores que conozcan la prueba clásica podrán juzgar si este planteamiento (aunque obviamente no es tan general) es o no ilustrativo, en la medida en que elimina muchos tecnicismos y deja al descubierto las ideas más relevantes de la prueba.