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:
- El conjunto $D^{\ast}$ es expresable en $\mathcal{L}$.
- 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.:
Publicar un comentario