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 $\Sigma _{1}$ de ${\mathcal {L}}_{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 ${\mathcal {L}}$ 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 ${\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 $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 ${\displaystyle \psi (\alpha )\equiv \neg {\underset {\ulcorner T\urcorner }{\vdash }}\alpha }$, así como su traducción a ${\mathcal {L}}$. Además, existe una sentencia aritmética $G$ del lenguaje ${\mathcal {L}}$ de $T$ tal que ${\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 $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}{\vdash }}G$ entonces ${\displaystyle {\underset {Q}{\vdash }}{\underset {\ulcorner T\urcorner }{\vdash }}\ulcorner G\urcorner }$, luego ${\displaystyle {\underset {T}{\vdash }}{\underset {\ulcorner T\urcorner }{\vdash }}\ulcorner G\urcorner }$, donde la última fórmula es traducción a ${\mathcal {L}}$ de la anterior, luego, por definición de sentencia de Gödel, ${\displaystyle {\underset {T}{\vdash }}\neg G}$, y resulta que $T$ es contradictoria.

Así, $G$ no es demostrable, luego ${\displaystyle \mathbb {N} \models \neg {\underset {\ulcorner T\urcorner }{\vdash }}\ulcorner G\urcorner }$. así la traducción a ${\mathcal {L}}$ 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.

• Datos: Q62091930