Teorema (Gödel, 1931): Si un sistema recursivo de axiomas para la aritmética verifica que:
1) Es omega-consistente.
2) Todo enunciado finitario es demostrable.
Entonces el sistema es incompleto, es decir, existe un enunciado P tal que ni P ni -P son demostrables en el sistema.Aquí, finalmente, el Teorema de Gödel. Antes de adentrarnos en la demostración conviene detenerse en algunas reflexiones.
1. El enunciado original de Gödel no es exactamente el que he dado más arriba. En su artículo de 1931 Gödel da algunos axiomas que garantizan la hipótesis de que todo enunciado finitario sea demostrable (en particular, incluía el esquema de inducción, que es el axioma 7 de la lista de axiomas de Peano que dí antes) y el enunciado de Gödel habla de todo sistema de axiomas que contenga a esos que él dio.
El enunciado que yo he dado parece "mejor" en el sentido de que se pide una condición más general, que incluye a más sistemas que el de Gödel (pues puede haber sistemas en los que todo enunciado finitario sea demostrabe, pero que no incluya todos los axiomas dados por Gödel). El de Gödel es, por otra parte, mejor en el sentido siguiente: el enunciado del teorema que yo he dado deja abierta la pregunta ¿habrá algún sistema recursivo de axiomas que cumpla que todo enunciado finitario sea demostrable? Gödel responde a esa cuestión dando explícitamente un tal sistema.
2. En 1936 John B. Rosser modificó la demostración de Gödel de modo que el teorema se transformó en:
Teorema (Rosser, 1936): Si un sistema recursivo de axiomas para la aritmética verifica que:
1) Es consistente.
2) Todo enunciado finitario es demostrable.
3) Todo enunciado de la forma \( \forall{x}(x\leq{n}\vee n\leq{x}) \) es demostrable, donde n es un numeral cualquiera y \( x\leq{y} \) debe tomarse como una abreviatura de \( \exists{z}(x + z = y) \).
4) Todo enunciado de la forma \( \forall{x}(x\leq{n}\Rightarrow (x=0 \vee \ldots \vee x = n)) \) es demostrable, donde n es un numeral cualquiera.
Entonces el sistema es incompleto, es decir, existe un enunciado P tal que ni P ni -P son demostrables en el sistema.(La diferencia esencial es que se cambia "omega-consistente" por "consistente".)
En la versión original de Rosser las hipótesis 2), 3) y 4) se reemplazan por el hecho de que el sistema contiene los axiomas propuestos por Gödel. Los enunciados mencionados en 3) y 4) no son finitarios en el sentido que hemos definido (verificables en una catidad finita de pasos), pero sí lo son en el sentido más amplio que usaba Hilbert ("intuitivamente verdaderos").
3. Se puede probar además que existe un enunciado P cuyo significado se puede interpretar como: "el sistema de axiomas es consistente" y que es indecidible (es decir, ni P ni -P son demostrable en el sistema). Ésta afirmación es el llamado Segundo Teorema de Gödel.
4. Panu Raatikainen, en un paper sobre las consecuencias filosóficas del Teorema de Gödel, escribe:
"It is widely thought that Gödel’s theorems gave a death blow to Hilbert’s program. Whether Gödel’s theorems really demonstrated that it is impossible to carry out Hilbert’s program is controversial. This is partly because there is not complete clarity as to what exactly constitutes Hilbert’s program, and what views are truly essential for it. Furthermore, some of Hilbert’s key concepts are somewhat vague. Nevertheless, I think that there are good reasons to think that Hilbert's mature program of the 1920s was, in its original form and in its full generality, refuted by Gödel’s theorems."
Es decir, es controvertido si el teorema de Gödel refuta el Programa de Hilbert, en parte porque no queda claro cuáles eran los conceptos clave de ese programa.
Creo que Panu se refiere a la idea a la de Hilbert de incluir dentro de la categoría de "finitarios" a los enunciados "intuitivamente evidentes" (Gödel intenta años después formalizar esta idea en su artículo "Sobre una extensión del punto de vista finitario"). Si por "finitario" (como hemos hecho aquí, y como se hace habitualmente) entendemos "verificable mecánicamente" entonces me parece que sí, que el Teorema de Gödel anula la posibilidad de completar el Programa de HIlbert.
5. Conviene observar que no toda teoría es incompleta. Por ejemplo, si del lenguaje eliminamos la operación de multiplicación (y dejamos sólo S y la suma) entonces la teoría así obtenida admite un sistema recursivo y completo de axiomas (Presburger, 1929).