Los teoremas de incompletitud de Gödel (II)

Preliminares notacionales.

Los términos $0,0\text{'},0\text{'}\text{'},...$, representantes de números naturales, se denominan numerales, y se abrevian simbólicamente: $0,1,2,...$.
Una letra en itálica '$x$' designa un número natural "intuitivo", y la correspondiente itálica en negrita, '$\mathit{x}$', designa al correspondiente numeral $0^{\left(x\right)} (0\text{'}\cdots \text{'})$ (con $x$ acentos).
Ejemplo: "$\mathit{x}+1$" designa a $0^{\left(x\right)}+0\text{'}$.

Sea $P\left(x_1,\cdots ,x_n\right)$ un predicado de la teoría numérica "intuitiva". Decimos que $P\left(x_1,\cdots ,x_n\right)$ es numeralmente expresable si existe una fórmula $\text{P}\left({\text{x}}_1,\cdots ,{\text{x}}_n\right)$, con solo las variables libres ${\text{x}}_1,...,{\text{x}}_n$, tal que $\forall \left(x_1,\cdots ,x_n\right)\in {\mathrm{\mathbb{N}}}^n$, se cumple:

$Si P\left(x_1,\cdots ,x_n\right) es verdadera, entonces ├\text{P}\left({\mathit{x}}_{\mathbf{1}},\cdots ,{\mathit{x}}_n\right)$

y

$Si P\left(x_1,\cdots ,x_n\right) es falsa, entonces ├\neg \text{P}\left({\mathit{x}}_{\mathbf{1}},\cdots ,{\mathit{x}}_n\right)$

En este caso, la fórmula $\text{P}\left({\text{x}}_1,\cdots ,{\text{x}}_n\right)$ expresa numeralmente el predicado $P\left(x_1,\cdots ,x_n\right)$ (con las variables formales ${\text{x}}_1,...,{\text{x}}_n$ correspondientes a las respectivas variables "intuitivas" $x_1,...,x_n$.

El uso metamatemático de esta notación se realizará solo si existe un procedimiento de decisión para el predicado $P\left(x_1,\cdots ,x_n\right)$; luego para cada n-tupla $(x_1,...,x_n)$, se tiene que

$P(x_1,...,x_n)$ es verdadera ó $P(x_1,...,x_n)$ es falsa.

Es decir:

$├\text{P}({\mathit{x}}_1,...,{\mathit{x}}_n) ó ├\neg \text{P}({\mathit{x}}_1,...,{\mathit{x}}_n)$

Esto es: $\text{P}({\mathit{x}}_1,...,{\mathit{x}}_n)$ es decidible para cada $({\mathit{x}}_1,...,{\mathit{x}}_n)$, lo que se expresa diciendo que $\text{P}\left({\text{x}}_1{\text{,...,x}}_n\right)$ es numeralmente decidible. La fórmula $\text{¬P}\left({\text{x}}_1{\text{,...,x}}_n\right)$ expresa numeralmente el predicado $no-P\left(x_1,...,x_n\right)$.

El conjunto de los objetos formales (símbolos del lenguaje, expresiones formales o fbfs, sucesiones finitas de expresiones formales o de fbfs, ...), $\mathbf{\text{OF}}$, es numerable; es decir, existe una aplicación (inyectiva):

$f:\mathbf{\text{OF}}\to \mathrm{\mathbb{N}}$

A dicha aplicación (cuya descripción completa es larga y no expondremos aquí), la llamaremos numeración de Gödel, y al correspondiente número natural de un objeto formal, su número de Gödel, de tal forma que el tipo de números correspondientes a los símbolos formales, las expresiones formales y las sucesiones finitas de expresiones formales son de distinta categoría numérica.

Notaremos mediante ${\text{A}}_n$ a la fórmula cuyo número de Gödel es $n$, y ${\text{A}}_n\left(a\right)$ a la fórmula cuyo número de Gödel es $n$ y con variable libre $a$.

Damos un Lema cuya demostración se omite.

LEMA.- Existe una numeración de Gödel de los objetos formales tal que los predicados:

$A(a,b)$: $a$ es el número de Gödel de una fórmula, ${\text{A}}_a\left(a\right)$, y $b$ es el número de Gödel de una demostración de la fórmula ${\text{A}}_a\left(\mathit{a}\right)$;
y

$B(a,c)$: $a$ es el número de Gödel de una fórmula, ${\text{A}}_a\left(a\right)$, y $c$ es el número de Gödel de una demostración de la fórmula ${\text{¬A}}_a\left(\mathit{a}\right)$;

son numeralmente expresables en el sistema formal.

Consideremos ahora la fórmula

$\forall b \neg \text{A}\left(a,b\right)$

con $a$ como la única variable libre. Sea $p$ el número de Gödel de la fórmula anterior. Entonces $\forall b \neg \text{A}\left(a,b\right)$ es la misma fórmula que ${\text{A}}_p\left(a\right)$.
Consideremos ahora la fórmula ${\text{A}}_p\left(\mathit{p}\right)$: $\forall b\neg \text{A}\left(\mathit{p},b\right)$, que no contiene variables libres ($\mathit{p}$ numeral).

Podemos interpretar la fórmula ${\text{A}}_p\left(\mathit{p}\right)$ heurísticamente, como expresión, desde la perspectiva de la numeración de Gödel, de que la proposición ${\text{A}}_p\left(\mathit{p}\right)$ es indemostrable. Es una fórmula que asegura su propia indemostrabilidad.

DEFINICIÓN.- Un sistema formal se dice (simplemente)consistente si para ninguna fórmula $\text{A}$, tanto $\text{A}$ como $\text{¬A}$ son probables en el sistema.
Un sistema formal se dice $\omega$-consistente si para ninguna variable $x$ y ninguna fórmula $\text{A}\left(x\right)$, todas las metasentencias del conjunto

$├\text{A}\left(0\right),├\text{A}\left(1\right),├\text{A}\left(2\right),\dots ;├\neg \forall x\text{A}\left(x\right)$

son verdaderas. Es decir, si no es posible que $├\text{A}\left(n\right),\forall n\in \mathrm{\mathbb{N}}, y ├\forall x\text{A}\left(x\right)$.

La $\omega$-consistencia implica la consistencia simple.

TEOREMA G.1.- Si el sistema formal de la teoría de números es simplemente consistente, entonces no-$├{\text{A}}_p\left(\mathit{p}\right)$.
Si el sistema formal de la teoría de números es $\omega$-consistente, entonces no-$├\neg {\text{A}}_p\left(\mathit{p}\right)$.

DEMOSTRACIÓN.- Supongamos el sistema consistente y que se verifica $├{\text{A}}_p\left(\mathit{p}\right)$. Es decir, ${\text{A}}_p\left(\mathit{p}\right)$ es probable.
Entonces existe una prueba de ${\text{A}}_p\left(\mathit{p}\right)$. Sea $k$ el número de Gödel de dicha prueba. Entonces $A\left(p,k\right)$ es verdadera. Pero, a su vez, por el Lema, $\text{A}\left(p,k\right)$ es una fórmula que expresa numeralmente a $A\left(p,k\right)$, luego se infiere que $├\text{A}\left(\mathit{p},\mathit{k}\right)$.
Por $\exists$-introducción, se deduce que $├\exists b\text{A}\left(\mathit{p},b\right)$. Luego $├\neg \forall b\neg \text{A}\left(\mathit{p},b\right)$. Pero esto es lo mismo que $├\neg {\text{A}}_p\left(\mathit{p}\right)$.

En consecuencia, nuestra asunción de que $├{\text{A}}_p\left(\mathit{p}\right)$, contradice la hipótesis de la consistencia del sistema. Por reducción al absurdo, se concluye que $no-├{\text{A}}_p\left(\mathit{p}\right)$.

Si el sistema es $\omega$-consistente, entonces $no-├\neg {\text{A}}_p\left(\mathit{p}\right)$.
Es decir, si el sistema es $\omega$-consistente, entonces es (simplemente)incompleto, siendo ${\text{A}}_p\left(\mathit{p}\right)$ una fórmula indecidible.

Por la consistencia y la primera parte de este Teorema, ${\text{A}}_p\left(\mathit{p}\right)$ no es demostrable. Por tanto, ningún número natural $0,1,2,\dots$ es el número de Gödel de una prueba de ${\text{A}}_p\left(\mathit{p}\right)$; esto es

$A\left(p,0\right),A\left(p,1\right),A\left(p,2\right),\dots$

son todas falsas. Por tanto, como $\text{A}\left(a,b\right)$ expresa numeralmente a $A\left(a,b\right)$, se tiene que

$├\neg \text{A}\left(\mathit{p},0\right),├\neg \text{A}\left(\mathit{p},1\right),\neg \text{A}\left(\mathit{p},2\right),\dots$

Ahora, por la $\omega$-consistencia, se tiene que $no-├\neg \forall b\neg \text{A}\left(\mathit{p},b\right)$. Pero eso es equivalente a $no-├\neg {\text{A}}_p\left(\mathit{p}\right)$, como puede verse. Q.E.D.