Los teoremas de incompletitud de Gödel (I)

Consideremos un computador (y su correspondiente programa), que podemos denominar máquina lógica o, simplemente, máquina, capaz de imprimir expresiones (cadenas o sucesiones finitas de símbolos gráficos) compuestas de los símbolos siguientes

$~ P N ( )$

DEFINICIONES.- Denominamos expresión a toda cadena finita, no vacía, formada por (algunos o todos) de los símbolos anteriores. Una expresión se dice imprimible si la máquina puede imprimirla.
Por norma de una expresión cualquiera $X$, entendemos la expresión $X\left(X\right)$.
Ejemplo: la norma de $~PN$
es $~PN\left(~PN\right)$ .
Por enunciado significamos una expresión de una de las cuatro formas siguientes:

$\begin{array}{cc}\left(1\right)& P\left(X\right)\\ \left(2\right)& PN\left(X\right)\\ \left(3\right)& ~P\left(X\right)\\ \left(4\right)& ~PN\left(X\right)\end{array}$

Siendo $X$ una expresión cualquiera.

Informalmente, la interpretación es la siguiente: $P$ significa "imprimible"; $N$, "norma de", y $~$, "no".

Concepto de verdad de un enunciado.

Sea $X$ una expresión cualquiera.

 Decimos que $P\left(X\right)$ es verdadera si y solo si $X$ es imprimible.
Decimos que $PN\left(X\right)$ es verdadera, si y solo si la norma de $X$ es imprimible.
Decimos que $~P\left(X\right)$ es verdadera, si y solo si $X$ no es imprimible.
Decimos que $~PN\left(X\right)$ es verdadera si y solo si la norma de $X$ no es imprimible.

En lo antedicho se ha dado una definición precisa de "enunciado verdadero" y de "verdad de un enunciado". Además, tenemos un interesante caso de autorreferencia: la máquina imprime enunciados referidos a los enunciados que la máquina puede o no imprimir, de manera que describe su propio comportamiento.

Supondremos, por hipótesis, que todos los enunciados que imprime la máquina son verdaderos. Ejemplo: Si imprime $P\left(X\right)$, entonces $X$ es efectivamente imprimible; si imprime $PN\left(X\right)$, entonces la norma de $X$ es efectivamente imprimible.

Ahora bien, si suponemos $X$ imprimible, ¿es $P\left(X\right)$ imprimible? No necesariamente. Si $X$ es imprimible, entonces $P\left(X\right)$ es verdadero; pero no consideramos la hipótesis de que la máquina imprime todos los enunciados verdaderos, sino que no puede imprimir alguno falso. Además, puede imprimir expresiones que no sean enunciados.

PROPOSICIÓN 1.- Existe un enunciado tal que ni él ni su negación son imprimibles.

Demostración.- Sea el enunciado $~PN(~PN)$. Por definición de "verdad", este enunciado es verdadero si y solo si la norma de $~PN$ no es imprimible.
Pero la norma de $~PN$ es el enunciado $~PN(~PN)$. Luego $~PN(~PN)$ es verdadero si y solo si $~PN(~PN)$ no es imprimible.
Ahora bien, si $~PN(~PN)$ fuese falso, entonces, por lo antexpuesto, $~PN(~PN)$ sería imprimible, lo que contradice la hipótesis que afirma la imposibilidad de impresión de enunciados falsos, por la máquina.
En consecuencia, $~PN(~PN)$ es verdadero y, por lo tanto, no imprimible.

Ahora bien, el enunciado $PN(~PN)$ es falso (pues su negación es verdadera). Por lo tanto, $PN(~PN)$ no es imprimible (por la hipótesis de inimprimibilidad de enunciados falsos).
En conclusión: Ni $PN(~PN)$, ni $~PN(~PN)$ son imprimibles. Q.E.D.

Mutatis mutandis, si en lugar de un sistema computador-programa hablamos de un Sistema Deductivo en el lenguaje formal generado por los cinco símbolos citados, reinterpretando la letra $P$ como "probable(demostrable)" en el sistema, en lugar de como imprimible, y con la hipótesis análoga de que el sistema es consistente (esto es, no puede demostrar enunciados falsos), entonces el enunciado $~PN(~PN)$ será verdadero e indemostrable en el sistema. E igualmente el enunciado $PN(~PN)$.

Luego estamos en presencia de un enunciado indecidible en el sistema: ni él ni su negación son demostrables (son teoremas) en el (del) sistema.


Consideremos, ahora, otro computador que imprime expresiones formadas por los símbolos

$~ P N 1 0$

Representemos ahora los símbolos anteriores en notación binaria, asignando a cada símbolo un número binario e identificándolo con él:

$\begin{array}{cc}~& 10\\ P& 100\\ N& 1000\\ 1& 10000\\ 0& 100000\end{array}$

A cada expresión le asociamos un número: su número de Gödel de la expresión, según la correspondencia anterior. El número de Gödel de una expresión compuesta se obtiene reemplazando cada símbolo de dicha expresión por su número de Gödel, y concatenando todos los números de Gödel obtenidos. Ejemplo: $PNP$ tiene como número de Gödel $1001000100$.
Redefinimos la norma de una expresión como "la expresión misma seguida de su número de Gödel". Ejemplo. La norma de $PNP$ es $PNP$$1001000100$.
Un enunciado será ahora una expresión de una de las cuatro formas siguientes: $PN,PNX,~PX,~PNX$, donde $X$ es un número binario cualquiera.
Diremos ahora que:

$PX$ es verdadera si y solo si $X$ es el número de Gödel de una expresión imprimible.
$PNX$ es verdadera si y solo si $X$ es el número de Gödel de una expresión cuya norma es imprimible.
$~PX$ es verdadera si y solo si $PX$ no es verdadera ($X$ no es el número de Gödel de una expresión imprimible).
$~PNX$ es verdadera si y solo si $PNX$ no es verdadera ($X$ no es el número de Gödel de una expresión cuya norma es imprimible).

Como hipótesis admitimos la siguiente: La máquina no imprime nunca un enunciado falso.

Entonces, se verifica:

PROPOSICIÓN 1'.- Existe un enunciado verdadero que no puede imprimir la máquina.

Demostración.- Es una sencilla comprobación el ver que el enunciado $~PN101001000$ es verdadero y no imprimible. Q.E.D.

Las anteriores Proposiciones son modelos simples del Primer Teorema de Incompletitud de Gödel, que enunciaremos y demostraremos más adelante. La Proposición 1' nos conduce, además, al método de demostración de Gödel, por numeración de objetos formales, que el gran lógico empleó para la demostración de su Segundo Teorema de Incompletitud, el cual enunciaremos y demostraremos, en una versión simplificada, más adelante también.