Autor Tema: Comentarios a "La Aritmética Recursiva Primitiva"

0 Usuarios y 1 Visitante están viendo este tema.

04 Julio, 2023, 01:23 pm
Respuesta #150

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Aún no he terminado de leer el último mensaje (curiosamente, por tener vacaciones tengo menos tiempo para sentarme a leerlo ::)), pero dejo las erratas, dudas y comentarios que tengo de momento.

Queda claro que eres un rencoroso y que me la tenías guardada desde que te dije lo de \( n\geq 2 \).   :P

En cuanto al tiempo, no te preocupes, que no tenemos ninguna prisa.

Respecto a la segunda propiedad, creo que no hace falta demostrar tampoco nada porque en lo anterior se ha visto que \( z_1+z_2=G(z) \) y que \( G(z) \leq z \), ¿no?

Cierto.

Aquí había una pequeña errata y me parece que en algún lugar habría que especificar que dada una variable \( n \), la notación \( n_1, n_2 \) significa \( z_1(n), z_2(n) \), ¿no?

La errata, sí, pero, si te fijas en la definición de los funtores \( z_1 \) y \( z_2 \), no son \( z_1(n) \) y \( z_2(n) \), sino que \( z \) es ya la variable. Los funtores se llaman \( ()_1 \) y \( ()_2 \) desde el primer momento.

Esto no sería más bien \( \ell(s)=(1\dot{-}(1\dot{-} s))((s \dot{-} 1)_1+1) \) y que \( (s \dot{-} 1)_1=\ell(s)\dot{-}1 \).

Cierto.

Así, cada número natural no nulo \( s \) codifica una única sucesión.

[...]

Una comprobación rutinaria muestra que

\( p^\infty_i(\left<x_0,\ldots, x_{n-1}\right>^n_\infty)=x_i, \)

lo que prueba que toda sucesión finita de números naturales está codificada por un número natural.

Veo un poco confusas estas afirmaciones tal y como están hechas.

La primera nos dice que cada natural \( s \) codifica una única sucesión y esto está claro, pero para verlo formalmente, ¿no es mejor poner la afirmación más adelante cuando se vea claro que si es \( l=\ell(s) \) entonces \( s=\langle s_0, \cdots, s_{l \dot{-} 1} \rangle \)?

Me refería a que, antes, un mismo número natural codificaba una sucesión distinta de cada longitud posible, mientras que ahora cada número natural determina una única sucesión, de longitud fija. He aclarado la frase, pero no sé si esto responde a tu objeción o si hay algo más. Esto que digo se puede decir justo ahí, porque ahí es dónde introducimos el convenio que asocia una longitud fija a cada número natural.

Mientras que la segunda, veo que ambas cosas que se dicen son ciertas, pero no veo la relación clara entre ellas. Quiero decir que lo que dices sobre que "esto prueba que toda sucesión finita está codificada por un natural", ¿no es trivial simplemente por la definición de sucesión finita que hemos dado al ya saber que \( <x, y>_2 \) representa un único natural?

No sé si entiendo lo que planteas. Lo que digo es que, si cogemos una sucesión finita, como \( 3, 5, 0, 2, 2 \), a partir de ella podemos calcular el número natural \( s=\left<3, 5, 0, 2, 2\right>^5_\infty \), y ahora vemos que \( s \) tiene precisamente longitud \( 5 \) y que sus proyecciones son precisamente \( 3, 5, 0, 2, 2 \), por lo que el número que hemos calculado codifica la sucesión dada, permite recuperar a partir de él la sucesión dada.

No sé si esto responde a lo que dices.

05 Julio, 2023, 07:40 am
Respuesta #151

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Intentaré aquí dar la prueba de la unicidad de un funtor.


Mi estrategia consiste en cambiar el lenguaje de ARP.  8^)

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.  ::)

 >:D 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\).

______________

 :laugh: 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.

_________________________

 :laugh: 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.

__________________________________

 :laugh: 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\).

___________________________________________________

 :laugh: 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.

_______________________________________

 :laugh: 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)\).

________________________________________________

 :laugh: 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.\]

_________________________________________

 8^) 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.

_________________________________________

 :laugh: 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.  :banghead: :banghead:

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.




05 Julio, 2023, 10:34 am
Respuesta #152

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Todo aclarado respecto a mi anterior mensaje (excepto que se me acuse de rencoroso cuando solo he mirado con lupa cada pequeño detalle ::) :laugh:).

