La idea es ésa, pero, puestos a ser puristas, la situación es muy sutil. Es verdad que el término \( f^1_{\bar k} \) (donde \( \bar k \) es el numeral asociado a \( k \)) "es" un funtor en el sentido de que se demuestra en ARP que \( f^1_{\bar k}\in \mbox{Fun}({\color{\blue}\mathcal L_{\rm arp}}) \), pero en realidad no es un funtor. Es un término que denota un cierto número natural, digamos \( N \). Lo que pasa es que \( N \) no es cualquier número, sino que existe un funtor de verdad, digamos, \( h \), tal que si interpretas sus signos como los números 0, 1, 2, 3, 4, 5 y a \( h \) como una sucesión de números, entonces esa sucesión es \( N \).
Entiendo, ¿pero podrías entonces describir exactamente como podríamos llegar a la enumeración de las funciones monádicas recursivas primitivas?
Lo que entiendo es esto:
- Podemos enumerar los funtores monádicos de \( {\color{blue}\mathcal L_{\rm arp}} \) (no es más que la enumeración \( f^1_0, f^1_1, f^1_2, \cdots \) donde cada término es el dado por el funtor \( f \) del mensaje anterior).
- Dado \( g \) un funtor monádico cualquiera de ARP, se tiene que \( \color{blue} g \) es un funtor monádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y, por tanto,es alguno de los \( f^1_j \).
- Si tuvieramos una enumeración, \( g_0, g_1, g_2, \cdots \), de los funtores monádicos de ARP entonces una enumeración (con posibles repeticiones) de las funciones monádicas recursivas primitivas es \( F(g_0), F(g_1), F(g_2), \cdots \). Efectivamente, aunque en el hilo no lo hemos demostrado, veo claro que dada una función \( n \)-ádica recursiva primitiva \( G \) existe un funtor de ARP (que no tiene porque ser único) \( g \) de rango \( n \) tal que \( F(g)=G \), por lo tanto como en la lista \( g_0, g_1, g_2, \cdots \) aparecen todos los funtores monádicos, en la lista \( F(g_0), F(g_1), F(g_2), \cdots \) deben aparecer todas las funciones monádicas recursivas primitivas.
El paso que no veo claro es como pasar de la enumeración de los funtores monádicos de \( {\color{blue}\mathcal L_{\rm arp}} \) a una enumeración de los funtores monádicos de ARP.
Estamos mareando la perdiz (y cuando digo "estamos", quiero decir que tú la estás mareando, y yo también). Es todo mucho más sencillo y directo. Sólo hay que tener presente que los teoremas de ARP no son meras cadenas de signos, sino que tienen un significado muy concreto. Por ejemplo, si demostramos en ARP que
\( x^3+y^3 = z^3\rightarrow xyz = 0 \),
cosa que es posible, cualquiera que vea la demostración debería convencerse inmediatamente de que la ecuación \( x^3+y^3=z^3 \) no tiene soluciones naturales no nulas, porque eso es lo que significa el teorema en cuestión.
Análogamente, en ARP hemos demostrado que el funtor monádico \( f^1 \) definido por
\( f^1(k) = f^1_k \)
enumera los funtores monádicos de
\( \mathcal L_{\rm arp} \) y ahora sólo tenemos que preguntarnos: ¿y eso qué significa? Si es un teorema de ARP, es que es verdadero, pero ¿qué significa?
Para responder a esa pregunta debemos recordar que hemos formalizado ARP identificando sus signos con los números del 0 al 7, con lo que cada funtor de \( \mathcal L_{\rm arp} \) se identifica con una sucesión finita de números del 0 al 5 y, por consiguiente, con un número natural.
Quiero decir, que, por ejemplo, el funtor \( p^1_1 \) (de \( \mathcal L_{\rm arp} \), no su formalización) es la sucesión \( pS0S0 \), que podemos identificar con la sucesión \( 2, 1, 0, 1, 0 \), que a su vez podemos identificar con el número natural \( \left<2, 1, 0, 1, 0\right>_\infty = 170\,378\,236\,901 \).
Así pues, podemos identificar cada funtor monádico de ARP con un número natural, y una enumeración de los funtores monádicos de \( \mathcal L_{\rm arp} \) consiste simplemente en enumerarlos de menor a mayor. El hecho de que en ARP hayamos construido el funtor monádico \( f^1 \) significa simplemente que la función \( H=F(f^1) \) enumera todos los funtores monádicos de \( \mathcal L_{\rm arp} \), es decir, que si \( H(0) = 2 \), con eso estamos diciendo que el primer funtor monádico de \( \mathcal L_{\rm arp} \) es el funtor que, como número natural, es el número \( 2 \), es decir, el funtor \( S \), mientras que \( H(1) \) es el número natural que, como funtor de \( \mathcal L_{\rm arp} \) es el segundo funtor en orden creciente, etc.
Más precisamente, lo que hemos probado al demostrar esto en ARP es que la función \( H \), por ser la función denotada por un funtor, es recursiva primitiva. Hemos probado que la función que a cada número natural \( k \) le asigna el número natural \( H(k) \) que, visto como sucesión finita de números naturales es el \( k \)-ésimo funtor monádico de \( \mathcal L_{\rm arp} \), es recursiva primitiva.
La enumeración, en la práctica (en el sentido de que es una forma de hacerlo, no necesariamente el más eficiente, ni mucho menos) es: sabemos que \( H(0) = 2 \). Si ya hemos calculado \( H(k)=m \):
1) Calculamos el funtor \( g \) correspondiente a \( m \) (es decir, calculamos la sucesión de números naturales que se identifica con \( m \)).
2) Le anteponemos \( p_1^1 = \left<2, 1, 0, 1, 0\right> \) a esa sucesión, con lo que obtenemos el número \( M \) correspondiente a un funtor mayor que \( m \).
3) Examinamos todos los números entre \( m+1 \) y \( M \) viendo cuáles se corresponden con funtores y nos quedamos con el menor de ellos, que será \( H(k+1) \).
Así, si llamamos \( \bar f_k^1 \) al funtor de \( \mathcal L_{\rm arp} \) que, visto como número natural, es igual a \( H(k) \), tenemos una enumeración de todos los funtores monádicos de \( \mathcal L_{\rm arp} \), de modo que en ARP se demuestra que \( {\color{blue}f^1_k} = f^1_{\bar k} \), donde \( \bar k \) es el numeral de \( k \).
A su vez, la sucesión \( F(\bar f^1_k) \) es una enumeración (con repeticiones) de las funciones monádicas recursivas primitivas.
¡Ah, vale! Me lio un poco el párrafo siguiente, donde entonces es igual mejor poner esto, ¿no?
Relajando el formalismo por caridad cristiana, este "teorema" afirma que el funtor \( \phi \) cumple (bajo las hipótesis obvias en cada caso):
- \( \phi({\color{blue}S},{\color{red} \langle}n{\color{red} \rangle}) = n+1 \).
- \( \phi({\color{blue}c}, {\color{red} \langle}n{\color{red} \rangle}) = 0 \).
[...]
¡Chivato! Ahora me reñirá a mí argentinator, porque ahí estaba feo haber puesto \( n \) en vez de \( \left<n\right> \).
Esta vez es culpa mía. Me faltaba una F y entonces resulta que F son dos cosas, así que mejor de esta forma:
En otras palabras, la función diádica \( H(f, s) \) que, cuando \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y \( s \) es una sucesión de longitud \( n \), calcula
\( H(f, s) = F(f)(s_0,\ldots, s_{n-1}) \)
(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva.
Vale, ahora le veo algo más de sentido, pero sigo sin tenerlo claro. Estas diciendo que \( f \) es un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), pero luego consideras \( F(f) \) como la función recursiva denotada por \( f \) y esto no me cuadra siendo un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \) y no de ARP.
Ahí estaba yo mareando la perdiz, y al final puse en azul un
\( \mathcal L_{\rm arp} \) que no debería haber estado en azul. En realidad es lo mismo que he dicho más arriba, pero ahora para funtores no necesariamente monádicos:
Tenemos el funtor monádico \( f \) que enumera todos los funtores de
\( \mathcal L_{\rm arp} \), y entonces, simplemente interpretando lo que significa el teorema que dice que ese funtor enumera todos los funtores, vemos que la función monádica recursiva primitiva \( H = F(f) \) enumera todos los funtores de \( \mathcal L{\rm arp} \), en el sentido de que \( H(7) \) es el séptimo número natural (en orden creciente) que, visto como sucesión de números naturales e identificando \( 0 \) con el signo \( 0 \), \( 1 \) con el signo \( S \), etc., resulta ser un funtor de \( \mathcal L_{\rm arp} \) (en negro).
Me espero mejor a que aclaremos la notación y entienda bien que quieres decir para exponer la otra duda que quedó pendiente en el mensaje anterior por el lío que hice al parecer que hacía referencia a la siguiente cita en lugar de a la que tocaba.
He modificado un poco la frase en el hilo. La relación por la que preguntas es que si fuera recursiva primitiva la función \( H \) que a cada funtor \( n \)-ádco \( f \) (identificado con un número natural) y a cada \( n \)-tupla \( s \) de números naturales (identificada con otro número natural) les hace corresponder \( H(f, s) = F(f)(s) \), entonces habría un funtor \( \Phi \) tal que \( F(\Phi) = H \) y ese funtor \( \Phi \) cumpliría el "teorema".
Decías más arriba que no hemos demostrado que a cada función recursiva primitiva le corresponde un funtor. He mirado la respuesta #3 y, efectivamente, no lo dice explícitamente, más allá de la declaración de intenciones: "Ahora vamos a darle un nombre en \( \mathcal L_{\rm arp} \) a cada función recursiva primitiva", pero es obvio que de la definición de función recursiva primitiva se sigue que toda función es denotada por un funtor.
Entiendo. Pero, aun así, supongo que por razones más complejas que las que podemos ver con lo que sabemos, es igualmente imposible obtener el funtor diádico que formalice la definición de "satisfacción" en las condiciones que ya se han mencionado, ¿no?
Existe el teorema de Tarski, que afirma que en una teoría aritmética de primer orden razonable capaz de formalizar su propia sintaxis no se puede definir una fórmula \( \vDash \alpha \) que se interprete en un modelo \( M \) como que la fórmula \( \alpha \) es verdadera en dicho modelo. El argumento de fondo es que entonces se podría construir una fórmula que fuera equivalente a que ella misma es falsa.
Esto no se aplica directamente a ARP, porque no es una teoría de primer orden, pero, aunque no me he puesto a comprobar los detalles, sospecho que todo vale igualmente.