Primer teorema de la incompletitud de Gödel

El primer teorema de incompletitud de Gödel es un teorema enunciado por el lógico-matemático austríaco Kurt Gödel en 1931, en su artículo Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I (Sobre proposiciones formalmente indecidibles de Principia Mathematica y sistemas relacionados, en español), donde demuestra la indecibilidad de teorías axiomáticas.

Enunciado

El enunciado del teorema puede entenderse sin necesidad de abordar la teoría, y se entiende como sigue:

Cualquier teoría aritmética recursiva que sea consistente es incompleta.

O bien, puede enunciarse más formalmente como:

Sea $T$ una teoría semirrecursiva que interprete a $Q$, en la que no pueda probarse la traducción de ninguna sentencia ${\mathrm{\Sigma }}_1$ de ${ℒ}_a$ que sea falsa en el modelo natural. Entonces la sentencia de Gödel de $T$ no es demostrable ni refutable en $T$.

donde definimos que un lenguaje formal $ℒ$ es recursivo si son recurvas las relaciones $\text{Var}(k)$, $\text{Rel}(k)$ y $\text{Fn}(k)$ que se cumplen, respectivamente, cuando el número $k$ es una variable, un relator o funtor de $ℒ$, así como la función Nar(k) que vale cero excepto sobre relatores y funtores, en los cuales es igual a su número de argumentos.

Una teoría axiomática $T$ es recursiva (respec. semirrecursiva) si el conjunto de sus axiomas (como números naturales) es recursivo (respec. semirrecursivo).

Si $T$ es una teoría semirrecursiva que interprete a $Q$, podemos considerar la fórmula $\psi (\alpha )\equiv \mathrm{\neg }\underset{⌜T⌝}{⊢}\alpha$, así como su traducción a $ℒ$. Además, existe una sentencia aritmética $G$ del lenguaje $ℒ$ de $T$ tal que $\underset{T}{⊢}(G⟷\mathrm{\neg }\underset{⌜T⌝}{⊢}⌜G⌝).$ A cualquier sentencia que cumpla esta propiedad se le denomina sentencia de Gödel para la teoría $T$.

Demostración

Por hipótesis hay fórmulas no demostrables en $T$, luego podemos suponer que $T$ es consistente. Queremos probar que si $T$ es semirrecursiva, consistente y extiende a $Q$, entonces las sentencias de Gödel de $T$ no son demostrables en $T$.

En efecto, si $\underset{T}{⊢}G$ entonces $\underset{Q}{⊢}\underset{⌜T⌝}{⊢}⌜G⌝$, luego $\underset{T}{⊢}\underset{⌜T⌝}{⊢}⌜G⌝$, donde la última fórmula es traducción a $ℒ$ de la anterior, luego, por definición de sentencia de Gödel, $\underset{T}{⊢}\mathrm{\neg }G$, y resulta que $T$ es contradictoria.

Así, $G$ no es demostrable, luego $\mathbb{N}\models \mathrm{\neg }\underset{⌜T⌝}{⊢}⌜G⌝$. así la traducción a $ℒ$ de esta sentencia no es demostrable en $T$, pero por definición de sentencia de Gödel tal traducción es equivalente a $G$ en $T$, por lo tanto en las hipótesis del teorema $G$ no es demostrable en $T$.

Véase también

• Teoremas de incompletitud de Gödel
• Segundo teorema de incompletitud de Gödel
• Completitud

Referencias

• Gödel, Kurt (1931). Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik (38): 173-198. doi:10.1007/BF01700692

• Gödel, Kurt (1962). On Formally Undecidable Propositions of Principia Mathematica and Related Systems. (Bernard Meltzer, trad.). Basic Books. ISBN 0-486-66980-7.