Bromas aparte, llega un nuevo paquete de erratas y dudas :P

Definimos

\( s\frown \left<n\right> = \color{red} (1\dot{-} s) \color{black}\left<n\right>_\infty+\color{red} (1\dot{-} (1\dot{-} s)) \color{black}\left<\ell(s),\left<(s\dot{-} 1)_2,n\right>_2\right>_2+1.
 \)

Supongo que es como lo que he cambiado en rojo, ¿no? (En el texto los términos en rojo estaban intercambiados entre sí).

También, por dejármelo completamente claro, estamos dando la definición de un funtor, no de un término, ¿no? E igualmente para la definición más general de concatenación.

Más en general, definimos

\( s\frown t = F(s, t, \ell(t)), \)

donde \( F \) es el funtor dado por

\( F(s, \color{red} t, \color{black} 0)=s,\qquad F(s, \color{red} t, \color{black} n+1)=F(s, \color{red} t, \color{black} n)\frown \left<t_n\right>. \)

Similarmente definimos \( s|^i= F(s, i, \ell(s)\dot{-} i) \), donde

\( F(s,i, 0)=\color{red} s_i \color{black},\qquad F(s, i, n+1)=F(s, i, n)\frown \left<s_{i+n}\right>. \)

Así, si \( i\leq \ell(s) \), se cumple que \( \ell(s|^i)=\ell(s)\dot{-} \color{red} i \color{black} \) y \( s=s|_i\frown  s|^i \).

Más explícitamente:
\( F|_x(x_1,\ldots, x_n) = \left<F(x_1,\ldots, x_n,0),\ldots, F(x_1,\ldots, x_n,n-1)\right>_{\color{red}\infty \color{black}}. \)

Teorema (Recursión completa) Si \( G \) es un funtor de rango \( n+2 \), existe un funtor \( F \) de rango \( n+1 \) tal que

\( F(x_1,\ldots, x_n, x)=G(x_1,\ldots, x_n, x, F|_x(x_1,\ldots, x_n)). \)

Demostración
Definimos un funtor \( H \) mediante

\begin{array}{r@{\ }c@{\ }l}
H(x_1,\ldots, x_n,0)&=&0,\\[1mm]
H(x_1,\ldots, x_n,x+1)&=&H(x_1,\ldots, x_n,x)\frown \left<G(x_1,\ldots, x_n, x, H(x_1,\ldots, x_n, x))\right>.
\end{array}

Y a su vez,
\( F(x_1,\ldots, x_n, x)=H(x_1,\ldots, x_n,x+1)_x. \)

Veamos que \( F \) cumple lo requerido. Por aligerar la notación escribiremos \( \bar x \) en lugar de \( x_1,\ldots, x_n \). En primer lugar, una simple inducción nos da que \( \ell(H(\bar x,x))=x \). En segundo lugar, \( H(\bar x, x)=F|_x(\bar x) \). En efecto, para \( x=0 \) es

\( H(\bar x,0)=0=F|_0(\bar x), \)

y si vale para \( x \), entonces, como \( \ell(H(\bar x, x+1))=x+1 \), la definición de \( H \) implica que

\( H(\bar x, x+1)=H(\bar x, x)\frown \left<H(\bar x, x+1)_x\right>, \)

luego por la hipótesis de inducción y la definición de \( F \):

\( H(\bar x, x+1)=F|_x(\bar x)\frown  \left<F(\bar x, \color{red} x \color{black})\right>=F|_{x+1}(\bar x) \).

Finalmente probamos por inducción que \( F \) cumple la propiedad del enunciado:

\( F(\bar x,0)=H(\bar x,1)_0=G(\bar x,0,0)=G(\bar x, 0, F|_0(\bar x)), \)

\( F(\bar x, x+1)=H(\bar x, x+2)_{x+1}=G(\bar x, x+1, H(\bar x, x+1))=G(\bar x, x+1, F|_{x+1}(\bar x)). \)
[cerrar]

Pequeña errata en la demostración.

Por ejemplo, ahora podemos definir la sucesión de Fibonacci en ARP:

\( F(0) = F(1) = 1, \quad F(n+1) = F(n\color{red}\dot{-}\color{black}1)+F(n). \)

Para ajustarnos al teorema anterior definimos el funtor

\( G(x, s) = \cases{1&si $\ell(s)\leq 1$,\cr s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}&si $\ell(s)\geq 2$,} \)

o, equivalentemente,

