Intentaré aquí dar la prueba de la unicidad de un funtor.
Mi estrategia consiste en cambiar el lenguaje de ARP.

Si ven como pongo muchas caritas sonrientes,
no es que sea un loquillo alegre,
sino que el mensaje es largo, y uso las caritas para marcar las secciones.
Lenguaje de pseudofuntores para ARP. Voy a considerar a los signos \(s,c,p,\kappa,\rho\), como "iniciales",
y los signos \(S,0\), serán usados para formar "numerales".
Un
numeral es lo de siempre: una cadena de varias "\(S\)" seguidas de un único "0".
Los signos iniciales se usan así:
Se llamará
encabezado inicial a una cadena \(Ikn\),
donde \(I\) es un signo inicial, y \(k,n\), son numerales
distintos de cero.
La idea de un encabezado inicial es la siguiente:
el numeral \(k\) denotará un índicador, como el subíndice de una proyección.
El numeral \(n\) indicará explícitamente el orden del funtor en formación.
Un
pseudofuntor \(f\) de orden \(n\) se construirá así:
Existe una sucesión de cadenas \(f_1,...,f_r\),
con números naturales asociados respectivos \(k_1,...,k_r\),
llamados
indicadores,
y naturales \(n_1,...,n_r\), respectivos,
llamados
órdenes,
tales que, para cada \(i\):
\(f_i\) es un encabezado inicial cuyos numerales son \(k_i,n_i\)
seguido de cadenas \(M_1\sigma_1,...,M_m\sigma_m\),
siendo \(M_1,...,M_m\), numerales,como sigue:
existen índices \(j_1,...,j_m<i\), tales que
cada \(\sigma_i=f_{j_i}\)
(admitimos el caso \(m=0\)).
Y finalmente \(f=f_r\).
Por inducción en \(i\), se puede apreciar que cada cadena \(f_i\)
es un pseudofuntor de indicador \(k_i\) y orden \(n_i\).
______________
Un pseudofuntor es ampliable trivialmente.Supongamos que \(f\) es un pseudofuntor de indicador \(k=k_r\) y orden \(n=n_r\),
con \(f_1,...,f_r\), como antes.
Si concatenamos a su derecha con una cadena de la forma \(M^*g^*\),
donde \(M^*\) es un numeral (positivo) y \(g^*\) un pseudofuntor,
podemos insertar a \(g^*\) antes en la lista, digamos \(f_0\equiv g\),
y obtendremos que \(f^*\equiv f M^*g^*\) es un pseudofuntor.
_________________________
Un pseudofuntor sin cabeza (y cuello) sigue siendo un pseudofuntor.Supongamos que un pseudofuntor \(f\) tiene alguna descomposición
\[f\equiv H M_1 f_1 M_2 f_2 ... M_m f_m,\]
en donde \(H\) es un encabezado inicial, y \(m\geq 1\).
Afirmamos que la subcadena que resulta de quitar el encabezado \(H\) y el numeral \(M_1\):
\[\tilde f \equiv f_1 M_2 f_2... M_m f_m,\]
es un pseudofuntor.
Como \(f_1\) es un pseudofuntor,
tiene alguna descomposición
\(f_1\equiv \tilde H \mu_1 \phi_1 ... \mu_a \phi_a\),
para un encabezado inicial \(\tilde H\), numerales \(\mu_j\), pseudofuntores \(\phi_j\),
y tal que \(a\geq 0\).
Ahora bien: \(\tilde f\) se obtiene de concatenarle al funtor \(f_1\)
las cadenas \(M_2 f_2\), ..., \(M_m f_m\) a la derecha.
Así que \(\tilde f\) es un pseudofuntor.
__________________________________
Descomposición única de pseudofuntores.Supongamos que para cadenas de longitud menor que \(\ell\)
un pseudofuntor tiene una descomposición única
como la concatenación de un encabezado inicial y una lista de pseudofuntores.
Veamos qué sucede con un pseudofuntor cuya cadena tiene longitud \(\ell\).
Supongamos que hay dos descomposiciones:
\(f \equiv H M_1 f_1 ... M_m f_m; \qquad f \equiv \tilde H N_1 g_1 ... N_n g _n\),
donde \(H,\tilde H\) son encabezados iniciales, \(M_j,N_j\), son numerales positivos,
\(f_j,g_j\), son pseudofuntores.
Como \(H\) y \(\tilde H\) son encabezados iniciales y comienzan en la misma posición de \(f\),
tienen el mismo signo inigial \(I\) (alguno de \(s,c,p,\kappa,\rho\)).
A continuación siguen dos numerales positivos en cada caso,
que es bastante claro que tienen que coincidir, porque estamos recorriendo la misma cadena \(f\) desde el principio.
O sea, \(H=\tilde H\).
Ahora, simplemente quitamos el encabezado inicial \(H\) y el primer numeral \(M_1\),
con lo cual obtenemos un pseudofunctor
\(\tilde f \equiv f_1 M_2 f_2 ... M_m f_m\).
Por igualdad de cadenas, tenemos también que:
\(\tilde f\equiv g_1 N_2 g_2 ... N_n g_n\).
Como la longitud del pseudofuntor \(\tilde f\) es estrictamente menor que \(\ell\),
debemos tener que ambas descomposiciones son iguales entre sí,
lo cual implica \(m=n,M_j=N_j,f_j=g_j\), todo \(j\).
___________________________________________________
Pseudofuntores válidos.Ahora vamos a restringir los pseudofuntores.
Decimos que un pseudofuntor \(f\) es
válido si:
\(f\equiv H M_1 f_1 .... M_m f_n\),
siendo \(H\) su encabezado inicial,
y \(M_j\) numerales, \(f_j\) pseudofuntores,
tales que:
Su encabezado inicial \(H\equiv I k n\) tiene signo inicial \(I\equiv s\) ó \(I\equiv c\),
numerales \(k=n=1\), y el valor de \(m\) es 0.
Su encabezado inicial \(H\equiv I k n\) tiene signo inicial \(I\equiv p\),
numerales \(1\leq k\leq n\), y el valor de \(m\) es 0.
Su encabezado inicial \(H\equiv I k n\) tiene signo inicial \(I\equiv \kappa\),
numerales \(k=1\), \(M_1\) igual al orden de \(f_1\), \(m=M_1\),
\(n=M_2=...=M_m\), e iguales respectivamente al orden de \(f_2,...,f_m\),
y además previamente ya eran válidos todos los \(f_j\).
Su encabezado inicial \(H\equiv I k n\) tiene signo inicial \(I\equiv \rho\),
numerales \(k=1\), \(m=2\), \(n=M_1+1\), \(M_2=M_1+2\),
y tal que \(M_1\) coincide con el orden de \(f_1\), y \(M_2\) con el orden de \(f_2\),
y además ya eran válidos \(f_1\) y \(f_2\).
Nos preguntamos si \(f\) es válido, ¿son válidos también los pseudofuntores \(f_j\)?
Creo yo que es bastante sencillo probar que esto es válido por inducción en la longitud de \(f\).
La clave está en que hemos puesto una definición bastante fuerte,
que exige que ya sean válidos los pseudofuntores componentes de un pseudofuntor válido.
_______________________________________
Aplicando pseudofuntores en funtores.Para cada pseudofuntor válido, asociaremos un funtor \(\phi(f)\) de \(\mathcal L_{ARP}\),
de la siguiente manera:
Primero anotamos la longitud \(\ell\) de la cadena \(f\).
Vamos a asignarle una cadena \(\phi(f)\) en forma de funtor, cuya longitud será igual o más corta.
Notamos además que el orden de un funtor siempre es menor que su longitud
(lo cual creo que es una sencilla prueba por inducción en la longitud del funtor).
Establecemos la lista de todos los funtores de orden menor que \(\ell\),
la denotamos \(f_1,...,f_r\), y ordenamos los funtores por su longitud como cadena.
Esto implica que si \(f_i\equiv I f_{j_0} ... f_{j_m}\),
para \(I\equiv \kappa\) ó \(I\equiv\rho\), y funtores \(f_{j_k}\),
necesariamente, por ser cadenas más cortas que \(f_i\),
los índices \(j_0,...,j_m\) serán menores que \(i\).
Si \(g\equiv s 1 1 \), asociamos \(\phi(g)\equiv S \).
\(\phi(g)\) es funtor de orden 1.
Si \(g\equiv c 1 1 \), asociamos \(\phi(g)\equiv c \).
\(\phi(g)\) es funtor de orden 1.
Si \(g\equiv p k n \), asociamos
\(\phi(g)\equiv p_k^n \).\(\phi(g)\) es funtor de orden n.
Si \(g\equiv \kappa 1 n \; m g_0 n_1 g_1 ... n_m g_m\),
asociamos \(\phi(g)\equiv \kappa \phi(g_0) \phi( g_1) ... \phi(g_m) \).
Si \(g\equiv \rho 1 n \; M_1 g_1 M_2 g_2\),
asociamos \(\phi(g)\equiv \rho \phi(g_1) \phi( g_2) \).
Por inducción en la longitud \(\ell\) de la cadena \(g\)
podemos probar que \(\phi(g)\) tiene longitud menor o igual que \(\ell\).
También podemos probar por inducción en la longitud \(\ell\) de \(g\)
que el orden de \(g\) coincide con el orden de \(\phi(g)\).
Así que \(\phi(g)\) es alguno de los funtores \(f_r\).
A continuación reordenamos los funtores de la lista,
de modo que \(f_r\) figure al final de ella.
Esto es coherente con nuestra ordenación basada en la longitud de las cadenas,
y así también compatible con la definición de funtor.
Debido a que el orden de \(g\) y \(\phi(g)\) coinciden,
no puede ocurrir que haya un pseudofuntor válido distinto \(\tilde g\),
con un orden distinto, tal que \(\phi(\tilde g)=\phi(g)\).
________________________________________________
Sobreyectividad de la aplicación de pseudofuntores válidos a funtores.Nos preguntamos si la función \(\phi\) es sobreyectiva.Si \(f\) es un funtor de orden \(n\),
tal que \(f\equiv I f_1...f_h\),
donde \(I\) es uno de \(S,c,p,\kappa,\rho\), \(h\geq 0\), \(f_1,...,f_h\), funtores
aplicamos inducción en la longitud \(\ell\) de la cadena \(f\),
y observamos que existen pseudofuntores válidos \(g_1,...,g_h\), tales que:
\(f_j\equiv \phi(g_j)\).
Si, por ejemplo, \(I\equiv\kappa\), tenemos que \(f_1\) tiene algún orden \(m\),
y \(f_2,...,f_h\), tienen algún orden común \(n\).
tenemos el pseudofuntor válido \(g\equiv H M_1 g_1 ... M_h g_h\),
donde \(H \equiv 1 n\), \(M_1 = m\), \(M_2 = ... = M_h = n\).
Cuando computamos su valor por \(\phi\), obtenemos:
\[\phi(g)\equiv \kappa \phi(g_1) \phi(g_2) ... \phi(g_h) \equiv \kappa f_1 f_2...f_h.\]
_________________________________________
Lema de irreducibilidad de funtores.Me gustaría probar lo siguiente:
Si \(f\) es un funtor, y si \(\hat f\) es otro funtor tal que \(f\equiv \hat f \tau\),
para alguna subcadena \(\tau\), entonces \(\tau\) es la cadena vacía.
Esto sería una propiedad de irreducibilidad de las cadenas que son funtores.
Sea \(f\) un funtor con longitud mínima tal que existen \(\hat f\) y \(\tau\)
tal que \(f\equiv \hat f\tau\) y \(\tau\) es no vacía.
Es más o menos fácil convencerse de que \(f\)
no puede tener signo inicial \(S,c,p\).
Si dicho signo inicial es \(\rho\), existen funtores \(f_1,f_2\), tales que
\(f\equiv \rho f_1 f_2\).
Al escribir \(f\equiv \hat f\tau\),
obtenemos funtores \(\hat f_1,\hat f_2\), tales que:
\(\hat f\equiv{ \color{red}\rho}\hat f_1\hat f_2\),
porque \(\hat f\) también comienza con \(\rho\).
Si \(f_1\) es subcadena estricta de \(\hat f_1\),
entonces \(\hat f_1\equiv f_1\tau_1\), para alguna cadena no vacía \(\tau_1\),
lo cual no puede ser, porque la longitud de \(\hat f_1\) es menor que la de \(f\).
Lo mismo si \(\hat f_1\) es subcadena estricta de \(f_1\).
Por lo tanto, \(f_1\equiv \hat f_1\).
Luego, obtenemos \(f_2\equiv \hat f_2\tau\),
que de nuevo contradice la longitud mínima de \(f\) con esta propiedad.
Si el signo inicial de \(f\) es \(\kappa\),
podemos razonar de manera similar,
escribiendo \(f\equiv \kappa f_0 f_1 ... f_m\equiv \hat f\tau\),
y observando, en forma inductiva (o iterativa),
que \(\tau\) no podría superponerse con \(f_0,f_1,...,f_m\),
porque en cada caso daría una contradicción.
Para explicarlo, notemos que podemos escribir
\(\hat f\equiv \kappa \hat f_0\hat f_1...\hat f_M\),
para ciertos funtores \(\hat f_j\).
Si \(\tau\) se superpone con \(f_0\),
entonces \(f_0\equiv \hat f_0\hat f_1...\hat f_M\sigma\),
para alguna cadena no vacía \(\sigma\), que comparte encabezamiento con \(\tau\).
Esto implica ahora que \(f_0\equiv \hat f_0\sigma_0\),
para alguna cadena \(\sigma_0\).
Pero la longitud de \(f_0\) es menor que la de \(f\), y esto no puede ser.
Así que \(\kappa f_0\) es subcadena de \(\hat f\).
Si fuesen iguales, entonces \(f_0\equiv \hat f_0\hat f_1...\hat f_M\equiv \hat f_0\xi\),
para alguna cadena \(\xi\), que tiene que ser no vacía, porque \(M\geq 1\),
y otra vez, por la minimalidad de la longitud de \(f\),
debemos tener que \(\xi\) es vacía, contradicción.
Por lo tanto \(\kappa f_0\) es subcadena estricta de \(\hat f\).
Tendremos \(f_0\tilde\tau\equiv \hat f_0\hat f_1...\hat f_M\).
Por minimalidad, no puede ser ni que \(f_0\) sea subcadena estricta de \(\hat f_0\),
ni tampoco que \(\hat f_0\) sea subcadena estricta de \(f_0\),
luego ambas son iguales.
\(f_0\equiv \hat f_0\).
En particular, ahora \(M=m\), pues ambos números son el orden común de \(f_0,\hat f_0\).
Podemos avanzar de manera similar con los demás funtores,
y entonces iremos encontrando que \(f_1\equiv \hat f_1\), \(f_2\equiv \hat f_2\),
y así sucesivamente.
Pero entonces nos encontramos conque \(\tau\) es vacía,
contradiciendo la hipótesis.
_________________________________________
La aplicación de pseudofuntores válidos a funtores es inyectiva.Ahora nos preguntamos si la función \(\phi\) es inyectiva.Vamos a suponer que para todo funtor de longitud menor que \(\ell\),
la función \(\phi\) tiene una única preimagen.
Supongamos que \(f\equiv \phi(g)\equiv \phi(\tilde g)\), siendo \(f\) un funtor cuya cadena tiene longitud \(\ell\).
Tenemos que \(g\) y \(\tilde g\) tienen el mismo orden \(n\),
como ya hemos visto.
Si el signo inicial es alguno de \(S,c,p\), es fácil convencerse de que \(g\equiv \tilde g\).
Así que si \(g\) y \(\tilde g\) difieren, el signo inicial de \(f\) será \(\kappa\) ó \(\rho\).
Supongamos por ejemplo el caso de signo inicial \(\kappa\).
Existen pseudofuntores válidos \(g_j\) y \(\tilde g_j\), tales que:
\(g\equiv H M_0 g_0 M_1 g_1 ... M_a g_a \),
\(\tilde g \equiv \tilde H \tilde M_0 \tilde g_0 \tilde M_1 \tilde g_1 ... \tilde M_\alpha \tilde g_\alpha\).
Aquí \(H,\tilde H\), son encabezados iniciales del tipo \(\kappa\),
con órdenes respectivos \(a=M_0,\alpha=\tilde M_0\).
Escribamos las respectivas descomposiciones del funtor \(f\) así:
\[f\equiv \kappa f_0 f_1 ... f_a.\]
\[f\equiv \kappa \tilde f_0 \tilde f_1 ... \tilde f_\alpha.\]
De manera que \(f_j\equiv \phi(g_j),\tilde f_j\equiv\phi(\tilde g_j)\).
El Lema previo nos permite afirmar que
ni \(f_0\) es subcadena de \(\tilde f_0\)
ni tampoco \(\tilde f_0\) es subcadena de \(f_0\).
Con lo cual \(f_0\equiv \tilde f_0\).
En particular, como la longitud de \(f_0\) es menor que \(\ell\),
debemos tener \(g_0\equiv \tilde g_0\),
y en particular coinciden los órdenes de "ambos" funtores,
por lo tanto \(a=\alpha\).
Luego seguimos razonando de forma iterativa,
y vemos que, recorriendo la cadena \(f\),
las cadenas \(f_1\) y \(\tilde f_1\) ahora comienzan en la misma posición,
y ambos son funtores, por lo cual ninguno es subcadena del otro,
y entonces \(f_1\equiv \tilde f_1\).
Esto se puede seguir haciendo para cada \(j\),
dando \(f_j\equiv \tilde f_j\).
Como todos estos son funtores de longitud menor que \(\ell\),
otra vez tienen única preimagen por \(\phi\),
por lo tanto \(g_j=\tilde g_j\), todo \(j\).
De paso, tendrán todos el mismo orden,
así que \(H\equiv \tilde H\),
y también \(M_j\equiv\tilde M_j\), todo \(j\).
Pero entonces hemos llegado a que \(g=\tilde g\),
como queríamos.
_______________________________________
Como Corolario, hemos probado en medio de estos cálculos,
que sólo hay una estructura posible de funtor,lo cual lo he deducido esencialmente del
Lema de Irreducibilidad de un funtor.O sea que no sé para qué diablos hice todo lo demás.

