Posterior: El teorema de Goodstein Arriba: Irresolubilidad en la Aritmética Anterior: Aritmética de Peano

Incompletitud

Veremos aquí que la aritmética de Peano no es completa. Para esto, codificaremos a la aritmética dentro de la misma aritmética y propondremos un enunciado tal que ni él ni su negación son demostrables en AP. Para cada $n\in{\mathbb{N}}$ construímos el $n$-ésimo numeral como $\mbox{\bf n}=s^n(0)=\underbrace{s(\cdots s(}_{n\mbox{\scriptsize veces}}0)\cdots )$. Una relación $A\subset{\mathbb{N}}^k$ se dice representable en AP si existe una fórmula bien formada $\phi_A(x_1,\ldots,x_k)$ tal que para cualesquiera $n_1,\ldots,n_k\in{\mathbb{N}}$ se tiene que rigen las implicaciones

$$\begin{eqnarray*} (n_1,\ldots,n_k)\in A &\rightarrow& \mbox{\it AP}\vdash \phi_... ...\it AP}\vdash \neg\phi_A(\mbox{\bf n}_1,\ldots,\mbox{\bf n}_k) \end{eqnarray*}$$

Una función ${\mathbb{N}}^{n}\rightarrow{\mathbb{N}}$ es representable si su gráfica lo es. El concepto de demostrabilidad es muy algorítmico, por lo cual una demostración puede verse como un método de cálculo o de comprobación. Así pues, el resultado siguiente aparece de manera muy natural, aunque en este texto omitiremos su demostración.

Teorema 5.1 (Gödel)   Una función es representable si y sólo si es recursiva. Una relación es representable si y sólo si es recursiva.

Ahora, es evidente que el conjunto de fórmulas bien formadas es efectivamente numerable, y cualquiera de los métodos ya vistos de enumeración basta para corroborar esta afirmación. De manera alternativa, sin embargo, podríamos introducir la enumeración $g$ que se muestra en la tabla 3.8. Ahí observamos que los símbolos del alfabeto quedan codificados por números impares, todas las cadenas por números pares divisibles por una potencia impar de 2 y todas las cadenas de cadenas por números pares divisibles por una potencia par de 2.

Table 3.8: Enumeración de Gödel.

Definamos las siguientes relaciones en ${\mathbb{N}}$:

1. $\mbox{\it Fbf}$ (Fórmula bien formada):
   
   $$\mbox{\it Fbf}(n)\ \Leftrightarrow\ \exists \phi\mbox{\rm FbF}:n=g(\phi)$$
   
   