\( G(x, s) = \chi_{\color{blue}x\leq y\color{black}}(\ell(s), 1)+\chi_{\color{blue}x\leq y\color{black}}(2, \ell(s))( s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}), \)

de modo que \( F(n) = G(n, F|_n) \).

Aparte de la erratilla, en lo que he marcado en azul, es decir, en la fórmula que describe la función característica, ¿no sería mejor poner \( z \leq y \)?
Se (más bien creo) que no está mal tal cual está, porque realmente al sustituir en la función característica la \( x \) desaparece por completo y, realmente, tanto el término \(  \chi_{x\leq y}(\ell(s), 1) \) como en el otro, no tienen como variable a \( x \) (¿es esto que he dicho correcto?). Pero lo digo, más que nada, para que no haya confusión al ser también \( x \) la variable de \( G \).

Un saludo.

05 Julio, 2023, 11:02 am
Respuesta #153

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Intentaré aquí dar la prueba de la unicidad de un funtor.


Spoiler
Mi estrategia consiste en cambiar el lenguaje de ARP.  8^)

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.  ::)

 >:D 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\), como sigue: y los \( M_i \) numerales, ¿no?
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\).

______________

 :laugh: 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.

_________________________

 :laugh: 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.

__________________________________

 :laugh: 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\).

___________________________________________________

 :laugh: 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.

_______________________________________

 :laugh: 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 \).
\(\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)\).

________________________________________________

 :laugh: 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.\]

_________________________________________

 8^) 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 \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.

_________________________________________

 :laugh: 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.
[cerrar]

Te he marcado algún detalle en rojo. Había visto alguna erratilla más al leerlo, pero no recuerdo dónde.

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.  :banghead: :banghead:

En efecto, con el resultado de irreducibilidad es suficiente.

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.

Es que eso es lo que hace con los funtores el código que te puse: va leyendo la cadena de izquierda a derecha y descubriendo en cada paso lo que viene. Me parece que es lo más natural y, si tienes un algoritmo que aplica la definición de funtor y no ésta deja margen para hacer algo distinto de lo que hace, es que la estructura de cada funtor es única. Me parece que es la prueba más natural y más práctica, porque un argumento inductivo —aunque en última instancia se puede desarrollar hasta un algoritmo iterativo— no deja claro al principio como comprobar lo que usas por hipótesis de inducción.

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.

No veo ninguna diferencia esencial entre un algoritmo y una demostración inductiva como la que has dado del lema de irreducibilidad. Al fin y al cabo, lo que haces es distinguir casos y ver qué sucede en cada uno de ellos, y eso mismo es lo que hace el algoritmo: ver qué se puede decir en cada caso de modo que se cubran todas las posibilidades, con la ventaja de que no sólo te dice que la estructura es única, sino que de dice cómo averiguarla explícitamente leyendo la cadena de izquierda a derecha.

05 Julio, 2023, 11:25 am
Respuesta #154

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Todo aclarado respecto a mi anterior mensaje (excepto que se me acuse de rencoroso cuando solo he mirado con lupa cada pequeño detalle ::) :laugh:).

 >:D

Bromas aparte, llega un nuevo paquete de erratas y dudas :P

Definimos

\( s\frown \left<n\right> = \color{red} (1\dot{-} s) \color{black}\left<n\right>_\infty+\color{red} (1\dot{-} (1\dot{-} s)) \color{black}\left<\ell(s),\left<(s\dot{-} 1)_2,n\right>_2\right>_2+1.
 \)

Supongo que es como lo que he cambiado en rojo, ¿no? (En el texto los términos en rojo estaban intercambiados entre sí).

Sí, y además faltaba un paréntesis para que el +1 final sólo afecte al segundo caso.

También, por dejármelo completamente claro, estamos dando la definición de un funtor, no de un término, ¿no? E igualmente para la definición más general de concatenación.

En principio, sí, aunque es equivalente, pues hemos demostrado que todo término define un funtor.

Por ejemplo, ahora podemos definir la sucesión de Fibonacci en ARP:

\( F(0) = F(1) = 1, \quad F(n+1) = F(n\color{red}\dot{-}\color{black}1)+F(n). \)

Para ajustarnos al teorema anterior definimos el funtor

\( G(x, s) = \cases{1&si $\ell(s)\leq 1$,\cr s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}&si $\ell(s)\geq 2$,} \)

o, equivalentemente,

