11 de enero de 2011

Dolor en el estómago y un pequeño ejercicio de lógica


Para distraerme de este intenso dolor de estómago que tengo, escribiré la solución del primer ejercicio del primer capítulo del Gödel's Incompleteness Theorems de Raymond Merrill Smullyan.

Ejercicio. Supóngase que $\mathcal{L}$ es un sistema correcto en el que se cumplen las siguientes condiciones:
  1. El conjunto $D^{\ast}$ es expresable en $\mathcal{L}$.
  2. Para todo predicado $H$, existe un predicado $H'$; tal que para todo número $n$, la proposicón $H'(n)$ es demostrable en $\mathcal{L}$ si y sólo si $H(n)$ es refutable en $\mathcal{L}$.

Demuestra que $\mathcal{L}$ es incompleto.

Se dice que una proposición $X$ es decidible en $\mathcal{L}$ si es demostrable o refutable en $\mathcal{L}$, e indecidible en $\mathcal{L}$ si no. Se dice que un sistema $\mathcal{L}$ es completo si toda proposición es decidible en $\mathcal{L}$, e incompleto si alguna proposición es indecidible en $\mathcal{L}$.

Solución. Como $D^{\ast}$ es expresable en $\mathcal{L}$, existe un predicado $H$ en $\mathcal{L}$ tal que para todo $n$,

$H(n)$ es verdadera $\Leftrightarrow n\in D^{\ast}\Leftrightarrow d(n)\in D$.

Por otro lado, para $H$, existe un predicado $H'$ tal que para todo $n$

$H'(n)$ es demostrable en $\mathcal{L}$ $\Leftrightarrow$ $H(n)$ es refutable en $\mathcal{L}$.

Ahora sea $h'$ el número de Gödel de $H'$. Entonces se tiene para $h'$ que

$H(h')$ es verdadera $\Leftrightarrow d(h')\in D \Leftrightarrow H'(h')$ es demostrable.

Y

$H'(h')$ es demostrable en $\mathcal{L}\Leftrightarrow H(h')$ es refutable en $\mathcal{L}$.

Así que

$H(h')$ es verdadera $\Leftrightarrow H(h')$ es refutable en $\mathcal{L}$.


Pero $\mathcal{L}$ es correcto; por lo tanto, $H(h')$ es falsa y no refutable en $\mathcal{L}$, y, nuevamente, como $\mathcal{L}$ es correcto, y $H(h')$ falsa, se tiene que $H(h')$ no puede ser demostrable en $\mathcal{L}$. Luego, $H(h')$ es indecidible, y, por lo tanto, $\mathcal{L}$ incompleto.

Un ejercicio bastante sencillo. Y el dolor ya se me pasó.

No hay comentarios.: