¿Existe una demostración del Teorema de Incompletitud de Gödel sin enunciados autorreferenciales?

Question

Para la demostración del Teorema de Incompletitud de Gödel, la mayoría de las versiones de demostración utilizan básicamente enunciados autorreferenciales.

Mi pregunta es, ¿qué pasa si uno argumenta que el Teorema de Incompletitud de Gödel sólo importa cuando una fórmula hace posible la autorreferencia?

¿Existe alguna prueba del Teorema de Incompletitud que no se base en afirmaciones autorreferenciales?

Answer 1

He aquí un argumento teórico de computabilidad directa. Supongamos que $T$ es una teoría "apropiada". Dejemos que $A,B$ sean dos conjuntos de c.e. conjuntos, y dejemos que $A_T=\{x: T\vdash x\in A\}$ y $B_T=\{x:T\vdash x\not\in A\}$ . Cada $A_T$ y $B_T$ es c.e. por definición; ya que $T$ está completo tenemos $A_T\sqcup B_T=\mathbb{N}$ y, por tanto, cada uno de ellos es computable; y como $T$ es "apropiado" tenemos $A\subseteq A_T$ y $B\subseteq B_T$ . Pero esto nos da una contradicción: basta con tomar $A,B$ para ser un par de computacionalmente inseparable c.e. sets.

Por supuesto, ¿cómo sabemos que existen conjuntos c.e. computables e inseparables? Bueno, esto a su vez es un truco sencillo con una máquina de Turing universal: establecemos $$A=\{e:\varphi_e(e)\downarrow =0\}\quad\mbox{and}\quad B=\{e:\varphi_e(e)\downarrow=1\}.$$ Por definición, $A$ y $B$ son conjuntos c.e. disjuntos (y nótese que si $\varphi_e(e)\uparrow$ entonces $e$ no está en $A$ ou $B$ ).

Supongamos ahora que $C$ fuera un separador computable para $A$ y $B$ eso es, $C$ es computable, $A\subseteq C$ y $B\cap C=\emptyset$ . Sea $\varphi_c$ sea la función característica total computable de $C$ - es decir, $$C=\{x:\varphi_c(x)\downarrow=1\}.$$ Ahora tenemos dos casos:

• Si $c\in C$ entonces $\varphi_c(c)=1$ . Pero entonces tenemos $c\in B$ contradiciendo la suposición de que $C\cap B=\emptyset$ .

• Si $c\not\in C$ entonces $\varphi_c(c)=0$ . Pero entonces tenemos $c\in A$ contradiciendo la suposición de que $A\subseteq C$ .

Tenga en cuenta que, fundamentalmente, " $\varphi_c(c)\uparrow$ " es no una opción - ya que $\varphi_c$ es total.

---

No hay autorreferencia en absoluto: lo más cerca que estamos es en el paso de verificación de nuestra construcción de conjuntos c.e. inseparables computacionalmente, pero eso no es realmente autorreferencia (alimentar un objeto existente con su propio "nombre" es diferente de construir un objeto que de alguna manera "conoce su propio nombre de antemano"). Esto es exactamente el la diagonalización frente a la autorreferencia punto.