La cuestión de los pseudofuntores la introduje
pensando en que sería más simple de implementar
a la hora de analizar un algoritmo.
La sintaxis de un pseudofuntor es más simple,
y entonces se puede descartar más rápido si algo es o no un pseudofuntor.
Como la función inversa de \(\phi\) convierte un funtor en un pseudofuntor,
descartar un pseudofuntor sería equivalente a descartar una cadena que no es un funtor.
Luego, habría que analizar si el pseudofuntor es válido.
Me dio la sensación de que eso es más simple que analizar si una cadena con varios funtores en ella como subcadenas dan un funtor correcto o no.
De todos modos, es posible que no pueda evitarse recursividad en ese análisis,
pero sí que podría evitarse tener que enumerar previamente
cuál es la lista de los funtores \(f_1,...,f_r\), que dan lugar al funtor \(f=f_r\).
O sea. Me da la sensación de que los pseudofuntores válidos,
que son la contraparte de los funtores,
pueden descansar en la recursividad a ciegas,
sin conocimiento previo de cuáles eran los pseudofuntores componentes,
sino más bien ir descubriéndolos al recorrer la cadena.
En ese caso, un algoritmo recursivo sería más natural.
________________________
Como sea, aún no miré ningún algoritmo.
Sino que me limité a estudiar esto matemáticamente.
Si todo está bien, entonces aparentemente he demostrado la unicidad de los funtores,
en forma matemática, sin algoritmos.