\( G(x, s) = \chi_{\color{blue}x\leq y\color{black}}(\ell(s), 1)+\chi_{\color{blue}x\leq y\color{black}}(2, \ell(s))( s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}), \)

de modo que \( F(n) = G(n, F|_n) \).

Aparte de la erratilla, en lo que he marcado en azul, es decir, en la fórmula que describe la función característica, ¿no sería mejor poner \( z \leq y \)?
Se (más bien creo) que no está mal tal cual está, porque realmente al sustituir en la función característica la \( x \) desaparece por completo y, realmente, tanto el término \(  \chi_{x\leq y}(\ell(s), 1) \) como en el otro, no tienen como variable a \( x \) (¿es esto que he dicho correcto?). Pero lo digo, más que nada, para que no haya confusión al ser también \( x \) la variable de \( G \).

Lo he cambiado, pero, en efecto, por lo que tú mismo señalas, de la otra forma también era correcto.

Bueno, creo que hará falta otro mensaje técnico un tanto aburrido, y luego ya podremos ver algo interesante.

05 Julio, 2023, 02:13 pm
Respuesta #155

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Todo aclarado ;)

Bueno, creo que hará falta otro mensaje técnico un tanto aburrido, y luego ya podremos ver algo interesante.

La verdad es que los últimos mensajes son muy técnicos y se hacen más duros de leer (no por ello no se disfrutan), pero la verdad es que poco nos puede faltar ya para tener herramientas con las que trabajar con los naturales ya de forma natural (valga la redundancia), ¿no?

Y, por curiosidad, ¿aun sigues de cerca el artículo que mencionaste al comienzo o ya te has desviado de él?

Un saludo.

06 Julio, 2023, 12:05 am
Respuesta #156

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La verdad es que los últimos mensajes son muy técnicos y se hacen más duros de leer (no por ello no se disfrutan), pero la verdad es que poco nos puede faltar ya para tener herramientas con las que trabajar con los naturales ya de forma natural (valga la redundancia), ¿no?

Yo creo que con lo visto en la respuesta #13 podemos considerar que ya hemos "desempaquetado" todo el potencial lógico de ARP. Los tecnicismos que aparecen en la respuesta #14 no se los podemos reprochar a ARP, sino que son consecuencia de que definir aritméticamente sucesiones de números naturales y los conceptos necesarios para manipularlas es intrínsecamente técnico y aparecerán necesariamente en cualquier teoría aritmética. De hecho, las posibilidades que ofrece ARP para definir funtores simplifican el tratamiento formal. En AP sería un poco más complicado.

En el próximo mensaje espero que podré llegar a formalizar en ARP la expresión de un número natural en una base \( n\geq 2 \) prefijada. Eso también requiere varios tecnicismos, pero que de nuevo no son culpa de que ARP sea demasiado débil o de que presente restricciones lógicas que dificulten el trabajo. Los tecnicismos se deben únicamente a que no tenemos más que números naturales a nuestra disposición (y ahora también sucesiones finitas de números naturales, imprescindibles si queremos hablar de la sucesión de cifras decimales de un número). Sin embargo, veremos que esos tecnicismos pueden aprovecharse para obtener mucho más que las expresiones decimales.

Y, por curiosidad, ¿aun sigues de cerca el artículo que mencionaste al comienzo o ya te has desviado de él?

No, el artículo de Goodman llega hasta la respuesta #13, aunque yo he ido mucho más despacio y detallando más las cosas, sobre todo pensando en presentarle a argentinator una exposición de una teoría aritmética sencilla de la forma más detallada y precisa posible.

06 Julio, 2023, 01:45 am
Respuesta #157

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
No, el artículo de Goodman llega hasta la respuesta #13, aunque yo he ido mucho más despacio y detallando más las cosas, sobre todo pensando en presentarle a argentinator una exposición de una teoría aritmética sencilla de la forma más detallada y precisa posible.

Bueno, en ese caso muchas gracias por las consideraciones.

En efecto, hay muchas cosas que un investigador como ese da por obvias, y que el resto de los mortales quedamos a medio entender, como quien llega al cine a mitad de la película.

Y ya que estamos, ¿cómo se traduce "Logic-free"?


12 Julio, 2023, 05:48 pm
Respuesta #158

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
Es obvio que toda sucesión en las condiciones de la definición de funtor se puede completar con una sucesión de funciones en las condiciones de la definición anterior, por lo que todo funtor denota al menos una función, que claramente es recursiva primitiva. Para probar la unicidad suponemos que hay un funtor que denota dos funciones distintas (es decir, que toman valores distintos sobre unos mismos números naturales). Distinguimos varios casos:

