5.7: Numeración Gödel

Ahora cambiamos nuestro enfoque de mirar funciones y relaciones sobre los números naturales, donde tiene sentido hablar de conjuntos representables, a funciones que mapean cadenas de\(\mathcal{L}_{NT}\) -símbolos a\(\mathbb{N}\). Estableceremos nuestro sistema de codificación para fórmulas, asociando a cada\(\mathcal{L}_{NT}\) fórmula\(\phi\) su número Gödel,\(\ulcorner \phi \urcorner\). Haremos un gran uso de la función de codificación\(\langle \cdot \rangle\) que definimos en la Definición 4.5.3.

Definición 5.7.1.

La función\(\ulcorner \cdot \urcorner\), con domain la colección de cadenas finitas de\(\mathcal{L}_{NT}\) -symbols y codomain\(\mathbb{N}\), se define de la siguiente manera:

\[\ulcorner s \urcorner = \begin{cases} \begin{array}{ll} \langle 1, \ulcorner \alpha \urcorner \rangle & \text{if} \: s \: \text{is} \: \left( \neg \alpha \right), \: \text{where} \: \alpha \: \text{is an} \: \mathcal{L}_{NT} \text{-formula} \\ \langle 3, \ulcorner \alpha \urcorner, \ulcorner \beta \urcorner \rangle & \text{if} \: s \: \text{is} \: \left( \alpha \lor \beta \right), \: \text{where} \: \alpha \: \text{and} \: \beta \: \text{are} \: \mathcal{L}_{NT} \text{-formulas} \\ \langle 5, \ulcorner v_i \urcorner, \ulcorner \alpha \urcorner \rangle & \text{if} \: s \: \text{is} \: \left( \forall v_i \right) \left( \alpha \right), \: \text{where} \: \alpha \: \text{is an} \: \mathcal{L}_{NT} \text{-formula} \\ \langle 7, \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner \rangle & \text{if} \: s \: \text{is} \: = t_1 t_2, \: \text{where} \: t_1 \: \text{and} \: t_2 \: \text{are terms} \\ \langle 9 \rangle & \text{if} \: s \: \text{is} \: 0 \\ \langle 11, \ulcorner t \urcorner \rangle & \text{if} \: s \: \text{is} \: St, \: \text{with} \: t \: \text{a term} \\ \langle 13, \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner \rangle & \text{if} \: s \: \text{is} \: + t_1 t_2, \: \text{where} \: t_1 \: \text{and} \: t_2 \: \text{are terms} \\ \langle 15, \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner \rangle & \text{if} \: s \: \text{is} \: \cdot t_1 t_2, \: \text{where} \: t_1 \: \text{and} \: t_2 \: \text{are terms} \\ \langle 17, \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner \rangle & \text{if} \: s \: \text{is} \: E t_1 t_2, \: \text{where} \: t_1 \: \text{and} \: t_2 \: \text{are terms} \\ \langle 19, \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner \rangle & \text{if} \: s \: \text{is} \: < t_1 t_2, \: \text{where} \: t_1 \: \text{and} \: t_2 \: \text{are terms} \\ \langle 2i \rangle & \text{if} \: s \: \text{is the variable} \: v_i \\ 3 & \text{otherwise.} \end{array} \end{cases}\]

Observe que cada símbolo está asociado con su número de símbolo, como se establece en la Tabla 5.1.

Ejemplo 5.7.2:

Sólo para la práctica, vamos a encontrar\(\ulcorner 0 \urcorner\). Apenas de la tabla anterior,\(\ulcorner 0 \urcorner = \langle 9 \rangle = 2^{10} = 1024\). Para mirar otro ejemplo, mira\(\ulcorner 0 = 0 \urcorner\). Trabajando recursivamente,

\[\begin{align} \ulcorner = 00 \urcorner &= \langle 7, \ulcorner 0 \urcorner, \ulcorner 0 \urcorner \rangle \\ &= \langle 7, 1024, 1024 \rangle \\ &= 2^8 3^{1025} 5^{1025} \end{align}\]

El Ejercicio 3 te pide investigar algunas de las sutilezas de la codificación en lo que se refiere a este último ejemplo.

Ejemplo 5.7.3:

Esta es una función ordenada, pero los números involucrados se vuelven realmente grandes, muy rápidos. Supongamos que calculamos el número de Gödel para la fórmula\(\phi\), donde\(\phi\) está\(\left( \neg = 0S0 \right)\).

Ya que\(\phi\) es una negación, la definición nos dice que

\[\ulcorner \phi \urcorner \: \text{is} \: \langle 1, \urcorner = 0S0 \urcorner \rangle = 2^2 3^{\ulcorner = 0S0 \urcorner + 1}.\]

Así que tenemos que encontrar\(\ulcorner = 0S0 \urcorner\), y por la cláusula “iguales” en la definición,

\[\ulcorner = 0S0 \urcorner \: \text{is} \: \langle 7, \ulcorner 0 \urcorner, \ulcorner S0 \urcorner \rangle = 2^8 3^{\ulcorner 0 \urcorner + 1} 5^{\ulcorner S0 \urcorner + 1}.\]

Pero\(\ulcorner 0 \urcorner = 2^{10} = 1024\), y\(\ulcorner S0 \urcorner = 2^{12} 3^{\ulcorner 0 \urcorner + 1} = 2^{12} 3^{1025}\). Ahora estamos llegando a alguna parte. Tapando las cosas de nuevo, obtenemos