2. $\mbox{\it AxL}$ (Axioma lógico):
   
   $$\mbox{\it AxL}(n)\ \Leftrightarrow\ \exists \phi\mbox{\rm FbF}:(\phi\mbox{\rm axioma l\'ogico})\land (n=g(\phi))$$
   
   

3. $\mbox{\it AxP}$ (Axioma propio):
   
   $$\mbox{\it AxP}(n)\ \Leftrightarrow\ \exists \phi\mbox{\rm Fbf}:(\phi\mbox{\rm axioma propio})\land (n=g(\phi))$$
   
   

4. $\mbox{\it Demos}$ (Demostración):
   
   $$\mbox{\it Demos}(n)\ \Leftrightarrow\ \exists \Delta\in(\mbox{\rm Fbf})^*:(\Delta\mbox{\rm demostraci\'on})\land (n=g(\Delta))$$
   
   

5. $\mbox{\it Dmble}$ (Demostrable):
   
   $$\begin{array}{rcl} \mbox{\it Dmble}(n) &\Leftrightarrow\ \e... ...l m\'aximo primo que divide a $m$)\end{minipage}} \end{array}$$
   
   

6. $\mbox{\it Sust}$ (Sustitución):
   
   $$\mbox{\it Sust}(m,n,p,q)\ \Leftrightarrow\ \exists \phi,x,t:\... ...(x),q=g(t)$, y \\ $m=g(\phi(x\leftarrow t))$. \end{minipage}}$$
   
   

7. $\mbox{\it Inst}$ (Instanciación):
   
   $$\mbox{\it Inst}(m,n)\ \Leftrightarrow\ \exists \phi(x):n=g(\phi(\mbox{\bf m})).$$
   
   

8. $\mbox{\it Cump}$ (Cúmplese):
   
   $$\mbox{\it Cump}(m,n)\ \Leftrightarrow\ \exists \Delta,\phi(x)... ... de $\phi(\mbox{\bf m})$, y \\ $n=g(\Delta)$. \end{minipage}}$$
   
   

Proposición 5.1   Las relaciones anteriores son todas recursivas y por ende son representables en AP.

Utilizaremos los mismos nombres para denotar a los predicados que representan a esas relaciones. Tenemos entonces que para cualesquiera $m,n\in {\mathbb{N}}$ se cumplen las equivalencias siguientes:

$$\begin{array}{lcl} \mbox{\it AP}\vdash \mbox{\it Cump}(\mbox... ...para ninguna f\'ormula $\phi(x)$. \end{minipage}} \end{array}$$

Hagamos

$$\alpha_1(x_1) \equiv \forall x_2(\neg\mbox{\it Cump}(x_1,x_2)... ...nciado'' de la forma $\phi(x_1)$ es demostrable,\end{minipage}}$$

y sean $p=g(\alpha_1(x_1))$ y $\alpha \equiv \alpha_1(\mbox{\bf p})$. Se ve pues que $\alpha$ asegura que ningún enunciado de la forma $\phi(\mbox{\bf p})$ es demostrable, en particular, para $\phi=\alpha_1$, asevera que $\alpha_1(\mbox{\bf p})$ no es demostrable, es decir, que $\alpha$ mismo no es demostrable. En otras palabras $\alpha$ es un enunciado que se refiere a sí mismo y asevera su propia indemostrabilidad. De aquí resulta que si AP fuese consistente, entonces $\mbox{\it AP}\not\vdash \alpha$. Una teoría $T$, que posea un modelo que incluya a ${\mathbb{N}}$, es CONSISTENTE- si para cualquier fórmula $\phi(x)$, dado que para cada $n\in{\mathbb{N}}$ se tuviera que $T\vdash\phi(\mbox{\bf n})$ entonces necesariamente $T\not\vdash\neg\forall x:\phi(x)$. Se observa que si $T$ es consistente-$\omega$ entonces es también consistente, a secas. Si AP fuese consistente-$\omega$, entonces $\mbox{\it AP}\not\vdash \neg\alpha$. Con todo esto se tiene el

Teorema 5.2 (Primero de Incompletitud de Gödel)   Si AP fuese
consistente-$\omega$ entonces ha de ser incompleta.

Vemos muchas semejanzas entre este teorema de incompletitud y el problema de la parada de máquinas de Turing. En última instancia, las imposibilidades aseveradas por ellos se demuestran utilizando mecanismos autoreferentes. Por otro lado, la capacidad de construir esos mecanismos se debe a sus propios niveles de expresividad y a sus características procedimentales. Concluímos esta sección presentando el

Teorema 5.3 (Segundo de Incompletitud de Gödel)   En AP no
puede demostrarse su propia consistencia.

De manera muy resumida, tenemos los hechos siguientes: 1. Si $H$ es un conjunto inconsistente de fórmulas bien formadas entonces la teoría de $H$, $\mbox{\it Teor\'\i a}(H)$, coincide con el conjunto de todas las fórmulas bien formadas. En otras palabras, en una teoría inconsistente cualquier cosa es demostrable.

2. Un enunciado $\phi$, con número de Gödel $n=g(\phi)$, es demostrable en AP si y sólo si $\mbox{\it AP}\vdash \mbox{\it Dmble}(\mbox{\bf n})$ y es indemostrable en AP si y sólo si $\mbox{\it AP}\vdash \neg \mbox{\it Dmble}(\mbox{\bf n})$.

3. En AP se puede mostrar que $0$ es distinto a $1=s(0)$. La negación de esta desigualdad es $\phi_0\equiv 0=s(0)$. Así pues, tendremos que AP es consistente si y sólo si no se puede demostrar $\phi_0$. Sea pues $n_0=g(\phi_0)$ y sea $\mbox{\it Con}\equiv \neg \mbox{\it Dmble}(\mbox{\bf n}_0)$. El Segundo Teorema de Incompletitud de Gödel equivale a mostrar que, en efecto, $\mbox{\it AP}\not\vdash \neg \mbox{\it Dmble}(\mbox{\bf n}_C)$, donde $n_C=g(\mbox{\it Con})$.

3. De acuerdo con la regla modus ponens, si $n_{12}=g(\phi_1\rightarrow\phi_2)$, $n_{1}=g(\phi_1)$ y $n_{2}=g(\phi_2)$ entonces

$$\mbox{\it AP}\vdash (\mbox{\it Dmble}(\mbox{\bf n}_{12})\land... ...mbox{\bf n}_{1})\rightarrow \mbox{\it Dmble}(\mbox{\bf n}_{2}))$$

5. Además tenemos que todo lo demostrable es demostrablemente demostrable, es decir, si $n_{1}=g(\phi_1)$ y $n_{2}=g(\mbox{\it Dmble}(\mbox{\bf n}_{1}))$ entonces

$$\mbox{\it AP}\vdash (\mbox{\it Dmble}(\mbox{\bf n}_{1})\rightarrow \mbox{\it Dmble}(\mbox{\bf n}_{2}))$$

6. Por todo lo anterior, para probar el Segundo Teorema de Incompletitud basta ver que $\mbox{\it Con}$ es demostrablemente equivalente en AP al enunciado $\alpha$ demostrado indemostrable en el Primer Teorema de Incompletitud. Utilicemos la notación $\phi(\lceil\xi\rceil)$ para denotar a la fórmula $\phi(\mbox{\bf n})$ donde $n=g(\xi)$. Esquemáticamente tenemos: Veamos primero $\mbox{\it AP}\vdash \alpha\rightarrow \mbox{\it Con}$:

$$\begin{eqnarray*} \mbox{\it AP}\vdash (0=s(0))\rightarrow \alpha &\Rightarrow& ... ...ightarrow& \mbox{\it AP}\vdash \alpha\rightarrow \mbox{\it Con} \end{eqnarray*}$$

pues $\mbox{\it AP}\vdash \alpha\rightarrow \neg\mbox{\it Dmble}(\lceil \alpha \rceil)$. Recíprocamente, veamos $\mbox{\it AP}\vdash \mbox{\it Con}\rightarrow \alpha$:

$$\begin{eqnarray*} & & \mbox{\it AP}\vdash \mbox{\it Dmble}(\lceil \alpha \rceil... ...ightarrow& \mbox{\it AP}\vdash \mbox{\it Con}\rightarrow \alpha \end{eqnarray*}$$

$\quad\Box$
Posterior: El teorema de Goodstein Arriba: Irresolubilidad en la Aritmética Anterior: Aritmética de Peano