En principio, no estoy de acuerdo en que nada aquí sea "obvio".
Aunque las comprobaciones puedan ser fáciles.

No sé por qué me resulta más cómodo usar inducción en la longitud \(\ell\) de las cadenas de ARP.

No es que me parezca más natural, pues lo natural sería perseguir recursivamente la estructura de dichas cadenas,
pero por otra parte me da un método uniforme de deducción en todo el asunto,
que sólo tendría que abandonarlo cuando no dé más de sí.

___________________

Supondré que todo funtor \(f\) cuya cadena tiene longitud menor que \(\ell\)
denota una única función recursiva primitiva \(F_f\),
y que además, si \(f\) tiene orden \(n\), entonces \(F_f\) es función \(n\)-ádica.

Para el caso \(\ell=1\) tenemos la situación obvia de que
\(f\) es \(S\) o \(c\),
así que hay claramente un único funtor denotado por \(f\).

Sea \(f\) un funtor de longitud \(\ell>1\).
Si \(f\) es un funtor cuyo primer signo es uno de \(S,c,p\),
entonces la función denotada es clara, es única, y no voy a decir nada más.

Los casos complicados ocurren cuando el primer signo es \(\kappa\) ó \(\rho\).

Sea \(n\) el orden del funtor \(f\).
En el primer caso, hay únicos funtores \(f_0,f_1,...,f_m\), tales que

\[f\equiv \kappa f_0f_1...f_m.\]

El orden de \(f_0\) es \(m\) y el de las demás \(f_j\) es \(n\).

Como las longitudes de cada uno de ellos es menor que \(\ell\),
existen únicas funciones recursivas primitivas \(F_0,F_1,...,F_m\),
tales que cada \(f_j\) denota a \(F_j\), en forma respectiva,
tal que \(F_0\) es \(m\)-ádica,
y cada \(F_j\) es \(n\)-ádica.

Por definición, la función \(F=F_0(F_1,...,F_m)\)
es recursiva primitiva y es \(n\)-ádica.
Además, la regla 4 de denotación de funciones establece que
\(f\) denotará a la función \(F\).

Supongamos que hay otra función \(\tilde F\) denotada por \(f\).
Por la manera en que se han dado las reglas de denotación
(es decir, para \(f\) sólo vale usar la regla 4\),
tienen que existir funciones \(m\)-ádica \(\tilde F_0\),
y \(n\)-ádicas \(\tilde F_1,...,\tilde F_m\),
tales que \(\tilde F = \tilde F_0(\tilde F_1,...,\tilde F_m)\),
y de modo que

\[ \tilde F = \tilde F_0(\tilde F_1,...,\tilde F_m).\]

Además, las funciones \(\tilde F_0,\tilde F_1,...\tilde F_m\),
deben estar denotadas por los funtores \(f_0,f_1,...,f_m\), respectivamente.

Por unicidad, \(\tilde F_j=F_j\), todo \(j=0,1,...,m\).
Luego \(\tilde F=F\).

_________________________

Ahora bien. ¿es una prueba así convincente?

En ninguna parte tuve que apelar  a usar sucesiones decrecientes de naturales.
Creo que tampoco he usado razonamiento por contradicción.

Y he metido la existencia y unicidad de la función recursiva primitiva denotada por el funtor
como parte de una misma demostración,
lo cual tampoco sé si a todo el mundo le parece conveniente proceder así.

_________________________

Me parece un poco extraño estar definiendo "funciones en el aire",
llamarles luego" recursivas primitivas",
y finalmente ver si es que "calzan" con el conjunto de funtores construidos en ARP.

Además, ¿no hay algo de redundancia en "denotar" \(F\) a las funciones recursivas primitivas,
para luego volver a denotarlas con el lenguaje ARP?

Tal vez podría hacerse todo al mismo tiempo,
más o menos así:

1. Partimos de funciones recursivas elementales \(S,C,P_I^N\),
    que significarían las funciones
    "sucesor", "constante cero", "proyección \(I\)-ésima y \(N\)-ádica", respectivamente.

2. Consideramos las cadenas \(s,c,p_i^n\), de ARP, y les llamamos funtores elementales,
    en donde \(i,n\), estarían denotando numerales.

3. Armamos los pares elementales \((s,S),(c,C),(p_i^n,P_I^N)\),
    de modo que \(i,n\), sean los numerales correspondientes a los naturales \(I,N\).