\[\ulcorner = 0S0 \urcorner \: \text{is} \: 2^8 3^{1025} 5^{\left[ 2^12 3^{1025} + 1 \right]}\]

por lo que el número de Gödel para\(\left( \neg = 0S0 \right)\) es

\[\ulcorner \phi \urcorner \: \text{is} \: 2^2 3^{\left( 2^8 3^{1025} 5^{\left[ 2^{12} 3^{1025} + 1 \right]} + 1 \right)}.\]

Chaff:Para hacerse una idea de lo grande que es este número, considere el hecho de que el exponente en el 5 es\(\ulcorner S0 \urcorner = 2^{12} 3^{1025} + 1\), que es

4588239037329654294933009459423640636113835 33711852348723982661700090725110495540711416 24496800232720851201851240219667428400380468 28472630247645228844759293716788206726298594 576060661169640295858586110650008838161967674248 714876110453564150536269711030213614452805279 213722748800276796114884183810302573694405480 301945785627339194850085383681785222504546 327111992210992776215014423059901287305704225 3643605726211189929819826835540873386794064170 56397550836223108131323849454313910276632860438529,

aproximadamente\(10^{490}\).

Ahora, juguemos un poco con el número de Gödel de\(\phi\):

\[\begin{align} \ulcorner \phi \urcorner &= 2^2 3^{\left( 2^8 3^{1025} 5^{\left[ 2^{12} 3^{1025} + 1 \right]} + 1 \right)} \\ &> 3^{5^{\left[ 10^{490} \right]}}, \end{align}\]

así que si tomamos logaritmos comunes, vemos que

\[\text{log} \left( \ulcorner \phi \urcorner \right) > 5^{\left[ 10^{490} \right]} \text{log} 3\]

y tomando logaritmos de nuevo,

\[\begin{align} \text{log} \left( \text{log} \left( \ulcorner \phi \urcorner \right) \right) &> 10^{490} \text{log} 5 + \text{log} \left( \text{log} 3 \right) \\ &> 10^{489}. \end{align}\]

Hmm... Entonces esto significa que\(\text{log} \left( \ulcorner \phi \urcorner \right)\) es más grande que\(10^{\left[ 10^{489} \right]}\). Pero el logaritmo común de un número es (aproximadamente) el número de dígitos que se necesita para expresar el número en notación base 10, por lo que hemos demostrado que se necesitan más que\(10^{\left[ 10^{489} \right]}\) dígitos para escribir el número de Gödel de\(\phi\). Si recuerdas que un googol es\(10^{100}\) y un googolplex es\(10^{10^{100}}\),\(\ulcorner \phi \urcorner\) está empezando a parecer un número bastante grande, ¡pero se pone mejor!

Escribir una cadena de\(10^{\left[10^{489} \right]}\) caracteres (asumiendo un millón de caracteres por milla, o unos 16 caracteres por pulgada) requeriría mucho más de\(10^{\left[ 10^{488} \right]}\) millas, lo que es mucho más que años\(10^{\left[ 10^{487} \right]}\) luz.

O bien, para mirarlo de otra manera, si asumimos que podemos poner alrededor de 132 líneas de tipo de un trozo de papel de 8.5 por 11 pulgadas, y como una resma de papel (500 hojas) tiene aproximadamente 2 pulgadas de grosor, eso le da una pegajosa de papel de más de años\(10^{\left[ 10^{488} \right]}\) luz de altura. Dado que actualmente se estima que la edad del universo está en las decenas de miles de millones de años (del orden de los\(10^{10}\) años), si suponemos que el universo es a la vez euclidiana y esférico, el volumen del universo es menor que los años luz\(10^{40}\) cúbicos, más bien menor que los años luz\(10^{\left[ 10^{488} \right]}\) cúbicos necesitaríamos almacenar nuestra pila de papel. En definitiva, no ganamos ningún premio por ser increíblemente eficientes con la codificación que hemos elegido. Lo que sí ganamos es facilidad de análisis. El hecho de que hayamos elegido codificar usando una función representable hará que nuestras pruebas sean mucho más fáciles de comprender.

Ejercicios

1. Evaluar el número de Gödel para cada uno de los siguientes:
   (a)\(\left( \forall v_3 \right) \left( v_3 + 0 = v_4 \right)\)
   (b)\(SSSS0\)
2. Encuentra la fórmula o término que está codificado por cada uno de los siguientes:
   (a)\(2^8 3^{\left( 2^{14} 3^{\left( 2^{18} 3^9 5^{1025} + 1 \right)} 5^{\left( 2^{18} 3^{33} 5^{1025} +1 \right)} + 1 \right]} 5^{\left[ 2^{18} 3^{129} 5^{1025} + 1 \right]}\)
   (b)\(2^2 3^{\left( 2^{20} 3^{1025} 5^{\left( 2^{12} 3^{1025} + 1 \right)} + 1 \right)}\)
   (c)\(2^6 3^9 5^{\left( 2^8 3^9 5^9 + 1 \right)}\)
3. Mira el número\(c = 2^8 3^{1025} 5^{1025} = \langle 7, \ulcorner 0 \urcorner, \ulcorner 0 \urcorner \rangle\). Encuentra el número\(e\) tal que\(IthElement \left( e, 2, c \right)\) sea cierto. Supongamos que\(d = \langle 3, 1, 4, 5 \rangle = 2^4 3^2 5^5 7^6\). ¿Por qué es\(IthElement \left( 4, 1, d \right)\) falso?