6.2: El lema de autorreferencia

Nuestro objetivo en esta sección es mostrar que, dada cualquier fórmula con una sola variable libre, podemos construir una oración que afirme que la fórmula dada se aplica a sí misma. Antes de hacer eso, sin embargo, necesitamos un lema.

Sin duda (!) recordar de la Sección 5.9 que tenemos la función representable\(\text{Num} : \mathbb{N} \rightarrow \mathbb{N}\) tal que\(\text{Num} \left( n \right) = \ulcorner \bar{n} \urcorner\). Tenemos una\(\Delta\) -fórmula,\(Num \left( x, y \right)\), que representa la relación representable\(\text{Num}\). Nos encantaría saber que\(N\) es lo suficientemente fuerte como para probar, por ejemplo, la\(\mathcal{L}_{NT}\) -fórmula

\[Num \left( \bar{3}, y \right) \leftrightarrow y = \overline{\text{Num} \left( 3 \right)}.\]

Chaf: No te confundió el uso de\(\text{Num} \left( 3 \right)\), ¿verdad? Puede ser confuso ya que\(\text{Num}\) es un conjunto, y\(\text{Num} \subseteq \mathbb{N}^2\). Pero sabemos que\(\text{Num}\) es una función y así lo que se nombra\(\text{Num} \left( 3 \right)\) es el elemento único\(y\) del codominio\(\mathbb{N}\) tal que el par ordenado\(\left( 3, y \right) \in \text{Num}\). Eso era obvio, ¿verdad?

Desafortunadamente, aunque querer que la equivalencia mostrada sea demostrable en\(N\) es eminentemente razonable, no podemos hacerlo del todo. El problema es que nuestra fórmula no\(Num\) es lo suficientemente complicada. El lema que vamos a declarar dará este resultado para cualquier función representable, por lo que lo vamos a exponer en esa generalidad. Para nuestros efectos, sin embargo, bastará con saber que se aplica a las funciones representables\(\text{Num}\) y\(\text{Sub}\) de la Sección 5.9.

lema 6.2.1.

Supongamos que\(\text{R} \subseteq \mathbb{N}^{n+1}\) es un conjunto representable representado (in\(N\)) por la\(\mathcal{L}_{NT}\) fórmula\(R\) -. Si\(\text{R}\) es una función con dominio\(\mathbb{N}^n\) y codominio\(\mathbb{N}\), entonces hay una fórmula\(Rf\) tal que

1. \(Rf\)representa\(\text{R}\), y
2. para cualquier\(a_1, \ldots, a_n \in \mathbb{N}\),
   \[N \vdash \left( Rf \left( \bar{a}_1, \ldots, \bar{a}_n, y \right) \leftrightarrow y = \overline{\text{R} \left( a_1, \ldots, a_n \right)} \right).\]

prueba

Para mejorar la legibilidad, asumimos que\(n = 1\). Deje que la relación\(\text{R}\) sea una función con dominio\(\mathbb{N}\), y deje que la fórmula\(Rf\) sea definida por

\[Rf \left( x, y \right) : \equiv R \left( x, y \right) \land \left( \forall i < y \right) \left[ \neg R \left( x, i \right) \right].\]

Primero probamos (1), que\(Rf\) representa el conjunto\(\text{R}\). Como ya sabemos que eso\(R\) representa\(\text{R}\), basta con demostrarlo\(N \vdash R \left( \bar{a}, \bar{b} \right) \iff N \vdash Rf \left( \bar{a}, \bar{b} \right)\).

Asumir eso\(N \vdash Rf \left( \bar{a}, \bar{b} \right)\). Entonces, tenemos\(N \vdash R \left( \bar{a}, \bar{b} \right)\) por nuestra regla de inferencia (PC).

Para lo contrario, asuma eso\(N \vdash R \left( \bar{a}, \bar{b} \right)\). Ya que\(\text{R}\) es una función, tenemos\(\left( a, i \right) \not\in \text{R}\) para todos\(i < b\). Así, ya que\(R\) representa\(\text{R}\), tenemos

\[N \vdash \neg R \left( \bar{a}, \bar{0} \right) \land \neg R \left( \bar{a}, \bar{1} \right) \land \ldots \land \neg R \left( \bar{a}, \overline{b-1} \right).\]

