En este mensaje y los siguientes vamos a ver que, entre las muchas cosas que pueden formalizarse en ARP se encuentra la propia construcción de ARP. Para ello sólo necesitamos aprovechar que los ocho signos de \( \mathcal L_{\rm arp} \) pueden ser lo que más nos convenga y elegir concretamente ocho números naturales (los ocho primeros, por decir algo). Todo lo que sigue ha de entenderse como definiciones y teoremas en ARP:
Definición Llamaremos
signos de \( \color{blue}\mathcal L_{\rm arp} \) a
\( {\color{blue}0} \equiv 0,\quad {\color{blue} S} \equiv 1, \quad {\color{blue}p}\equiv 2,\quad {\color{blue} c}\equiv 3,\quad {\color{blue} \kappa}\equiv 4,\quad {\color{blue} \rho} \equiv 5, \quad {\color{blue} x}\equiv 6,\quad {\color{blue} =}\equiv 7.
\)
El conjunto de signos de \( {\color{blue}\mathcal L_{\rm arp}} \) es, pues, el conjunto
\( \mbox{Sig}({\color{blue}\mathcal L_{\rm arp}}) \equiv \{{\color{blue} 0},\quad {\color{blue} S},\quad{\color{blue} p},\quad{\color{blue} c},\quad {\color{blue} \kappa},\quad{\color{blue}\rho},\quad{\color{blue} x},\quad{\color{blue} =}\}. \)
Notemos que a partir de aquí el color no es un mero adorno, sino que es significativo. Por ejemplo, \( S \) y \( \color{blue}S \) son dos cadenas de signos de \( \mathcal L_{\rm arp} \) distintas entre sí. La primera tiene longitud 1, mientras que la segunda tiene longitud 2, ya que \( {\color{blue}S}\equiv 1 \equiv S0 \).
Diremos que \( \zeta \) es una
cadena de signos de \( {\color{blue}\mathcal L_{\rm arp}} \) si cumple
\( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\equiv \forall i<\ell(\zeta)\ \zeta_i\in \mbox{Sig}({\color{blue}\mathcal L_{\rm arp}}).
\)
Esta definición incluye a la cadena de signos vacía \( 0 \) de longitud \( 0 \).
En el mensaje anterior hemos definido la yuxtaposición de una sucesión de sucesiones: \( \zeta_0\ldots \zeta_n \), y es claro que la yuxtaposición de cadenas de signos de \( \color{blue}\mathcal L_{\rm arp} \) es de nuevo una cadena de signos de \( \color{blue}\mathcal L_{\rm arp} \).
Si \( \zeta\equiv s_0\cdots s_n \) es cualquier cadena metamatemática de signos \( s_i \) de \( \mathcal L_{\rm arp} \), llamaremos \( \color{blue}\zeta \) al único numeral que, según el último teorema de la respuesta #7, cumple
\( \mathop\vdash\limits_{\rm ARP}{\color{blue}\zeta} = {\color{blue}s_0}\cdots {\color{blue}s_n} = \left<{\color{blue}s_0},\ldots, {\color{blue} s_n}\right>. \)
(A partir de aquí escribiré \( \left<\right> \) en lugar de \( \left<\right>_\infty \).)
[Copiado de Eparoh] Es sencillo ver entonces que si \( \zeta \) y \( \psi \) son dos cadenas metamatemáticas de signos de \( \mathcal L_{\rm arp} \) y \( \zeta \psi \) es su yuxtaposición (metamatemática), entonces
\( \mathop\vdash\limits_{\rm ARP} {\color{blue} \zeta \psi} = {\color{blue} \zeta} \frown {\color{blue}\psi}. \)
La prueba se realiza por inducción (metamatemática) sobre la longitud de \( \psi \).
Nota Con esto hemos introducido una ambigüedad en la notación. En el caso de un signo de \( \mathcal L_{\rm arp} \), como por ejemplo \( p \), la notación \( \color{blue}p \) puede hacer referencia a dos numerales distintos. Según la definición inicial de este mensaje es \( {\color{blue}p} \equiv 2 \), pero según la definición que acabamos de dar (viendo a \( p \) como una cadena de signos de longitud \( 1 \)) tenemos que \( \left<{\color{blue}p}\right> = \left<2\right> = 4 \), luego \( {\color{blue}p} \equiv 4 \). En general, según este segundo criterio, tenemos que
\( {\color{blue} 0} \equiv 1,\quad {\color{blue}S} \equiv 2, \quad {\color{blue}p}\equiv 4,\quad {\color{blue}c}\equiv 7, \quad {\color{blue}\kappa}\equiv 11,\quad {\color{blue} \rho} \equiv 16, \quad {\color{blue} x}\equiv 22, \quad {\color{blue}=} \equiv 29.
\)
En la práctica el contexto siempre dejará claro cuándo consideramos que una expresión como \( \color{blue} s \) hace referencia a un signo de \( {\color{blue}\mathcal L_{\rm arp}} \) o a la cadena de signos de longitud \( 1 \) correspondiente.
Por ejemplo, tenemos que \( p^2_1 \equiv pS0SS0 \), y en ARP se demuestra que
\( \left<{\color{blue} p},{\color{blue} S}, {\color{blue} 0}, {\color{blue} S}, {\color{blue} S}, {\color{blue} 0}\right> = \left<2, 1, 0, 1, 1, 0\right>= 14\,621\,784\,001\,269\,145\,854\,811,
\)
luego,
\( {\color{blue}p^2_1}\equiv 14\,621\,784\,001\,269\,145\,854\,811 \)
(entendiendo el miembro derecho como un \( 0 \) precedido del número indicado de funtores \( S \)).
Numerales Diremos que \( N \) es un
numeral si cumple
\( N\in \mbox{Num}({\color{blue}{\mathcal L_{\rm arp}}})\equiv \ell(N)>0\land \forall i <\ell(N)\dot- 1\, N_i = {\color{blue} S}\land N_{\ell(N)\dot- 1}={\color{blue} 0}.
\)
Consideramos el funtor definido por
\( N_0 = {\color{blue} 0},\qquad N_{n+1} = {\color{blue}S} N_n. \)
(El miembro derecho hay que entenderlo como la yuxtaposición \( {\color{blue}S}\frown N_n \).)
Una simple inducción prueba que \( N_n\in \mbox{Num}({\color{blue}\mathcal L_{\rm arp}}) \) y, más aún, los numerales de esta forma son los únicos que hay, pues si definimos el
indice de un numeral como \( \mbox{ind}(N) = \ell(N)\dot-1 \), tenemos que \( \mbox{ind}(N_n) = n \) y que
\( N\in \mbox{Num}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{ind}(N) = n\rightarrow N = N_n. \)
Es claro que si \( \bar n \) es el numeral (metamatemático) correspondiente al número natural \( n \), entonces en ARP se demuestra que \( {\color{blue}\bar n} = N_{\bar n} \). Por ejemplo: \( {\color{blue}SSSS0} \equiv N_4 \). Esto se prueba por inducción (metamatemática) sobre \( n \).
Notemos que no es lo mismo el numeral (metamatemático) \( 4\equiv SSSS0 \) que el numeral (formalizado) \( N_4 = {\color{blue}SSSS0} \equiv 352\,942\,601 \).
Por otro lado, el funtor \( N \) que hemos definido un poco más arriba es algo más general que la sucesión de numerales \( {\color{blue} 0}, {\color{blue}S0}, {\color{blue}SS0}, \ldots \), pues esto son únicamente términos sin variables, mientras que el funtor \( N \) nos permite considerar el término \( N_n \), donde \( n \) es una variable de ARP, una variable que al sustituirla por un numeral, como \( \bar 4\equiv SSSS0 \), da lugar a un término (que se demuestra) igual al numeral \( {\color{blue}SSSS0} \).
Proyecciones Definimos el funtor diádico
\( p^n_k = {\color{blue} p} N_k N_n. \)
(Nuevamente, en el miembro derecho sobreentendemos dos \( \frown \), como en la definición del funtor \( N \).)
Llamaremos
proyecciones a las cadenas de signos que cumplen
\( \pi\in \mbox{Proy}({\color{blue}\mathcal L_{\rm arp}})\equiv \pi \in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \exists kn<\ell(\pi)(1\leq k\leq n\land \pi =p^n_k).
\)
Si \( \pi\in \mbox{Proy}({\color{blue}\mathcal L_{\rm arp}}) \), podemos calcular:
\( k(\pi) = (\mu i<\ell(\pi)\ \pi_i = {\color{blue} 0})\dot- 1,\qquad n(\pi) = \ell(\pi)\dot -(k(\pi)+ 3), \)
y es fácil ver que
\( \pi\in \mbox{Proy}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \pi = p^{n(\pi)}_{k(\pi)}. \)
Por ejemplo, si \( \pi \equiv p^3_2 = {\color{blue} pSS0SSS0} \), vemos que \( k(\pi) = 3\dot- 1=2 \) y que \( n(\pi) = 8\dot-(2+3) = 3 \).
Los números \( k(\pi) \) y \( n(\pi) \) se llaman
índice y
rango de \( \pi \), respectivamente. Por definición tenemos que \( 1\leq k(\pi)\leq n(\pi) \).
Es fácil ver que si \( 1\leq k\leq n \) son números naturales metamatemáticos, entonces
\( \mathop\vdash\limits_{\rm ARP}{\color{blue}p^n_k} = p^{\bar n}_{\bar k}, \)
donde \( \bar k \) y \( \bar n \) son los numerales (metamatemáticos) de ARP correspondientes a \( k \) y \( n \), respectivamente.
Funtores Vamos a definir un funtor monádico \( \mbox{rang} \) usando el penúltimo teorema de la respuesta #17, es decir, que definiremos \( \mbox{rang}(\zeta) \) suponiendo definido el rango de las subcadenas propias de \( \zeta \) (las de \( \mbox{Sub}(\zeta) \)). Para la cadena vacía, definimos \( \mbox{rang}(0)= 0 \) y, para cadenas de longitud no nula, distinguimos varios casos:
En cualquier otro caso, \( \mbox{rang}_n(\zeta)=0 \). Llamaremos
funtores de \( {\color{blue}\mathcal L_{\rm arp}} \) a las cadenas de signos que cumplen
\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\equiv f\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)>0. \)
Así, cada funtor \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) tiene asociado un rango \( \mbox{rang}(f)>0 \).
A partir de las definiciones precedentes (y suprimiendo precisiones técnicas), es fácil ver que todo funtor \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) se encuentra en uno de los casos siguientes:
- \( f = {\color{blue} S} \) (en cuyo caso \( f \) es un funtor monádico),
- \( f = {\color{blue} c} \) (en cuyo caso \( f \) es un funtor monádico),
- \( f = p^n_k \), para ciertos índices \( 1\leq k\leq n \) (y entonces \( f \) es un funtor \( n \)-ádico),
- \( f = {\color{blue}\kappa}(h, g_0,\ldots, g_{m\dot-1}) \), donde \( h \) es un funtor \( m \)-ádico y los \( g_i \) forman una sucesión de funtores \( n \)-ádicos (y entonces \( f \) es un funtor \( n \)-ádico),
- \( f = {\color{blue}\rho}(g, h) \), donde \( g \) es un funtor \( n \)-ádico y \( h \) es un funtor \( n+2 \)-ádico (y entonces \( f \) es un funtor \( n+1 \)-ádico).
Es evidente que un mismo funtor no puede estar a la vez en en dos de estos casos, pues el signo inicial \( f_0 \) es distinto en cada uno de ellos, pero, más aún, en los casos \( 4 \) y \( 5 \) los funtores que componen \( f \) también están unívocamente determinados.
Demostración
En primer lugar definimos el funtor
\( \mbox{R}(\zeta,n) = \mu \zeta'\in \mbox{Sub}(\zeta)\exists \zeta''\in \mbox{Sub}(\zeta)(\ell(\zeta'')=n\land \zeta = \zeta''\zeta').
\)
Es fácil ver que si \( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}}) \) y \( \ell(\zeta)\geq n \), entonces \( R(\zeta,n) \) es la cadena que resulta de quitarle a \( \zeta \) sus \( n \) primeros signos.
A su vez definimos
\( \mbox{PN}(\zeta)=\mu \zeta'\in \mbox{Sub}(\zeta)\exists k\leq \ell(\zeta)(\zeta' = N_k\land \zeta = N_k\ R(\zeta,k+1)).
\)
Así, \( \mbox{PN}(\zeta) \) es el numeral con el que empieza \( \zeta \) si es que realmente empieza por un numeral, y es \( 0 \) (que es también la cadena vacía) si no es el caso. Es fácil probar entonces que
\( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \mbox{PN}(N_k\zeta)=N_k. \)
Esto implica que el primer numeral de una cadena de signos (si existe) está unívocamente determinado, es decir, que una misma cadena de signos no puede descomponerse de dos formas distintas de modo que el primer fragmento sea un numeral.
Ahora definimos un funtor monádico \( \mbox{PF} \) con la propiedad de que, si \( f \) es un funtor, entonces
\( \mbox{PF}(f\zeta)=f, \)
es decir, que \( \mbox{PF} \) proporciona el primer funtor de su argumento, mientras que si \( \zeta \) es una cadena que no empieza por un funtor, entonces \( \mbox{PF}(\zeta)=0 \) es la cadena vacía.
Para ello definimos \( \mbox{PF}(0) = 0 \) y, para cadenas de longitud no nula, distinguimos varios casos:
- Si \( \zeta_0 = {\color{blue}S} \), entonces \( \mbox{PF}(\zeta) = {\color{blue} S} \),
- Si \( \zeta_0 = {\color{blue}c} \), entonces \( \mbox{PF}(\zeta) = {\color{blue}c} \),
- Si \( \zeta_0 = {\color{blue}p} \), calculamos \( \bar k\equiv \mbox{PN}(R(\zeta,1)) \). Si no es la cadena vacía, calculamos \( \bar n\equiv\mbox{PN}(R(\zeta, 1+\ell(\bar k))) \). Si tampoco es la cadena vacía y además \( 2\leq \ell(\bar k)\leq \ell(\bar n) \), entonces \( \mbox{PF}(\zeta) = \zeta|_{\ell(\bar k)+\ell(\bar n)+1}. \)
- Si \( \zeta_0 = {\color{blue}\kappa} \), calculamos \( h\equiv \mbox{PF}(R(\zeta, 1)) \). Si no es la cadena vacía (y, por consiguiente, es un funtor), llamamos \( m\equiv \mbox{rang}(h) \) y consideramos el funtor definido por \( F(\zeta, 0) = \left<{\color{blue}\kappa} h, R(\zeta, 1+\ell(h))\right> \) y
\( F(\zeta, n+1) = \cases{\left<\smash{F(\zeta, n)_0\frown \mbox{PF}(F(\zeta,n)_1),R(F(\zeta,n)_1,\ell(\mbox{PF}(F(\zeta,n)_1)))}\right>, &si $\mbox{PF}(F(\zeta,n)_1)\neq 0$,\cr
\left<0, 0\right>&si $\mbox{PF}(F(\zeta,n)_1)=0$.}
\)
Así, si \( F(\zeta, m) = \left<0,0\right> \), definimos \( \mbox{PF}(\zeta) = 0 \) y en caso contrario hacemos \( \mbox{PF}(\zeta)=F(\zeta, m)_0 \).
Lo que hace \( F \) es quitarle a \( \zeta \) la cadena inicial \( {\color{blue}\kappa} h \) y luego ir quitándole funtores mientras sea posible. Lo que hemos hecho es decir que si se le pueden quitar \( m \) funtores, entonces \( \mbox{PF}(\zeta) \) es la yuxtaposición de \( \color{blue}\kappa \) y los \( m+1 \) funtores que hemos quitado.
- Si \( \zeta_0 = {\color{blue}\rho} \), calculamos \( g = \mbox{PF}(R(\zeta, 1)) \). Si es un funtor, calculamos \( h = \mbox{PF}(R(\zeta, 1+\ell(h))) \). Si es un funtor y \( \mbox{rang}(h)=\mbox{rang}(g)+2 \), definimos \( \mbox{PF}(\zeta)={\color{blue}\rho} g h \)
En cualquier otro caso, \( \mbox{PF}(\zeta)=0 \).
Ahora una inducción rutinaria muestra que cumple lo requerido, es decir, que si \( f \) es un funtor y \( \zeta \) es una cadena de signos arbitraria, entonces \( \mbox{PF}(f\zeta) = f \), lo que prueba que el primer funtor de una cadena de signos está unívocamente determinado.
Usando esto es inmediato comprobar que la descomposición de un funtor como composición o recursión es única.
Observemos también que una simple inducción sobre la longitud de \( f \) prueba que si \( f \) es un funtor (metamatemático) de rango \( n \), entonces
\( \mathop\vdash\limits_{\rm ARP}{\color{blue} f}\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{ran}({\color{blue} f}) = \bar n, \)
donde \( \bar n \) es el numeral (metamatemático) asociado a \( n \).
Enumeración de funtores Es interesante observar que podemos enumerar los funtores de
\( \mathcal L_{\rm arp} \). Para ello observamos que si \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( {\color{blue}\kappa}({\color{blue}S} ,f) \) es otro funtor del mismo rango, pero mayor como número natural. Esto nos permite definir los funtores
\( \mbox{SF}(f)= \mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land f<g), \)
\( \mbox{SFR}(f)=\mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \land \mbox{rang}(g)=\mbox{rang}(f)\land f<g).
\)
que calculan el menor funtor mayor que uno dado, y el menor funtor del mismo rango mayor que uno dado. A su vez:
\( f_0 = {\color{blue}S},\qquad f_{k+1} = \mbox{SF}(f_k), \)
\( f^n_0 =\mu g\leq p^n_1(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g)=n),\qquad f^n_{k+1} = \mbox{SFR}(f^n_k),
\)
de modo que
\( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}),\qquad f_k^n\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f^n_k)=n,
\)
\( k<k'\rightarrow f_k<f_{k'}\land f^n_k<f^n_{k'}, \)
(de donde se sigue por inducción que \( k\leq f_k \), \( k\leq f^n_k \)), y a su vez
\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \exists! k\leq f\ f = f_k, \)
\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)=n\rightarrow \exists! k\leq f\ f = f^n_k. \)
Veamos, como ejemplo, la prueba del primero de estos dos hechos:
Demostración
Dado un funtor \( f \), tomando \( m\equiv f \), se cumple que \( f\leq f_m<f_{m+1} \), luego podemos considerar \( r\equiv \mu m\leq f+1(f< f_m) \). Claramente, no puede ser \( r = 0 \), luego si hacemos \( k = r\dot- 1 \), tenemos que \( f_k\leq f<f_{k+1} = \mbox{SF}(f_k) \). La definición de SF implica entonces que \( f = f_k \).
Variables Consideramos el funtor definido por
\( x_n = {\color{blue} x} N_n. \)
Llamaremos
variables a las cadenas de signos que cumplen
\( \xi\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\equiv \xi \in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \exists n\leq \ell(\xi)\,\xi = x_n.
\)
El
índice de una variable es \( \mbox{ind}(\xi) = \ell(\xi)\dot-2 \). Es fácil probar que
\( \xi\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{ind}(\xi) = n\rightarrow \xi = x_n. \)
Si \( x \) es la variable (metamatemática) de índice \( n \), es fácil ver que
\( \mathop\vdash\limits_{\rm ARP}{\color{blue} x} = x_{\bar n}, \)
donde \( \bar n \) es el numeral (metamatemático) correspondiente a \( n \).
Términos Para definir los términos de \( {\color{blue}\mathcal L_{\rm arp}} \) definimos un funtor \( F \) que tome el valor \( 1 \) sobre los términos y \( 0 \) en otro caso. Escribiendo
\( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\equiv F(\zeta)=1, \)
la definición es:
En cualquier otro caso, \( \zeta\notin \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \). Es claro entonces que
\( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\leftrightarrow \zeta = {\color{blue} 0}\lor \zeta\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\lor \exists f\in \mbox{Sub}(\zeta)\exists m\leq \ell(f)\exists t\in S_m( \mbox{Sub}(\zeta))(f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land m = \mbox{rang}(f)\land \)
\( \forall i< m\ t_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta = ft_0\cdots t_{m\dot-1}). \)
Sin tecnicismos, tenemos que \( t \) es un término si y sólo si \( t= \color{blue} 0 \) o bien \( t \) es una variable, o bien existe un funtor \( m \)-ádico \( f \) y una sucesión de \( m \) términos tal que \( t = ft_0\cdots t_{m\dot-1} \).
En la práctica, en este último caso, escribiremos \( t = f(t_0,\ldots, t_{m\dot- 1}) \). Como en el caso de los funtores, es pura rutina comprobar que si \( t \) es de esta forma, entonces \( m \) y los términos \( t_i \) están unívocamente determinados.
Demostración
Definimos un funtor \( \mbox{PT} \) tal que si \( t \) es un término, entonces \( \mbox{PT}(t\zeta) = t \), es decir, que \( \mbox{PT} \) asigna a cada cadena el término por el que empieza, si es que existe, o \( 0 \) en caso contrario. Para ello definimos $\mbox{PT}(0) = 0$ y, para cadenas de longitud no nula, distinguimos varios casos:
- Si \( \zeta_0 = \color{blue} 0 \), entonces \( \mbox{PT}(\zeta) = \color{blue} 0 \).
- Si \( \zeta_0 = \color{blue}x \), llamamos \( N\equiv \mbox{PT}(R(\zeta, 1)) \). Si \( N\in \mbox{Num}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( \mbox{PT}(\zeta)={\color{blue} x} N \).
- Si \( f \equiv \mbox{PF}(\zeta) \) es un funtor, llamamos \( m\equiv \mbox{rang}(f) \) y consideramos el funtor definido por \( F(\zeta, 0) = \left<f,R(\zeta, \ell(f))\right> \) y
\( F(\zeta, n+1) = \cases{\left<\smash{F(\zeta, n)_0\frown \mbox{PT}(F(\zeta,n)_1),R(F(\zeta,n)_1,\ell(\mbox{PT}(F(\zeta,n)_1)))}\right>&si $\mbox{PT}(F(\zeta,n)_1)\neq 0$,\cr \left<0, 0\right>& si $\mbox{PT}(F(\zeta,n)_1)=0$.}
\)
Finalmente, si \( F(\zeta, m) \neq \left<0,0\right> \), definimos \( \mbox{PT}(\zeta)=F(\zeta, m)_0 \).
En cualquier otro caso, \( \mbox{PT}(\zeta) = 0 \).
Es fácil ver que el funtor PT cumple lo requerido:
\( t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \mbox{PT}(t\zeta) = f, \)
es decir, que PT extrae el primer término de cualquier cadena de signos, y con eso es fácil probar la unicidad de la expresión de un término construido a partir de un funtor.
Por último observemos que una simple inducción sobre la longitud de \( t \), prueba que si \( t \) es un término (metamatemático), entonces
\( \mathop\vdash\limits_{\rm ARP}{\color{blue} t}\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}). \)
Fórmulas Definimos las
fórmulas de \( {\color{blue}\mathcal L_{\rm arp}} \) como las cadenas de signos que cumplen:
\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\equiv \alpha\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \exists t_1t_2\in \mbox{Sub}(\alpha)
\)
\( (t_1, t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \alpha = {\color{blue}=}\, t_1t_2). \)
En la práctica escribiremos \( t_1{\color{blue}=} \ t_2 \) en lugar de \( {\color{blue} =}\ t_1t_2 \). Podemos definir los funtores
\( T_1(\alpha) = \mbox{PT}(R(\alpha,1)),\qquad T_2(\alpha) = R(\alpha, 1+\ell(T_1(\alpha))), \)
de modo que
\( t_1, t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow T_1(t_1{\color{blue}=} \, t_2) = t_1\land T_2(t_1{\color{blue}=} \, t_2) = t_2. \)
\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow T_1(\alpha),T_2(\alpha)\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \alpha = T_1(\alpha){\color{blue} =}\,T_2(\alpha).
\)
Esto significa que los dos términos que componen una fórmula están unívocamente determinados.
También es claro que si \( \alpha \) es una fórmula (metamatemática) de ARP, entonces
\( \mathop\vdash\limits_{\rm ARP}{\color{blue}\alpha}\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}). \)
Diremos que \( \theta \) es una
expresión de \( \color{blue}\mathcal L_{\rm arp} \) si cumple
\( \theta\in \mbox{Exp}({\color{blue}\mathcal L_{\rm arp}})\equiv \theta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\lor \theta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}).
\)
Sustitución Definimos ahora la sustitución de una variable por un término en una expresión, distinguiendo casos:
- Si \( \zeta\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}}) \),
\( S_x^t\zeta \equiv \cases{t& si $\zeta = x$,\cr \zeta&si $\zeta\neq x$.} \)
- Si \( \zeta = {\color{blue}0} \), entonces \( S_x^t {\color{blue}0} = \color{blue} 0 \).
- Si\( f = \mbox{PF}(\zeta) \) es un funtor y \( \mbox{rang}(f)=m \) y existe \( s\in S_m(\mbox{Sub}(\zeta)) \) tal que \( \forall i<m\ s_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \) y \( \zeta = ft_0\cdots t_{m\dot- 1} \), entonces definimos
\( S_x^t\zeta = fS_x^ts_0\cdots S_x^ts_{m\dot-1}. \)
- Si \( \zeta_0= {\color{blue} =} \) y existen \( t_1, t_2\in \mbox{Sub}(\zeta) \) tales que \( \zeta = {\color{blue} =} t_1t_2 \), definimos \( S_x^t\zeta={\color{blue} =} S_x^tt_1S_x^tt_2 \)
En cualquier otro caso, definimos \( S_x^t\zeta = 0 \). Es claro entonces que (suponiendo en cada caso \( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})) \):
- \( S_x^t{\color{blue}0} = {\color{blue}0} \).
- \( y\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^ty=\cases{t&si $y=x$,\cr y&si $y\neq x$.} \)
- \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)=n\land \ell(s)= n\land \forall i<n\ s_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^tfs_0\cdots s_{n\dot-1} = fS_x^ts_0\cdots S_x^ts_{n\dot-1}. \)
- \( t_1, t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^t(t_1{\color{blue} =} \, t_2)=S_x^tt_1{\color{blue} =}\ S_x^tt_2 \).
Es fácil ver que
\( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^t\zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}),
\)
\( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^t\zeta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}),
\)
así como que \( si x, t, \theta \) son, respectivamente, una variable, un término y una expresión metamatemáticas, entonces
\( \mathop\vdash\limits_{\rm ARP} S_{\color{blue} x}^{\color{blue} t}{\color{blue} \theta} = {\color{blue} S_x^t\theta}. \)
Nota Hasta aquí hemos detallado las definiciones y las demostraciones en ARP para que el lector se haga una idea de lo que supone formalizar en ARP, pero tenemos que insistir en que no es nada práctico exponer las definiciones y demostraciones con este nivel de detalle, ni en ARP ni en cualquier otra teoría axiomática formal.
La forma habitual de trabajar de los matemáticos en cualquier teoría formal no es detallar todas las definiciones y argumentos hasta el punto de que sea evidente cómo se formalizan en una teoría axiomática en particular, sino sólo hasta el punto de que se entiendan las ideas relevantes, dando por hecho que formalizar los pasos técnicos que no ofrecen ninguna dificultad conceptual es una pura rutina que no aporta nada salvo el hecho de confirmar que lo que se está diciendo es formalizable en una teoría dada, pero normalmente uno puede convencerse de que esto es así sin necesidad de especificar todos los detalles
ad nauseam.Por ejemplo, comparemos las condiciones que definen la sustitución de una variable por un término tal y como las enunciamos en su momento al introducir ARP informalmente y cómo las hemos enunciado aquí. Si nos fijamos, concretamente, en la tercera condición. En su momento la enunciamos así:
\( S_x^tf(t_1,\ldots, t_n)\equiv f(S_x^tt_1,\ldots, S_x^tt_n) \),
y ahora:
\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)=n\land \ell(s)= n\land \forall i<n\ s_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^tfs_0\cdots s_{n\dot-1} = fS_x^ts_0\cdots S_x^ts_{n\dot-1}. \)
Vemos que la diferencia consiste en que en la versión informal sobreentendemos que \( f \) es un funtor \( n \)-ádico, que \( t \) es un término, etc., mientras que en la versión formalizada hemos explicitado estas hipótesis para asegurarnos de que la fórmula que presentamos es realmente un teorema de ARP, y no un mero fragmento de teorema.
En la práctica, no hay ningún inconveniente (al contrario, tiene muchas ventajas) en formular los teoremas de ARP en un lenguaje más laxo, por ejemplo diciendo (así, con palabras) que si \( x \) es una variable, \( t \) es un término, \( f \) es un funtor \( n \)-ádico y \( t_1,\ldots, t_n \) son términos, entonces
\( S_x^tf(t_1,\ldots, t_n)\equiv f(S_x^tt_1,\ldots, S_x^tt_n), \)
sin necesidad de escribir una fórmula técnica en forma de implicación que contenga todas las hipótesis, y eso es lo que haremos de ahora en adelante. (Notemos que hemos aprovechado para introducir la costumbre habitual de numerar las sucesiones de \( 1 \) a \( n \) en lugar de empezar en \( 0 \) y acabar en \( n\dot- 1 \), que también se puede formalizar a cambio de introducir algo más de notación rutinaria.)
En cuanto a los argumentos, a la hora de juzgar si un determinado concepto o un determinado argumento son formalizables en ARP, el mejor método no es ponerse a escribir una formalización detallada, sino reflexionar sobre si la definición o la demostración pueden realizarse acotando siempre a priori los cuantificadores que empleemos.
Por ejemplo, para completar la exposición sobre la sustitución nos faltaría definir la sustitución múltiple:
\( S_{x_1\cdots x_n}^{t_1\cdots t_n}\theta = S_{y_1}^{t_1}\cdots S_{y_n}^{t_n}S_{x_1}^{y_1}\cdots S_{x_n}^{y_n}\theta,
\)
donde \( y_1,\ldots, y_n \) son variables cualesquiera que no estén en \( t_1,\ldots, t_n \) ni en \( \theta \). Formalizar esta definición requiere definir funtores que calculen las variables contenidas en una sucesión de expresiones, y que calculen una biyección entre esas variables y otras nuevas, y otros que apliquen sustituciones de forma recurrente, etc., pero el lector que haya analizado las pruebas que hemos dado en esta sección debería convencerse de que no hay nada que impida detallar toda esa construcción de modo que sea obviamente formalizable en ARP, y por eso mismo sería una pérdida de tiempo ponerse a escribir todos esos detalles en un papel.
Con esto hemos formalizado en ARP el lenguaje \( \mathcal L_{\rm arp} \). Falta formalizar la lógica de ARP.