Hola, Gustavo.
En primer lugar, creo que hay que "romper una lanza" por Gödel.
En la versión que tengo de su artículo de 1931 (Sobre sentencias formalmente indecidibles...) el segundo teorema de incompletitud aparece como Teorema XI, y Gödel dice:
La prueba (meramente esbozada) es la siguiente: ...
y luego termina:
Los resultados en toda su generalidad serán formulados y probados en una continuación de próxima aparición. En ese trabajo presentaremos también la prueba detallada del teorema XI, que aquí sólo fue esbozada.
Dicha continuación nunca se publicó. En su segundo trabajo sobre incompletitud, de 1934, el segundo teorema ni siquiera aparece enunciado como teorema, sino como una mera observación al final de la sección 5, donde dice (modifico un poco las fórmulas que cita porque sólo me interesan las palabras):
Los razonamientos más bien simples empleados en esta prueba pueden ser calcados en la lógica formal para obtener una deducción de Con \( \rightarrow \lnot G \), donde Con es una fórmula del sistema que expresa la sentencia [no se puede deducir una contradicción]. Entonces, si también fuese deducible Con, podríamos [...] inferir G, en cuyo caso, como ya se ha visto, el sistema contendría una contradicción.
Como digo, he alterado un poco las fórmulas que escribe Gödel, porque lo único que quiero destacar es que Gödel insiste en que simplemente está dando un esbozo de la prueba, y todo lo que dice en dicho esbozo es correcto, aunque lo que dice no lo justifica, pero creo que no hay duda de que él mismo es consciente de ello, por lo que no puede decirse que su justificación no es correcta. No porque sí que lo sea, sino porque no pretende ser una justificación. Concretamente, Gödel no pretende justificar en ningún momento su afirmación de que toda la prueba finitista del (primer) teorema de incompletitud es formalizable en cualquier teoría aritmética. Lo afirma diciendo que "se puede demostrar", pero no lo demuestra.
¿Por qué desconfío de la demostración de Gödel?
A esto quería llegar: no creo que pueda hablarse de "la demostración" de Gödel.
Dicho esto, queda planteado el problema de proporcionar una prueba que justifique la afirmación de Gödel al respecto.
Gödel dice que todo el desarrollo que lleva de \( CON \) a \( G \) (en realidad, de \( \sim G \) a \( \sim CON \)) puede traducirse a una sucesión de fórmulas que constituye una demostración aritmética según la lógica de primer orden. Ese desarrollo, recordemos, comienza así:
“Supongamos que \( G \) sí fuese demostrable; entonces existiría un número \( k \) que es el código de una demostración de \( G \). Por lo tanto el enunciado \( Dem(\bar{k}, \bar{g}) \) sería verdadero y finitista (su verdad es verificable algorítmicamente en una cantidad finita de pasos), y por ende, por hipótesis, es demostrable.”
¿Cómo se traduce esto sintácticamente, es decir, como se lo convierte en una demostración aritmética formal de primer orden?
“\( G \) es demostrable” se expresa así: \( \exists x Dem(x,\bar{g}) \). De esto hemos deducido que vale \( Dem(\bar{k}, \bar{g}) \) para algún \( k \). Pero para traducir esto a una deducción sintáctica necesitaríamos que el siguiente esquema sea válido en la lógica de primer orden (es decir, que sea deducible de los axiomas de la lógica de primer orden):
\( \exists x Dem(x,\bar{g})\to Dem(\bar{k}, \bar{g}) \) para algún \( k \).
Esto último es falso, sin duda alguna, pero no es exactamente la formalización del argumento que prueba el primer teorema de incompletitud. Estás hablando de la implicación que parte de "G es demostrable" y llega a \( Dem(\bar{k}, \bar{g}) \) es demostrable. La formalización de la hipótesis es ciertamente \( \exists x Dem(x,\bar{g}) \), como bien dices, pero la formalización de la consecuencia no sería la que indicas (\( Dem(\bar{k}, \bar{g}) \)), sino la sentencia que afirma que existe un \( k \) tal que \( Dem(\bar{k}, \bar{g}) \) es demostrable.
Formalizar esa sentencia requiere un poco de trabajo. Para empezar habría que formalizar la función que a cada número \( k \) le asigna el número de Gödel de \( \bar k \), etc.
O sea, debería valer que: \( \exists x P(x)\to P(\bar{k}) \) para algún \( k \)., Lo que equivale a decir que si \( \exists x P(x) \) es demostrable a partir de los axiomas entonces \( P(a) \) es demostrable para algún \( a \) en el modelo estándar de los axiomas de Peano, hecho que es falso en general. Tal vez sí sea cierto para el caso particular en que \( P(x) \) sea \( Dem(x,\bar{g}) \), pero para probarlo, en caso de que sea cierto, debería apelarse seguramente a la maquinaria de la teoría de modelos, o al menos de la teoría de conjuntos, y ya no queda claro que pueda traducirse a una demostración aritmética formal de primer orden.
No, no es cierto ni en ese caso en particular. Basta tener en cuenta que si una teoría (aritmética recursiva) T es consistente, también lo es T + \( \lnot \) G, luego esta teoría tiene un modelo en el cual existe un \( x \) que demuestra G, es decir, en tal modelo es verdadero \( \exists x Dem(x,\bar{g}) \), pero no existe ningún natural "de verdad" que cumpla \( Dem(\bar k,\bar{g}) \), porque eso significaría que \( G \) es demostrable en T, y no lo es. Como en este modelo se cumple la hipótesis de la implicación que planteas, pero no la conclusión, resulta que dicha implicación no es demostrable.
Otro argumento me fue señalado alguna vez por un lector de “Gödel para Todos” y diría así.
Este argumento me resulta confuso. Quiero decir que no sé muy bien qué pretende probar y bajo qué supuestos.
Hagamos la siguiente deducción “a lo Gödel”:
Hemos probado que \( \sim G\to \sim CON \) es demostrable.
No entiendo lo de "hemos probado". Esto es cierto (como bien dices luego), pero a partir de ahí el segundo teorema de incompletitud es inmediato.
Por otra parte, ya hemos dicho que si un sistema de axiomas no es consistente entonces todo enunciado es demostrable a partir de esos axiomas, y esto puede probarse sintácticamente. Sea \( Q \) un enunciado finitista verdadero cualquiera, luego vale \( \sim CON\to \sim Q \) y este enunciado es demostrable en el sistema (porque su validez es verificable algorítmicamente).
No, no, la afirmación \( \sim CON\to \sim Q \) no es necesariamente válida, luego su validez no es verificable ni algorítmica ni no algorítmicamente.
La hipótesis \( \sim CON \) significa que la teoría considerada es contradictoria, y si eso es cierto, toda afirmación (en particular \( \sim Q \)) es demostrable en la teoría, pero esa implicación no es la que dices. No es "Si la teoría es contradictoria entonces se cumple no Q", sino "Si la teoría es contradictoria en ella se puede demostrar no Q", y la forma de expresar eso no es la implicación que pones, sino \( \sim CON\to \exists x\,\mbox{Dem}(x,\bar q) \), donde \( \bar q \) es el número de Gödel de \( \sim Q \). Lo que sigue a partir de ahí ya no está justificado.
¿Cuál es el error en este razonamiento? Llamo su atención sobre el hecho de que \( \sim G\to \sim CON \) sí es demostrable en el sistema (lo probaremos después), de modo que el error, creo yo, tiene que estar en el modo en que justificamos que \( \sim G\to \sim Q \) es demostrable.
No. El error es que la afirmación que dices que es algorítmicamente demostrable no es siquiera necesariamente verdadera.
Es decir, es falso que si la validez de una demostración aritmética que comienza con \( P \) y termina con \( Q \) es verificable algorítmicamente entonces necesariamente \( P\to Q \) deba ser demostrable en el sistema.
No sé si entiendo bien esta afirmación. Si dices que tenemos una demostración aritmética (entiendo que esto significa una demostración en una teoría aritmética prefijada) que empieza por P y termina con Q, lo que tenemos, es (literalmente) una demostración aritmética de que \( P\to Q \). Entonces no entiendo por qué dices que \( P\to Q \) no es demostrable en el sistema. Si lo entiendo bien, la premisa es exactamente lo mismo que la conclusión que niegas. Si estoy liándome necesitaría que me aclararas el sentido de esta frase.
Por lo tanto, aunque es verdad que \( CON\to G \) es demostrable en el sistema, la justificación que da Gödel para ese hecho no sería correcta.
No veo ninguna relación entre lo anterior y el esbozo de Gödel.
Por otra parte, aunque (supongo) podría probarse el segundo teorema de incompletitud siguiendo las directrices de Gödel, es decir, formalizando literalmente la prueba del primer teorema de incompletitud, cuando uno se pone a hacerlo se da cuenta de que es tediosísimo (y hay que enfrentarse a sutilezas, como formalizar bien la implicación que hemos discutido al principio), pero afortunadamente también se da cuenta de que basta formalizar algunas propiedades del concepto lógico de demostración. Concretamente, basta formalizar las condiciones de Hilbert-Bernays:
http://en.wikipedia.org/wiki/Hilbert%E2%80%93Bernays_provability_conditionsLa única que da guerra es la segunda. A partir de ellas la prueba del segundo teorema de incompletitud es ya muy sencilla.