Por Corolario 5.3.12, esto significa que\(N \vdash \left( \forall i < \bar{b} \right) \left[ \neg R \left( x, i \right) \right]\). Por lo tanto\(N \vdash Rf \left( \bar{a}, \bar{b} \right)\),, estableciendo (1).

Pasamos ahora a la prueba de (2). Primero lo demostramos\(N \vdash Rf \left( \bar{a}, y \right) \rightarrow y = \overline{\text{R} \left( a \right)}\). Ya que\(\text{R}\) es una función y\(R\) representa\(\text{R}\), tenemos

\[N \vdash \neg R \left( \bar{a}, \bar{0} \right) \land \ldots \land \neg R \left( \bar{a}, \overline{\text{R} \left( a \right) - 1} \right).\]

(Ten cuidado con la tipografía ahí - recuerda la diferencia entre la fórmula\(R\) y la función)\(\text{R}\).

Nuevamente por Corolario 5.3.12, tenemos\(N \vdash \left( \forall y < \overline{\text{R} \left( a \right)} \right) \left[ \neg R \left( \bar{a}, y \right) \right]\). Así, también tenemos

\[N \vdash \left( y < \overline{\text{R} \left( a \right)} \rightarrow \neg R \left( \bar{a}, y \right) \right). \tag{i}\]

Por (i) y (PC), tenemos

\[N \vdash \left( R \left( \bar{a}, y \right) \rightarrow \neg y < \overline{\text{R} \left( a \right)} \right). \tag{ii}\]

Por los axiomas lógicos, sabemos que

\[N \vdash \left[ \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \rightarrow \left( \overline{\text{R} \left( a \right)} < y \rightarrow \neg R \left( \bar{a} \overline{\text{R} \left( a \right)} \right) \right) \right]. \tag{iii}\]

Además, como la fórmula\(R\) representa la función\(\text{R}\), tenemos

\[N \vdash R \left( \bar{a}, \overline{\text{R} \left( a \right)} \right). \tag{iv}\]

Por (iii), (iv) y (PC), tenemos

\[N \vdash \left( \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \rightarrow \neg \overline{\text{R} \left( a \right)} < y \right). \tag{v}\]

Por (ii), (v) y (PC), tenemos

\[N \vdash \left( R \left( \bar{a}, y \right) \land \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \right) \rightarrow \left( \neg y < \overline{\text{R} \left( a \right)} \land \neg \overline{\text{R} \left( a \right)} < y \right). \tag{vi}\]

Por (vi) y el axioma N11, tenemos

\[N \vdash \left( R \left( \bar{a}, y \right) \land \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \right) \rightarrow y = \overline{\text{R} \left( a \right)},\]

es decir,\(N \vdash \left( Rf \left( \bar{a}, y \right) \rightarrow y = \overline{\text{R} \left( a \right)} \right)\), que establece la dirección de avance de nuestro bicondicional.

Para completar la prueba de (2), también necesitamos demostrar que

\[N \vdash \left( y = \overline{\text{R} \left( a \right)} \rightarrow Rf \left( \bar{a}, y \right) \right).\]

Esto se deja para el lector como Ejercicio 1.

Ahora, al Lema de Auto-Referencia. Este es solo un resultado encantador, perspicaz en su concepto y de gran alcance en sus consecuencias. Nos encantaría decir que la prueba también fue encantadora y esclarecedora, pero para ser sinceros, no tenemos una especie de prueba esclarecedora que mostrarte. A veces la mejor manera de describir una prueba es que el argumento te recoge y te sacude hasta que aceptas que, de hecho, establece lo que se supone que debe establecer. Eso es lo que obtienes aquí. Entonces, prepárate para un argumento técnico y algunos cálculos intrincados, pero ten en cuenta que el resultado, clave para establecer el Teorema de Incompletitud, realmente es bastante bonito.

Lema 6.2.2: Lema de autorreferencia de Gödel

Deja\(\psi \left( v_1 \right)\) ser una\(\mathcal{L}_{NT}\) -fórmula con solo\(v_1\) gratis. Entonces hay una frase\(\phi\) tal que

\[N \vdash \left( \phi \leftrightarrow \psi \left( \overline{ \ulcorner \phi \urcorner} \right) \right).\]

