Prueba del Teorema de la INCOMPLETITUD de Gödel

Lo prometido es deuda

... y vuelvo a prometer algo más de Douglas R. Hofstadter y su libro (tocho) que ganó el Premio Pulitzer de ensayo en 1980: Gödel, Escher, Bach: un Eterno y Grácil Bucle. Ya conté en la entrada correspondiente que fue quien en la revista Investigación y Ciencia presentó al mundo el famoso Cubo de Rubik.

TEOREMA.- Si L es una lógica aritmética ω-consistente y adecuada, entonces L es incompleta.

DEFINICIONES:

L es ω-consistente si ∄ una fbf (fórmula bien formada) W-1aria | tal que,
∀ m (entero), Th(L): W(m^*) y también Th(L): ~(x_i)W
L es adecuada, si ∀ Q, conjunto recursivamente numerable, ∃ un predicado R(x,y) totalmente representable en L | tal que:
Q = { x | existe, y | R(x,y) es verdadero }
L es completa si toda fbf A de L, se tiene
Th(L): A o bien Th(L): ~A

* ver en wikipedia: fbf

DEMOSTRACION DEL TEOREMA:

Se elige Q recursivamente numerable y no recursivo.
Puesto que L es adecuada ∃ R(x,y) totalmente representable en L | tal que:
Q = { x | existe, y | R(x,y) es verdadero } Así pues ∃ una fbf W-2aria, tal que cuando R(x,y) es verdadero,
Th(L): W(x^*,y^*)
Cuando R(x,y) es falso,
Th(L): ~W(x^*,y^*)
Sea U la fbf 1-aria (∃x₂)W. Veremos que
Q = {x | Th(L): U(x^*)}
Para cada entero n, escribimos W(n^*,x₂) para S(W,x₁,n^*)

Supongamos que n₀ ∈ Q, entonces para algún número y₀, R(n₀,y₀)
Por 1.)
Th(L): [W(n₀^*,y₀^*) ⊃ (∃x₂)W(n₀^*,x₂)]
Th(L): (∃x₂)W(n₀^*,x₂)
Th(L): U(n₀^*)

Supongamos que Th(L): U(n₀^*)

Esto es, Th(L): (∃x₂)W(n₀^*,x₂)
o bien, Th(L): ~(x₂) ~ W(n₀^*,x₂)

Así por 1) ∃ un numero entero m₀ para el cual la fbf ~W(n₀^*,m₀^*) no es un teorema de L. Por tanto R(n₀,m₀) tiene que ser cierto puesto que si fuera falso tendríamos Th(L) ~W(n₀^*,m₀^*). Finalmente, n₀ ∈ Q y hemos demostrado Q = {x | Th(L): U(x^*}

Sopongamos ahora que Th(L) ~U(n^*). Entonces n ∈ Q̅
ya que si n ∈ Q, Th(L): U(n^*) lo que contradice la consistencia de L. Así pues,
{x | Th(L): ~U(x^*)} es un subconjunto ⊂ Q̅
Pero por el corolario:

Si Q es recursivamente numerable pero no recursivo, entonces ninguna lógica recursiva es completa con respecto a Q. {x | Th(L): ~U(x^*)} = Q̅
puesto que Q̅ no es recursivamente numerable. Por eso existe un numero ∃n₀ | n₀ ∊ Q̅, para el cual no se cumple que Th(L): ~U(n₀^*)
Por otra parte tampoco se cumple que Th(L): U(n₀^*) puesto que de cumplirse implicaría que n₀ ∊ Q.
Por tanto U(n₀^*) y ~ U(n₀^*) no son decidibles en L y por tanto L es incompleta, como queda demostrado.
- Consideremos ~U(n₀^*). En virtud del TEOREMA hay que interpretarla como n₀ ∊ Q̅, de modo que es un enunciado verdadero. Pero no es un Teorema de L. O sea que si L es ω-consistente, existe un enunciado verdadero que no puede demostrarse en L, aunque añadamos U(n₀^*) a la lista de axiomas, puesto que el nuevo L' está igualmente sometido al Teorema de Gödel.