Notar que estoy usando minúsculas para la sintaxis de ARP,
y mayúsculas para la semántica de ARP.


4. Ahora definitmos funtores de ARP igual que hasta ahora.

5. Y finalmente, definimos un par recursivo \((f,F)\), como un objeto tal que
    \(f\) es un funtor de ARP, de orden \(n\), digamos,
    y \(F\) es una función que se obtiene de la siguiente manera:
   
    Si \(f\) es \(s,c,p_i^j\),
    entonces \(F\) es la función tal que \((f,F)\) es un par primitivo.

    Si \(f\) tiene signo inicial \(\kappa\),
    y si \(f_0,f_1,...,f_m\), son funtores tales que
    \[f\equiv\kappa f_0f_1...f_m,\]
    y \(F_0,F_1,...,F_m\), son funciones tales que
    \((f_0,F_0),(f_1,F_1),...,(f_m,F_m)\),
    son pares recursivos
    entonces \((f,F)\) es un par recursivo para la función
    \(F=F_0(F_1,...,F_m)\).

    Algo análogo haríamos para el caso del signo \(\rho\).

Tras estas definiciones, habría que ver en qué orden conviene demostrar
que todo encaja bien, es decir, que los pares primitivos existen para cada funtor
como primera componente, que se obtienen de manera única, etc.

Creo que me sentiría más cómodo si agregara la longitud de cada funtor
como parte de la definición de los pares,
sospechando que eso simplificaría las demostraciones por inducción...

Finalmente, si para cada funtor \(f\) denoto \(\beta(f) = F\),
para el caso de su par recursivo \((f,F)\) correspondiente,
y habiendo demostrado que la descomposición de un par recursivo
en pares recursivos más pequeños es única (si no es elemental),
entonces estaría definiendo, por ejemplo para el caso \(\kappa\):