Chaf: ¡Mira lo pulcro que es esto! ¿Ves cómo\(\phi\) “dice” \(\psi\)es cierto de mi parte? ¡Y podemos hacer esto para cualquier fórmula\(\psi\)! ¡Qué idea genial!

prueba

Construiremos explícitamente lo necesario\(\phi\). Recordemos que en la Sección 5.9 definimos funciones representables\(\text{Num} : \mathbb{N} \rightarrow \mathbb{N}\) y\(\text{Sub} : \mathbb{N}^3 \rightarrow \mathbb{N}\) tal que\(\text{Num} \left( n \right) = \ulcorner \bar{n} \urcorner\) y\(\text{Sub} \left( \ulcorner \alpha \urcorner, \ulcorner x \urcorner, \ulcorner t \urcorner \right) = \ulcorner \alpha_t^x \urcorner\). Por Lemma 6.2.1 sabemos que hay fórmulas\(Numf\) y\(Subf\) tal que

\[\begin{align} N &\vdash \left[ Numf \left( \bar{a}, y \right) \leftrightarrow y = \overline{\text{Num} \left( a \right)} \right], \: \text{and that} \\ N &\vdash \left[ Subf \left( \bar{a}, \bar{b}, \bar{c}, z \right) \leftrightarrow z = \overline{\text{Sub} \left( a, b, c \right)} \right]. \end{align}\]

Chafia: ¡Recuerda,\(\text{Num}\) es la función y\(Numf\) es una\(\mathcal{L}_{NT}\) -fórmula que representa la función! Ah, y solo porque lo vamos a necesitar,\(\ulcorner v_1 \urcorner = 8\).

Ahora supongamos que\(\psi \left( v_1 \right)\) se da como en el enunciado del lema. Let\(\gamma \left( v_1 \right)\) be

\[\forall y \forall z \left[ \left[ Numf \left( v_1, y \right) \land Subf \left( v_1, \bar{8}, y, z \right) \right] \rightarrow \psi \left( z \right) \right].\]

Veamos\(\gamma \left( n \right)\) un poco más de cerca, suponiendo eso\(n = \ulcorner \alpha \urcorner\). Si el antecedente de las\(\gamma \left( n \right)\) retenciones, entonces la primera parte del antecedente nos dice que

\ [y =\ texto {Núm}\ izquierda (n\ derecha) =\ ulesquina\ barra {n}\ uresquina\)

y la segunda parte del antecedente afirma que

\[\begin{align} z &= \text{Sub} \left( n, 8, \ulcorner \bar{n} \urcorner \right) \\ &= \text{Sub} \left( \ulcorner \alpha \urcorner, \ulcorner v_1 \urcorner, \ulcorner \bar{n} \urcorner \right) \\ &= \ulcorner \alpha_{\bar{n}}^{v_1} \urcorner \\ &= \ulcorner \alpha_{\overline{\ulcorner \alpha \urcorner}}^{v_1} \urcorner. \end{align}\]

Así\(z\) es el número de Gödel de {\(\alpha\)con el número de Gödel de\(\alpha\) sustituido en por\(v_1\)}.

Una elección más complicada nos llevará a donde queremos ir. Dejar\(m = \ulcorner \gamma \left( v_1 \right) \urcorner\), y dejar\(\phi\) ser\(\gamma \left( \bar{m} \right)\). Ciertamente,\(\phi\) es una oración, así que estaremos terminados si podemos demostrarlo\(N \vdash \phi \leftrightarrow \psi \left( \overline{\ulcorner \phi \urcorner} \right)\).

Trabajemos primero a través de un pequeño cálculo. Observe que

\[\begin{align} \text{Sub} \left( m, 8, \ulcorner \bar{m} \urcorner \right) &= \text{Sub} \left( \ulcorner \gamma \left( v_1 \right) \urcorner, \ulcorner v_1 \urcorner, \ulcorner \bar{m} \urcorner \right) \\ &= \ulcorner \gamma \left( v_1 \right)_{\bar{m}}^{v_1} \urcorner \\ &= \ulcorner \gamma \left( \bar{m} \right) \urcorner \\ &= \ulcorner \phi \urcorner. \end{align}\]

