5.8: Números de Gödel y N
- Page ID
- 113523
Supongamos que te preguntamos si el número
\[\begin{align} a = &35845617479137924179164136401747192469639 \\ &33857123846474406114544531958789925746411 \\ &80793941381251818131650014462814216151784 \\ &37797240847442423809728350349681982162407 \\ &86504920777012547391538781481141489453194 \\ &04814037245506808496961291846992606460711 \\ &74235438629125412438572089750021624696475 \\ &32686017988856987542814858951450213588587 \\ &45976629206001394705081676818056243914838 \\ &10641798001801554788070758142606590669736 \\ &02492132671739715266307333432862633253105 \\ &8659079930322842573861827424036194222176 \\ &00000 \end{align}\]
fue el número Gödel\(\mathcal{L}_{NT}\) de un término. ¿Cómo lo harías para averiguarlo? Un enfoque razonable sería factorial\(a\) e intentar decodificar. Resulta que\(a = 2^{14} 3^{1025} 5^9\), y desde\(1024 = 2^{10} = \ulcorner 0 \urcorner\) y\(8 = 2^3 = \ulcorner v_1 \urcorner\), ya sabes que\(a\) es el número Gödel del término\(+0v_1\). Eso fue fácil.
Lo que hace que esto sea más interesante es que lo anterior es tan fácil que\(N\) puede probar que\(a\) es el número Gödel de un término. Establecer este hecho es el objetivo de esta sección.
Mostraremos cómo construir ciertas\(\Delta\) -fórmulas, por ejemplo la fórmula\(Term \left( x \right)\), tal que por cada número natural\(a\),\(\mathfrak{N} \models Term \left( \bar{a} \right)\) si y sólo si\(a\) es el número Gödel de un término. Ya que nuestra fórmula será una\(\Delta\) -fórmula, esto nos dice que\(N \vdash Term \left( \bar{a} \right)\) si\(a\) es el número Gödel de un término.
El problema va a estar en anotar la fórmula. Al mirar la definición de la función\(\ulcorner \cdot \urcorner\) en Definición 5.7.1, puede ver que la definición es por recursión, y necesitaremos una forma de tratar las definiciones recursivas dentro de las restricciones de\(\Delta\) -definition. Nos gustaría poder escribir algo así como
\[Term \left( x \right) = \cdots \lor \left( \exists y < x \right) \left[ x = 2^{11} 3^y \land Term \left( y \right) \right] \lor \cdots,\]
pero esta definición es claramente circular. Un truco técnico nos hará superar este punto.
Pero deberíamos empezar por el principio. Usted sabe que la colección de\(\mathcal{L}_{NT}\) -terms es el cierre del conjunto de variables y la colección de símbolos constantes bajo los símbolos de función. Comenzaremos mostrando que la colección de números de Gödel de variables es representable.
El conjunto
\[VARIABLE = \{ a \in \mathbb{N} | a = \ulcorner v \urcorner \: \text{for some variable} \: v \}\]
es representable.
Basta con proporcionar una\(\Delta\) -definición para\(VARIABLE\):
\(Variable \left( x \right) =\)
\[\left( \exists y < x \right) \left( Even \left( y \right) \land 0 < y \land x = 2^{Sy} \right).\]
Observe que utilizamos el hecho de que si\(x = 2^{Sy}\), entonces\(y < x\). Es fácil ver que\(\mathfrak{N} \models Variable \left( \bar{a} \right)\) si y solo si\(a \in VARIABLE\), entonces nuestra fórmula muestra que\(VARIABLE\) es un conjunto representable.
Para motivar nuestro desarrollo de la fórmula\(Term\), consideremos el término\(t\), dónde\(t\) está\(+0Sv_1\). Estamos acostumbrados a reconocer que se trata de un término mirándolo desde fuera en:\(t\) es un término, ya que es la suma de dos términos. Ahora tenemos que empezar a mirar\(t\) de adentro hacia afuera:\(t\) es un término, ya que hay una secuencia de términos, cada uno de los cuales es un símbolo constante, una variable, o construido a partir de entradas anteriores en la secuencia por aplicación de una función símbolos de la aridad apropiada. Aquí hay una secuencia de construcción para nuestro término\(t\):
\[\left( v_1, Sv_1, 0, +0Sv_1 \right).\]
A partir de esta secuencia de construcción podemos observar la secuencia asociada de números de Gödel:
\[\begin{align} \left( \ulcorner v_1 \urcorner, \ulcorner Sv_1 \urcorner, \ulcorner 0 \urcorner, \ulcorner +0Sv_1 \urcorner \right) &= \left( \langle 2 \rangle, \langle 11, \ulcorner v_1 \urcorner \rangle, \langle 9 \rangle, \langle 13, \ulcorner 0 \urcorner, \ulcorner Sv_1 \urcorner \rangle \right) \\ &= \left( \langle 2 \rangle, \langle 11, 8 \rangle, \langle 9 \rangle, \langle 13, 1024, \langle 11, \ulcorner v_1 \urcorner \rangle \rangle \right) \\ &= \left( \langle 2 \rangle, \langle 11, 8 \rangle, \langle 9 \rangle, \langle 13, 1024, \langle 11, 8 \rangle \rangle \right) \\ &= \left( \langle 2 \rangle, \langle 11, 8 \rangle, \langle 9 \rangle, \langle 13, 1024, 2^{12} 3^9 \rangle \rangle \right) \\ &= \left( 8, 2^{12} 3^9, 1024, 2^{14} 3^{1025} 5^{80621569} \right) \\ &= \left( 8, 80621568, 1024, a \right) \end{align}\]
donde el número grande\(a\) es el número Gödel del término\(+0Sv_1\). Ahora podemos codificar esta secuencia de números de Gödel como un solo número
\[c = 2^9 3^{80621569} 5^{1025} 7^{a+1}.\]
Ahora podemos empezar a ver como\(Term \left( a \right)\) va a quedar nuestra fórmula. Sabremos que\(a\) es el número Gödel de un término si hay un número\(c\) que es el código para una secuencia de construcción para un término, y el último término es que secuencia de construcción tiene número de Gödel\(a\). Para formalizar todo esto, comencemos definiendo la colección de secuencias constructivas:
Una secuencia finita\(\mathcal{L}_{NT}\) de términos\(\left( t_1, t_2, \ldots, t_l \right)\) se denomina secuencia de construcción de términos para\(t_l\) si, para cada\(i\)\(1 \leq i \leq l\),\(t_i\) es una variable, el símbolo constante 0, o es uno de\(t_j\),,\(St_j\),\(+t_j t_k\),\(\cdot t_j t_k\), o\(E t_j t_k\), donde \(j < i\)y\(k < i\).
El conjunto
\(TERMCONSTRUCTIONSEQUENCE =\)
\[\{ \left( c, a \right) | c \: \text{codes a term construction sequence for the term with Gödel number} \: a \}\]
es representable.
Aquí hay una\(\Delta\) -definición para el conjunto:
\(TermConstructionSequence \left( c, a \right) =\)
\[CodeNumber \left( c \right) \land \\ \left( \exists l < c \right) \left[ Length \left( c, l \right) \land IthElement \left( a, l, c \right) \land \\ \left( \forall e < c \right) \left( \forall i \leq l \right) \left( IthElement \left( e, i, c \right) \rightarrow \\ Variable \left( e \right) \lor e = \bar{2}^{\bar{10}} \lor \\ \left( \exists j < i \right) \left( \exists k < i \right) \left( \exists e_j < c \right) \left( \exists e_k < c \right) \\ \left( IthElement \left( e_j, j, c \right) \land IthElement \left( e_k, k, c \right) \land \\ \left[ e = e_j \lor e = \bar{2}^{\bar{12}} \cdot \bar{3}^{Se_j} \lor \\ e = \bar{2}^{\bar{14}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \lor \\ e = \bar{2}^{\bar{16}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \lor \\ e = \bar{2}^{\bar{16}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \lor e = \bar{2}^{\bar{18}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \right] \right) \right) \right].\]
Esto solo dice que\(\left( c, a \right) \in TERMCONSTRUCTIONSEQUENCE\) si y solo si\(c\) es un código de longitud\(l\),\(a\) es el último número de la secuencia codificada por\(c\), y si\(e\) es una entrada en la posición\(i\) de\(c\), entonces\(e\) es o bien el número Gödel de una variable, el número de Gödel de 0, una repetición de una entrada anterior, o es el número de Gödel que es el resultado de aplicar\(S\)\(+\),,\(\cdot\), o\(E\) a entradas anteriores en\(c\). Como todos los cuantificadores están acotados, esta es una\(\Delta\) -definición, por lo que el conjunto\(TERMCONSTRUCTIONSEQUENCE\) es representable.
Ahora parecería que para definir\(Term \left( a \right)\), lo único que tendríamos que hacer es decir que\(a\) es el número Gödel de un término si hay un número\(c\) tal que\(TermConstructionSequence \left( c, a \right)\). Esto no es suficiente, ya que el cuantificador no\(\exists c\) está acotado. Para escribir una\(\Delta\) -definición de\(Term\), tendremos que entender cuán grandes tienen que ser los códigos para las secuencias de construcción.
Si\(t\) es un\(\mathcal{L}_{NT}\) -term y\(\ulcorner t \urcorner = a\), entonces el número de símbolos en\(t\) es menor que\(a\).
La prueba es por inducción sobre la complejidad de\(t\). Sólo para darte una idea de cuán cierto es el lema, considera el ejemplo de\(t\), dónde\(t\) está\(S0\). Entonces\(t\) tiene dos símbolos, mientras\(\ulcorner t \urcorner = a = 2^{12} 3^{1025}\), que es sólo un poco más grande que 2.
Si\(t\) es un término, la longitud de la secuencia de construcción más corta de\(t\) es menor o igual al número de símbolos en\(t\).
Nuevamente, utilizar la inducción en la complejidad de\(t\).
Estos lemas nos dicen que si\(a\) es el número Gödel de un término, entonces hay una secuencia de construcción de ese término cuya longitud es menor que\(a\).
Supongamos que\(t\) es un\(\mathcal{L}_{NT}\) -término,\(u\) es un subtérmino de\(t\). (En otras palabras,\(u\) es una subcadena de\(t\), también\(u\) es un\(\mathcal{L}_{NT}\) -term, y no\(u\) es idéntica a\(t\).) Entonces\(\ulcorner u \urcorner < \ulcorner t \urcorner\).
Ejercicio 4.
Si\(a\) es un número natural mayor o igual a 1, entonces\(p_a \leq 2^{a^a}\), donde\(p_a\) está el número primo\(a\) th.
Ejercicio 5.
Ahora tenemos suficiente para darnos nuestro encuadernado en el código para la secuencia de construcción más corta para un término\(t\) con número de Gödel\(\ulcorner t \urcorner = a\). Cualquier secuencia de construcción de este tipo debe verse como
\[\left( t_1, t_2, \ldots, t_k = t \right),\]
donde\(k \leq a\) y cada uno\(t_i\) es un subtérmino de\(t\). Pero entonces el código para esta secuencia de construcción es
\[\begin{align} c &= \langle \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner, \ldots, \ulcorner t \urcorner \langle \\ &= 2^{\ulcorner t_1 \urcorner + 1} 3^{\ulcorner t_2 \urcorner + 1} \cdots p_k^{\ulcorner t \urcorner + 1} \\ &\leq 2^{a+1} 3^{a+1} \cdots p_k^{a+1} \\ &\leq p_k^{a+1} p_k^{a+1} \cdots p_k^{a+1} \left( k \: \text{terms} \right) \\ &\leq p_a^{a+1} p_a^{a+1} \cdots p_a^{a+1} \left( a \: \text{terms} \right) \\ &= \left[ \left( 2^{a^a} \right)^{a+1} \right]^a \\ &= \left( 2^{a^a} \right)^{a^2+a}, \end{align}\]
lo que nos da nuestro necesario atado.
Finalmente estamos en una posición en la que podemos dar una\(\Delta\) -definición de la colección de Gödel números de\(\mathcal{L}_{NT}\) -términos:
\(Term \left( a \right) =\)
\[\left( \exists c < \left( \bar{2}^{a^a} \right)^{a^{\bar{2}}+a} \right) TermConstructionSequence \left( c, a \right).\]
Así que el conjunto
\[TERM = \{ a \in \mathbb{N} | a \: \text{is the Gödel number of an} \: \mathcal{L}_{NT} \text{-term} \}\]
es un conjunto representable, y así\(N\) tiene la fuerza para demostrar, para cualquier número\(a\), ya sea\(Term \left( \bar{a} \right)\) o\(\neg Term \left( \bar{a} \right)\). En el Ejercicio 6 te pediremos que demuestres que el conjunto también\(FORMULA\) es representable.
Ejercicios
- Supongamos que\(\phi\) es una fórmula de\(\mathcal{L}_{NT}\). ¿Cuáles de las siguientes son también\(\mathcal{L}_{NT}\) -fórmulas? Para los que no son fórmulas, ¿por qué no son fórmulas?
a)\(Term \left( \phi \right)\)
b)\(Term \left( \ulcorner \phi \urcorner \right)\)
c)\(Term \left( \overline{\ulcorner \phi \urcorner} \right)\) - Supongamos que en la definición de\(TermConstructionSequence\), viste la siguiente cadena:
\[\cdots \lor e = \overline{2^{11} \cdot 3^{e_j}} \lor \cdots\]
¿Eso sería parte de una\(\mathcal{L}_{NT}\) fórmula legal? ¿Cómo lo sabes? ¿Y si la cadena fuera
\[\cdots \lor e = \bar{2}^{\bar{11}} \cdot \bar{3}^{\bar{e_j}} \lor \cdots?\] - Demostrar Lema 5.8.4.
- Demostrar Lema 5.8.6.
- Demostrar Lema 5.8.7 por inducción. Para el paso inductivo, si estás tratando de demostrarlo\(p_{n+1} \leq 2^{\left( n+1 \right)^{n+1}}\), usa el hecho de que\(p_{n+1}\) es menor o igual al factor primo más pequeño de\(\left( p_1 p_2 \cdots p_n \right) - 1\).
- Una prueba similar a la prueba que\(TERM\) es representable demostrará que también
\[FORMULA = \{ a \in \mathbb{N} | a \: \text{is the Gödel number of an} \: \mathcal{L}_{NT} \text{-formula} \}\]
es representable. Suministre cuidadosamente los detalles necesarios y defina la fórmula\(Formula \left( f \right)\). Probablemente tendrás que definir la fórmula\(FormulaConstructionSequence \left( c, f \right)\) y estimar la longitud de dicha secuencia como parte de tu exposición.