\(f\equiv \kappa f_0f_1... f_m\),
\(F=\beta(f) = \beta(f_0)(\beta(f_1),...,\beta(f_m)\).

No sé qué ventajas podría tener este enfoque.

En cualquier caso, la idea acá es definir las funciones recursivas primitivas
en términos de los funtores asociados, recursivamente.
De ese modo, la semántica estaría claramente descripta desde la sintaxis del lenguaje
desde un comienzo.

Aún así, creo que debo pulir mi propia idea...





12 Julio, 2023, 09:50 pm
Respuesta #159

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Citar
Es obvio que toda sucesión en las condiciones de la definición de funtor se puede completar con una sucesión de funciones en las condiciones de la definición anterior, por lo que todo funtor denota al menos una función, que claramente es recursiva primitiva. Para probar la unicidad suponemos que hay un funtor que denota dos funciones distintas (es decir, que toman valores distintos sobre unos mismos números naturales). Distinguimos varios casos:

En principio, no estoy de acuerdo en que nada aquí sea "obvio".
Aunque las comprobaciones puedan ser fáciles.

Si tienes una sucesión de funciones según la definición de funtor, lo que yo decía que es obvio es que siempre puedes asociarle una función a cada una, porque nada te impide aplicar la definición de "función denotada" a cada paso. Lo que no es inmediato es la unicidad.

No sé por qué me resulta más cómodo usar inducción en la longitud \(\ell\) de las cadenas de ARP.

No es que me parezca más natural, pues lo natural sería perseguir recursivamente la estructura de dichas cadenas,
pero por otra parte me da un método uniforme de deducción en todo el asunto,
que sólo tendría que abandonarlo cuando no dé más de sí.

___________________

Spoiler
Supondré que todo funtor \(f\) cuya cadena tiene longitud menor que \(\ell\)
denota una única función recursiva primitiva \(F_f\),
y que además, si \(f\) tiene orden \(n\), entonces \(F_f\) es función \(n\)-ádica.

Para el caso \(\ell=1\) tenemos la situación obvia de que
\(f\) es \(S\) o \(c\),
así que hay claramente un único funtor denotado por \(f\).

Sea \(f\) un funtor de longitud \(\ell>1\).
Si \(f\) es un funtor cuyo primer signo es uno de \(S,c,p\),
entonces la función denotada es clara, es única, y no voy a decir nada más.

Los casos complicados ocurren cuando el primer signo es \(\kappa\) ó \(\rho\).

Sea \(n\) el orden del funtor \(f\).
En el primer caso, hay únicos funtores \(f_0,f_1,...,f_m\), tales que

\[f\equiv \kappa f_0f_1...f_m.\]

El orden de \(f_0\) es \(m\) y el de las demás \(f_j\) es \(n\).

Como las longitudes de cada uno de ellos es menor que \(\ell\),
existen únicas funciones recursivas primitivas \(F_0,F_1,...,F_m\),
tales que cada \(f_j\) denota a \(F_j\), en forma respectiva,
tal que \(F_0\) es \(m\)-ádica,
y cada \(F_j\) es \(n\)-ádica.

Por definición, la función \(F=F_0(F_1,...,F_m)\)
es recursiva primitiva y es \(n\)-ádica.
Además, la regla 4 de denotación de funciones establece que
\(f\) denotará a la función \(F\).

Supongamos que hay otra función \(\tilde F\) denotada por \(f\).
Por la manera en que se han dado las reglas de denotación
(es decir, para \(f\) sólo vale usar la regla 4\),
tienen que existir funciones \(m\)-ádica \(\tilde F_0\),
y \(n\)-ádicas \(\tilde F_1,...,\tilde F_m\),
tales que \(\tilde F = \tilde F_0(\tilde F_1,...,\tilde F_m)\),
y de modo que

\[ \tilde F = \tilde F_0(\tilde F_1,...,\tilde F_m).\]

Además, las funciones \(\tilde F_0,\tilde F_1,...\tilde F_m\),
deben estar denotadas por los funtores \(f_0,f_1,...,f_m\), respectivamente.

Por unicidad, \(\tilde F_j=F_j\), todo \(j=0,1,...,m\).
Luego \(\tilde F=F\).
[cerrar]

_________________________

Ahora bien. ¿es una prueba así convincente?

En ninguna parte tuve que apelar  a usar sucesiones decrecientes de naturales.
Creo que tampoco he usado razonamiento por contradicción.

El problema de esa demostración es que en toda ella has fijado una sucesión \( f_1,\ldots, f_n \), y lo que has probado es que esa sucesión asigna una única función a cada funtor, pero en principio un mismo funtor puede definirse a partir de sucesiones distintas, y no veo que hayas probado que, aunque consideres otra sucesión, la función asociada al último funtor (común a ambas) será la misma en los dos casos.

En realidad, dos sucesiones sólo pueden diferir en el orden en que aparecen las funciones o en que contengan funciones inútiles, que no se usan al final en el cálculo de la última función, pero cuesta más probar eso que argumentar la unicidad como lo he hecho yo o, una alternativa que tal vez te guste más, apelando a la unicidad de la estructura de un funtor que ya has dado por demostrada.

Y he metido la existencia y unicidad de la función recursiva primitiva denotada por el funtor
como parte de una misma demostración,
lo cual tampoco sé si a todo el mundo le parece conveniente proceder así.

Aunque no te guste oír esto: no hay reglas. Si lo que dices es convincente, puedes meter todo lo que quieras en una misma demostración. El problema que yo le veo es el que ya te he dicho: que das por supuesto que un funtor está definido por una sucesión de funtores fija, cuando puede haber muchas distintas.

_________________________

Me parece un poco extraño estar definiendo "funciones en el aire",
llamarles luego" recursivas primitivas",
y finalmente ver si es que "calzan" con el conjunto de funtores construidos en ARP.

Además, ¿no hay algo de redundancia en "denotar" \(F\) a las funciones recursivas primitivas,
para luego volver a denotarlas con el lenguaje ARP?

No estoy seguro de entender el problema que planteas. En especial no entiendo lo de "llamarles luego". Hemos definido las funciones recursivas primitivas "en el aire", si quieres, igual que hemos definido los números naturales "en el aire", y luego hemos definido un lenguaje formal para hablar tanto de números naturales como de funciones recursivas primitivas. La misma duplicidad que encuentras entre las funciones y los funtores que las denotas es la que hay entre los números naturales y los numerales que los denotan.

"Fuera" tenemos los números naturales y las funciones recursivas primitivas, definimos un lenguaje dotado de numerales y funtores, y luego vemos que cada numeral denota un único número natural y cada funtor una única función recursiva primitiva, de modo que cada número natural es nombrado por un único numeral y cada función recursiva primitiva es denotada por un funtor. Aquí no digo "único" porque no hay tantos funtores como funciones recursivas primitivas, sino tantos funtores como definiciones posibles de funciones recursivas primitivas, pero dos definiciones completamente distintas pueden definir la misma función, en el sentido de que tomen los mismos valores sobre todos los argumentos.

Tal vez podría hacerse todo al mismo tiempo,
más o menos así:

1. Partimos de funciones recursivas elementales \(S,C,P_I^N\),
    que significarían las funciones
    "sucesor", "constante cero", "proyección \(I\)-ésima y \(N\)-ádica", respectivamente.

2. Consideramos las cadenas \(s,c,p_i^n\), de ARP, y les llamamos funtores elementales,
    en donde \(i,n\), estarían denotando numerales.

3. Armamos los pares elementales \((s,S),(c,C),(p_i^n,P_I^N)\),
    de modo que \(i,n\), sean los numerales correspondientes a los naturales \(I,N\).

Notar que estoy usando minúsculas para la sintaxis de ARP,
y mayúsculas para la semántica de ARP.


4. Ahora definitmos funtores de ARP igual que hasta ahora.

5. Y finalmente, definimos un par recursivo \((f,F)\), como un objeto tal que
    \(f\) es un funtor de ARP, de orden \(n\), digamos,
    y \(F\) es una función que se obtiene de la siguiente manera:
   
    Si \(f\) es \(s,c,p_i^j\),
    entonces \(F\) es la función tal que \((f,F)\) es un par primitivo.

    Si \(f\) tiene signo inicial \(\kappa\),
    y si \(f_0,f_1,...,f_m\), son funtores tales que
    \[f\equiv\kappa f_0f_1...f_m,\]
    y \(F_0,F_1,...,F_m\), son funciones tales que
    \((f_0,F_0),(f_1,F_1),...,(f_m,F_m)\),
    son pares recursivos
    entonces \((f,F)\) es un par recursivo para la función
    \(F=F_0(F_1,...,F_m)\).

    Algo análogo haríamos para el caso del signo \(\rho\).

Tras estas definiciones, habría que ver en qué orden conviene demostrar
que todo encaja bien, es decir, que los pares primitivos existen para cada funtor
como primera componente, que se obtienen de manera única, etc.

Creo que me sentiría más cómodo si agregara la longitud de cada funtor
como parte de la definición de los pares,
sospechando que eso simplificaría las demostraciones por inducción...

Finalmente, si para cada funtor \(f\) denoto \(\beta(f) = F\),
para el caso de su par recursivo \((f,F)\) correspondiente,
y habiendo demostrado que la descomposición de un par recursivo
en pares recursivos más pequeños es única (si no es elemental),
entonces estaría definiendo, por ejemplo para el caso \(\kappa\):

\(f\equiv \kappa f_0f_1... f_m\),
\(F=\beta(f) = \beta(f_0)(\beta(f_1),...,\beta(f_m)\).

No sé qué ventajas podría tener este enfoque.

En cualquier caso, la idea acá es definir las funciones recursivas primitivas
en términos de los funtores asociados, recursivamente.
De ese modo, la semántica estaría claramente descripta desde la sintaxis del lenguaje
desde un comienzo.

Aún así, creo que debo pulir mi propia idea...

El problema es que un objetivo fundamental en la lógica formal es independizar el lenguaje formal de su posible significado. Se trata de definir un lenguaje formal que pueda usar un formalista radical para demostrar cosas sin tener en cuenta para nada que los funtores denotan funciones recursivas primitivas. Más gráficamente, para que podamos decir que \( \mathcal L_{\rm arp} \) es realmente un lenguaje formal de pleno derecho, es esencial que un formalista radical pueda entender lo que es \( \mathcal L_{\rm arp} \) (en particular, qué son los funtores de \( \mathcal L_{\rm arp} \) ) sin necesidad de leer nada escrito en rojo en el hilo, sin necesidad de que entienda (o quiera admitir) que los funtores están pensados para denotar funciones. Si agrupas la definición de los funtores con la definición de las funciones recursivas primitivas estás obligando a un formalista radical que  quiera entender (formalistarradicalmente) la definición de funtor a tragarse una buena píldora semántica.

El hecho de que los funtores denotan funciones sirve para entender qué hacemos y por qué lo hacemos, pero el objetivo de la lógica formal es que se pueda trabajar con ARP olvidando que sus fórmulas significan algo. Una cosa es que des una definición formal e inmediatamente después la interpretes semánticamente, pero juntar en la misma definición la sintaxis con la semántica es ocultar un hecho fundamental: que la sintaxis está pensada para que funcione independientemente de la semántica.