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.[1]

O bien, puede enunciarse más formalmente^[2] como:

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

donde definimos que un lenguaje formal ${\displaystyle {\mathcal {L}}}$ es recursivo si son recurvas las relaciones ${\displaystyle {\text{Var}}(k)}$, ${\displaystyle {\text{Rel}}(k)}$ y ${\displaystyle {\text{Fn}}(k)}$ que se cumplen, respectivamente, cuando el número ${\displaystyle k}$ es una variable, un relator o funtor de ${\displaystyle {\mathcal {L}}}$, 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 ${\displaystyle T}$ es recursiva (respec. semirrecursiva) si el conjunto de sus axiomas (como números naturales) es recursivo (respec. semirrecursivo).

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

Demostración

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

En efecto, si ${\displaystyle {\underset {T}{\vdash }}G}$ entonces ${\displaystyle {\displaystyle {\underset {Q}{\vdash }}{\underset {\ulcorner T\urcorner }{\vdash }}\ulcorner G\urcorner }}$, luego ${\displaystyle {\displaystyle {\underset {T}{\vdash }}{\underset {\ulcorner T\urcorner }{\vdash }}\ulcorner G\urcorner }}$, donde la última fórmula es traducción a ${\displaystyle {\mathcal {L}}}$ de la anterior, luego, por definición de sentencia de Gödel, ${\displaystyle {\displaystyle {\underset {T}{\vdash }}\neg G}}$, y resulta que ${\displaystyle T}$ es contradictoria.

Así, ${\displaystyle G}$ no es demostrable, luego ${\displaystyle {\displaystyle \mathbb {N} \models \neg {\underset {\ulcorner T\urcorner }{\vdash }}\ulcorner G\urcorner }}$. así la traducción a ${\displaystyle {\mathcal {L}}}$ de esta sentencia no es demostrable en ${\displaystyle T}$, pero por definición de sentencia de Gödel tal traducción es equivalente a ${\displaystyle G}$ en ${\displaystyle T}$, por lo tanto en las hipótesis del teorema ${\displaystyle G}$ no es demostrable en ${\displaystyle T}$.

Véase también

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