Con esto en la mano, los siguientes son probablemente equivalentes en\(N\):

\[\begin{array}{lr} \phi & \\ \forall y \forall z \left[ Numf \left( \bar{m}, y \right) \rightarrow \left( Subf \left( \bar{m}, \bar{8}, y, z \right) \rightarrow \psi \left( z \right) \right) \right] & \text{logic} \\ \forall y \forall z \left[ y = \overline{\text{Num} \left( m \right)} \rightarrow \left( Subf \left( \bar{m}, \bar{8}, y, z \right) \rightarrow \psi \left( z \right) \right) \right] & \text{Lemma 6.2.1} \\ \forall y \forall z \left[ y = \overline{\ulcorner \bar{m} \urcorner} \rightarrow \left( Subf \left( \bar{m}, \bar{8}, y, z \right) \rightarrow \psi \left( z \right) \right) \right] & \text{calculation} \\ \forall z \left( Subf \left( \bar{m} \bar{8}, \overline{\ulcorner \bar{m} \urcorner}, z \right) \rightarrow \psi \left( z \right) \right) & \text{quantifier rules} \\ \forall z \left( z = \overline{\text{Sub} \left( m, 8, \ulcorner \bar{m} \urcorner \right)} \rightarrow \psi \left( z \right) \right) & \text{Lemma 6.2.1} \\ \forall z \left( z = \overline{\ulcorner \phi \urcorner} \rightarrow \psi \left( z \right) \right) & \text{calculation (6.2.16-19) above} \\ \psi \left( \overline{\ulcorner \phi \urcorner} \right) & \text{quantifier rules} \end{array} \notag\]

Entonces\(N \vdash \phi \leftrightarrow \psi \left( \overline{\ulcorner \phi \urcorner} \right)\), según sea necesario.

Observe en esta prueba que si\(\psi\) es una\(\Pi\) -fórmula, entonces\(\phi\) es lógicamente equivalente a una\(\Pi\) -oración. Al alterar\(\gamma\) ligeramente también podemos disponer, si\(\psi\) es una\(\Sigma\) fórmula, para tener\(\phi\) lógicamente equivalente a una\(\Sigma\) -oración.

Ejercicios

1. Completar el comprobante de Reclamación (2) de Lemma 6.2.1 demostrando que
   \[N \vdash \left( y = \overline{\text{R} \left( a \right)} \rightarrow Rf \left( \bar{a}, y \right) \right).\]
2. El comprobante de Lema 6.2.1 dependía del uso del corolario al Lema de Rosser, Corolario 5.3.12. Para facilitar la lectura, asumimos en la prueba de eso\(n = 1\), lo que facilitó mucho el uso del corolario. Trabajar a través de la prueba de Lemma 6.2.1 asumiendo que\(n = 2\), teniendo cuidado con los detalles.
3. Supongamos que\(\psi \left( v_1 \right)\) es\(Formula \left( v_1 \right)\). Por el Lema de Auto-Referencia, hay una frase\(\phi\) tal que\(N \vdash \left( \phi \leftrightarrow Formula \left( \overline{\ulcorner \phi \urcorner} \right) \right)\). ¿Lo hace\(N \vdash \phi\)? ¿Lo hace\(N \vdash \neg \phi\)? Justifica tu respuesta. ¿Qué pasa si usamos\(\psi \left( v_1 \right) = \neg Formula \left( v_1 \right)\) en su lugar?
4. Let\(\psi \left( v_1 \right)\) be\(Even \left( v_1 \right)\), and let\(\phi\) be the sentence generated when the Self-Reference Lemma is applied to\(\psi \left( v_1 \right)\). ¿Lo hace\(N \vdash phi\)? ¿Lo hace\(N \vdash \neg \phi\)? ¿Cómo se puede decir?
5. Demostrar que la prueba del Lema de Auto-Referencia aún funciona si usamos
   \[\gamma \left( v_1 \right) = \exists y \exists z \left[ Numf \left( v_1, y \right) \land Subf \left( v_1, \bar{8}, y, z \right) \land \psi \left( z \right) \right].\]
   Concluir que si\(\psi\) es una\(\Sigma\) fórmula, entonces el\(\phi\) del Lema de Auto-Referencia puede tomarse como equivalente a una\(\Sigma\) frase.