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

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

27 Julio, 2023, 12:30 pm
Respuesta #240

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Perdón por no responder antes. Ayer estuve fuera y no pude encender el ordenador en todo el día.

¿Y qué prisa tenemos? Si crees que vas a cobrar el doble por trabajar más rápido... pues, ¡es cierto!

Ojala esto fuera cierto en la vida... ::)

La duda anterior está más que clara y ya he entendido bien el modo de demostrar las cosas en este ámbito de "formalizar lo formal" :laugh:

He leído ya casi todo el mensaje. Me quedan las sustituciones que ya es tarea para mañana porque esta tarde tengo que coger un tren que va para largo, pero para que te acuerdes de mi esta tarde ( >:D) te dejo todas las erratas y dudas que he encontrado.

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 $\mbox{Sub}(\zeta)$. Para la cadena vacía, definimos $\mbox{rang}(0)= 0$ y, para cadenas de longitud no nula, distinguimos varios casos:

Es un poco raro decir "las subcadenas propias de \( \mbox{Sub}(\zeta) \)", ¿no? Sería, o bien "las subcadenas propias de \( \zeta \)", o bien "los elementos de \( \mbox{Sub}(\zeta) \)", ¿no?

Funtores Vamos a definir un funtor monádico \( \mbox{rang} \) usando el penúltimo teorema de la respuests #17, es decir, que definiremos $\mbox{rang}(\zeta)$ suponiendo definido el rango de las subcadenas propias de $\mbox{Sub}(\zeta)$. Para la cadena vacía, definimos $\mbox{rang}(0)= 0$ y, para cadenas de longitud no nula, distinguimos varios casos:

  • \( \mbox{rang}({\color{blue} S}) = 1, \mbox{rang}({\color{blue}  c}) = 1 \)

  • Si \( \zeta_0 = {\color{blue}p} \) y existen números \( 1\leq k\leq \ell(\zeta) \) tales que \( \zeta = p^n_k \), entonces \( \mbox{rang}(\zeta) = n \).

  • Si \( \zeta_0 = {\color{blue}\kappa} \) y existen \( {\color{red}1 \leq} m, n\leq \ell(\zeta) \) y \( h\in \mbox{Sub}(\zeta) \) tales que \( \mbox{rang}(h) = m \) y existe \( g\in S_m(\mbox{Sub}(\zeta)) \) de modo que

    \( \textstyle \forall i< m\ \mbox{rang}(g_i)= n,\qquad \zeta = {\color{blue}\kappa} h g_0\cdots g_{m\dot-1}, \)

    entonces \( \mbox{rang}(\zeta)= n \).

  • Si \( \zeta_0 = {\color{blue} \rho} \) y existe \( {\color{red}1 \leq}n\leq \ell(\zeta) \) y cadenas \( g, h\in \mbox{Sub}(\zeta) \) de modo que \( \mbox{rang}(g) = n \), \( \mbox{rang}(h) = n+2 \) y \( \zeta = {\color{blue}\rho} gh \), entonces \( \mbox{rang}(\zeta)=n+1 \).

En cualquier otro caso, \( \color{red}\mbox{rang}(\zeta)=0 \).

A parte de las erratillas, siendo un poco masoca, para la definición del funtor \( \mbox{rang} \) siguiendo el teorema de recursión formalmente, la \( G \) necesaria es la siguiente, ¿no?

\( G(x,y)=\begin{cases}
1 & \text{si} & x={\color{blue}S} \vee x={\color{blue}c}\\
n & \text{si} & x_0={\color{blue}p} \wedge \exists k \leq \ell(x) (k \geq 1 \wedge x=p_k^n)\\
n & \text{si} & x_0={\color{blue}\kappa} \wedge \exists m,n \leq \ell(x) \exists h \in \text{Sub}(x) (m \geq 1 \wedge n \geq 1 \wedge y(h)=m \wedge \exists g \in S_m(\text{Sub}(x)) (\forall i < m y(g_i)=n \wedge x={\color{blue}\kappa}hg_0 \cdots g_{m \dot{-}1}))\\
n+1 & \text{si} & x_0={\color{blue} \rho} \wedge \exists n \leq \ell(x) \exists g,h \in \text{Sub}(x) (n \geq 1 \wedge y(g)=n \wedge y(h)=n+2 \wedge x={\color{blue} \rho}gh)\\
0 & \text{si} & \text{no se da ningún caso anterior}\\
\end{cases} \)

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} s} \) (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).

¿A que te refieres con "suprimiendo precisiones técnicas"?

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
    {\color{red} \cancel{F(\zeta, n+1) =}} \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.
[cerrar]

A parte de la errata que he marcado en la demostración, en esto:

Citar
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.

En general (incluso aunque no sea \( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}}) \)), si \( \ell(\zeta)\geq n \) lo que quieres decir con este párrafo es que se puede ver que \( R(\zeta,n) = \zeta|^{n} \), ¿no?

En este caso, no me atrevo a dar explícitamente la "\( G \)" necesaria para definir el funtor \( PF \) (sobre todo por el caso de la composición donde se define otro funtor más de por medio) :laugh:

Enumeración de funtores Es interesante observar que podemos enumerar los funtores de 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

¿Lo que he marcado en rojo no deberías ser \( {\color{blue}\mathcal L_{\rm arp}} \)?

Mientras lo que he marcado en verde no lo veo del todo claro. Entiendo que quieres decir que \( {\color{blue} \kappa} \frown {\color{blue} S} \frown f > f \), pero esto no lo veo tan claro. Básicamente, lo que queremos probar es que \( \langle 4 \rangle \frown \langle 1 \rangle \frown s > s \), ¿no? ¿Pero esto como se prueba? Porque por inducción (formal) no lo veo sencillo porque no veo la relación entre \( s \) y \( s+1 \) como sucesiones. No se si me estoy perdiendo algún detalle, pero creo que hasta ahora no habíamos compardo nunca el orden entre dos sucesiones de esta forma, ¿no?

A su vez:

\( f_0 = \mu g\leq {\color{blue}S}(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})),\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^{\color{red} n}_{k+1} = \mbox{SFR}(f^{\color{red} n}_k),
 \)

A parte de la errata, ¿por qué no definir directamente \( f_0 = \color{blue} S \)?

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 \( \color{red} 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 \).
[cerrar]

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({\color{red} \zeta})=1, \)

[...]

3. Si \( f\equiv \mbox{PF}(\zeta) \) es un funtor, llamamos \( m\equiv \mbox{rang}(f) \) y establecemos que \( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \) si

\( \exists t\in S_m(\mbox{Sub}(\zeta){\color{red})}(\forall i<m\ {t_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})}\land \zeta = ft_{\color{red} 0}\cdots t_{\color{red} m \dot{-}1}). \)

En cualquier otro caso, \( t\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_{\color{red} 0}\cdots t_{\color{red} 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
[...]

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

Falta un entorno matemático en lo que he marcado en rojo.

También es claro que si \( \alpha \) es una fórmula (metamatemática) de ARP, entonces

\( \mathop\vdash\limits_{\color{red}\rm ARP}{\color{blue}\alpha}\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}). \)

Diremos que \( \theta \) es una expresión de 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}}).
 \)

Lo que he marcado en naranja debería ser \( \color{blue}\mathcal L_{\rm arp} \), ¿no?

Un saludo.

27 Julio, 2023, 01:28 pm
Respuesta #241

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
He leído ya casi todo el mensaje. Me quedan las sustituciones que ya es tarea para mañana porque esta tarde tengo que coger un tren que va para largo, pero para que te acuerdes de mi esta tarde ( >:D) te dejo todas las erratas y dudas que he encontrado.

 >:(   Aprovechando que las matemáticas me lo permiten, te bajo el sueldo a la mitad.

Es un poco raro decir "las subcadenas propias de \( \mbox{Sub}(\zeta) \)", ¿no? Sería, o bien "las subcadenas propias de \( \zeta \)", o bien "los elementos de \( \mbox{Sub}(\zeta) \)", ¿no?

Sí, mezclé dos ideas en la misma frase. Quería decir "las subcadenas propias de \( \zeta \)" y luego aclarar que, formalmente, eso son los elementos de \( \mbox{Sub}(\zeta) \).

A parte de las erratillas, siendo un poco masoca, para la definición del funtor \( \mbox{rang} \) siguiendo el teorema de recursión formalmente, la \( G \) necesaria es la siguiente, ¿no?

\( G(x,y)=\begin{cases}
1 & \text{si} & x={\color{blue}S} \vee x={\color{blue}c}\\
n & \text{si} & x_0={\color{blue}p} \wedge \exists k \leq \ell(x) (k \geq 1 \wedge x=p_k^n)\\
n & \text{si} & x_0={\color{blue}\kappa} \wedge \exists m,n \leq \ell(x) \exists h \in \text{Sub}(x) (m \geq 1 \wedge n \geq 1 \wedge y(h)=m \wedge \exists g \in S_m(\text{Sub}(x)) (\forall i < m y(g_i)=n \wedge x={\color{blue}\kappa}hg_0 \cdots g_{m \dot{-}1}))\\
n+1 & \text{si} & x_0={\color{blue} \rho} \wedge \exists n \leq \ell(x) \exists g,h \in \text{Sub}(x) (n \geq 1 \wedge y(g)=n \wedge y(h)=n+2 \wedge x={\color{blue} \rho}gh)\\
0 & \text{si} & \text{no se da ningún caso anterior}\\
\end{cases} \)

Pues... se te da mucho mejor que a mí encontrar erratas, pero, en principio, lo veo bien.

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} s} \) (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).

¿A que te refieres con "suprimiendo precisiones técnicas"?

Si comparas con la definición del rango un poco más arriba, me refiero a que no estoy diciendo: "Existe una \( g \), que es una sucesión de longitud \( m \) en \( \mbox{Sub}(f) \), tal que para todo \( i<\ell(g) \) se cumple que \( g_i \) es un funtor y..."

Citar
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.

En general (incluso aunque no sea \( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}}) \)), si \( \ell(\zeta)\geq n \) lo que quieres decir con este párrafo es que se puede ver que \( R(\zeta,n) = \zeta|^{n} \), ¿no?

Sí.

En este caso, no me atrevo a dar explícitamente la "\( G \)" necesaria para definir el funtor \( PF \) (sobre todo por el caso de la composición donde se define otro funtor más de por medio) :laugh:

La definición de ese funtor no formaría parte de la definición de \( G \), sino que habría que definirlo antes y luego usarlo en la definición de \( G \). Con esto no te estoy animando a que escribas \( G \) explícitamente. No se gana nada con ello.

Enumeración de funtores Es interesante observar que podemos enumerar los funtores de 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

¿Lo que he marcado en rojo no deberías ser \( {\color{blue}\mathcal L_{\rm arp}} \)?

Mientras lo que he marcado en verde no lo veo del todo claro. Entiendo que quieres decir que \( {\color{blue} \kappa} \frown {\color{blue} S} \frown f > f \), pero esto no lo veo tan claro. Básicamente, lo que queremos probar es que \( \langle 4 \rangle \frown \langle 1 \rangle \frown s > s \), ¿no? ¿Pero esto como se prueba? Porque por inducción (formal) no lo veo sencillo porque no veo la relación entre \( s \) y \( s+1 \) como sucesiones. No se si me estoy perdiendo algún detalle, pero creo que hasta ahora no habíamos compardo nunca el orden entre dos sucesiones de esta forma, ¿no?

No me había parado a pensarlo. Ahora mismo se me ha hecho tarde, pero te contesto a esto en cuanto pueda. (Pero sí, yo había dado por hecho que \( x\frown y > y \), y tiene pinta de ser cierto.)

A su vez:

\( f_0 = \mu g\leq {\color{blue}S}(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})),\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^{\color{red} n}_{k+1} = \mbox{SFR}(f^{\color{red} n}_k),
 \)

A parte de la errata, ¿por qué no definir directamente \( f_0 = \color{blue} S \)?

Cierto.

27 Julio, 2023, 04:24 pm
Respuesta #242

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Mientras lo que he marcado en verde no lo veo del todo claro. Entiendo que quieres decir que \( {\color{blue} \kappa} \frown {\color{blue} S} \frown f > f \), pero esto no lo veo tan claro. Básicamente, lo que queremos probar es que \( \langle 4 \rangle \frown \langle 1 \rangle \frown s > s \), ¿no? ¿Pero esto como se prueba? Porque por inducción (formal) no lo veo sencillo porque no veo la relación entre \( s \) y \( s+1 \) como sucesiones. No se si me estoy perdiendo algún detalle, pero creo que hasta ahora no habíamos compardo nunca el orden entre dos sucesiones de esta forma, ¿no?

Se cumple que \( t>0\rightarrow s<t\frown s \). Por inducción sobre la longitud de \( t \), basta probarlo cuando \( \ell(t) = 1 \), es decir, que basta probar que \( s<\left<m\right>_\infty\frown s \).

Como la prueba (al menos, la que he encontrado) es bastante fea, doy primero un argumento que, curiosamente, prueba que la afirmación es cierta y muestra claramente por qué, pero no sirve como demostración.

Cuasidemostración
De la definición de par ordenado se sigue inmediatamente que

\( x<x'\land y\leq y'\rightarrow \left<x, y\right>_2<\left<x', y'\right>_2 \)

Por otra parte, también sabemos que \( x+y \leq \left<x, y\right>_2 \). Por lo tanto:

\( s_0\leq \left<m, s_0\right>_2 \),

\( \left<s_0, s_1\right>_2\leq \left<\left<m, s_0\right>_2, s_1\right>_2 = \left<m, s_0, s_1\right>_3 \)

\( \left<s_0, s_1, s_2\right>_3 = \left<\left<s_0, s_1\right>_2, s_2\right>_2 \leq \left<\left<m, s_0, s_1\right>_3, s_2\right>_2 = \left<m, s_0, s_1, s_2\right>_4 \)

Así podemos seguir hasta que nos cansemos y, cuando nos cansamos, concluimos:

\( \left<s_0, s_1, s_2\right>_\infty = \left<2, \left<s_0, s_1, s_2\right>_3\right>_2<\left<3, \left<m, s_0, s_1, s_2\right>_4\right>_2 = \left<m, s_0, s_1, s_2\right>_\infty = \left<m\right>_\infty\frown \left<s_0, s_1, s_2\right>_\infty \).

Esto demuestra que no existen contraejemplos al teorema, pero no puede convertirse en una demostración porque la \( n \) en \( \left<s_0, \ldots, s_{n-1}\right>_n \) no es una variable, sino necesariamente un número natural metamatemático, y no es posible formular así una inducción sobre \( n \) formalizada en ARP.
[cerrar]

Para dar una prueba válida, tenemos que recurrir a la definición de las proyecciones \( p^\infty_n \), que está en la respuesta #14, pero la copio aquí para facilitar la lectura:

Para definir las proyecciones definimos primero el funtor

\( R(s, 0)=(s\dot{-} 1)_2,\qquad R(s, i+1)=R(s, i)_1. \)

\( p^\infty_i(s)=\begin{cases}{R\bigl(s, (s\dot{-}1)_1\bigr)}&\text{si}& i=0,\\
R\bigl(s, (s\dot{-} 1)_1\dot{-} i\bigr)_2& \text{si}& i>0.\end{cases} \)

Notemos que \( p^\infty_i(s) \) es un funtor de rango \( 2 \), es decir, que ahora no tenemos infinitos funtores de rango \( 1 \), sino que tanto \( i \) como \( s \) son argumentos de un mismo funtor.

Ejemplo Si \( s= \left<3, 2, 7\right>_\infty=\left<2, \left<\left<3,2\right>_2, 7\right>_2\right>_2+1 \), tenemos que

\( R(s, 0)=\left<\left<3,2\right>_2, 7\right>_2,\quad R(s, 1)=\left<3,2\right>_2,\quad R(s, 2)=3, \)

luego \( p^\infty_0(s)=R(s,2)=3 \), \( p^\infty_1(s)=R(s, 1)_2=2 \), \( p^\infty_2(s)=R(s, 0)_2=7 \).

Nota A partir de ahora escribiremos \( s_i\equiv p^\infty_i(s) \).

Demostración
Sea \( n\geq 1 \) y \( \ell(s) = n+1 \).

Entonces \( s\dot- 1 = \left<n, x\right>_2 \). Definimos \( s^* = \left<n\dot- 1, x_1\right>_2+1 \), de modo que \( \ell(s^*) = n \).

Por definición del funtor \( R \), tenemos que

\( R(s, 0) = (s\dot-1)_2 = x \),      \( R(s, 1) = R(s, 0)_1 = x_1 \),      \( R(s^*, 0) = (s^*\dot-1)_2 = x_1 = R(s, 1) \).

Vamos a probar por inducción que \( R(s^*, i) = R(s, i+1) \). Lo acabamos de probar para \( i=0 \). Supuesto cierto para \( i \),

\( R(s^*, i+1) = R(s^*, i)_1 = R(s, i+1)_1 = R(s, i+2). \)

Ahora observamos que

\( s^*_0 = p^\infty_0(s^*) = R(s^*, (s^*\dot-1)_1) = R(s^*, n\dot-1) = R8s, n) = R(s, (s\dot-1)_1) = p^\infty_0(s)=s_0 \).

Veamos que \( \forall i<n\ s^*_i = s_i \). Lo tenemos probado para \( i=0 \). Si es cierto para \( i \) y se cumple \( i+1<n \), entonces

\( s^*_{i+1} = p^\infty_{i+1}(s^*) = R(s^*, (s^*\dot-1)_1\dot-(i+1))) = R(s^*,(n\dot-1)\dot-(i+1)) = R(s,n\dot-(i+1))= R(s, (s\dot-1)_1\dot-(i+1))) = p^\infty_{i+1}(s) = s_{i+1} \).

Como \( \ell(s^*) = n \), hemos probado que \( \forall i<\ell(s^*) s^*_i = s_i \), lo que implica que \( s^* = s|_n \).

Volvemos ahora a la igualdad \( R(s^*,0) = x_1 = R(s,0)_1 \), que ahora se convierte en \( R(s|_n, 0) = R(s, 0)_1 \).

Por otra parte, \( s_n = p^\infty_n(s) = R(s, n\dot-n)_2 = R(s, 0)_2 \).

Así pues, como \( R(s, 0)_1 = R(s|_n, 0) \) y \( R(s, 0)_2 = s_n \), tenemos que

\( R(s,0) = \left<R(s|_n, 0), s_n\right>_2 \),

siempre que \( \ell(s) = n+1 \) y \( n\geq 1 \). Más en general, si \( \ell(s)\geq n+1\geq 2 \), aplicando esto a \( s|_{n+1} \), concluimos que

\( R(s|_{n+1},0) = \left<R(s|_n, 0), s_n\right>_2 \).

Ahora vamos a probar que si \( 1\leq n\leq \ell(s) \), se cumple que

\( R(s|_n, 0) \leq R(\left<m\right>_\infty\frown s|_n, 0) \).

Por inducción sobre \( n \). Para \( n = 1 \) se cumple que
\( s|_1 = \left<0, s_0\right>_2+1,\qquad \left<m\right>_\infty\frown s|_1=\left<1, \left<m, s_0\right>_2\right>_2+1 \).

Por lo tanto, \( R(s|_1, 0) = s_0 \leq \left<m, s_0\right>_2 = R(\left<m\right>_\infty\frown s|_1,0). \)

Si vale para \( n\geq 1 \), entonces, por la fórmula azul (aplicada a \( s|_{n+1} \) en la primera igualdad y a \( \left<m\right>_\infty\frown s|_{n+1} \) en la última) y la hipótesis de inducción (y aquí es donde se aplica la idea de la cuasidemostración anterior):

\( {\color{blue}R(s|_{n+1},0) = \left<R(s|_n, 0), s_n\right>_2}\leq \left<R(\left<m\right>_\infty\frown s|_n, 0), s_n\right>_2={\color{blue}\left<R((\left<m\right>\frown s)|_{n+1},0), s_n\right>_2 = R((\left<m\right>_\infty\frown s)|_{n+2},0) }= R(\left<m\right>\frown s|_{n+1},0). \)

En particular, para \( n = \ell(s)\geq 1 \), tenemos que

\( R(s, 0) \leq R(\left<m\right>_\infty\frown s, 0) \),

y a su vez:

\( s = \left<n\dot- 1,R(s, 0)\right>_2+1 < \left<n, R(\left<m\right>_\infty\frown s,0)\right>_2 +1= \left<m\right>\frown s \).

Si \( s = 0 \) la desigualdad es obvia.
[cerrar]

28 Julio, 2023, 11:29 am
Respuesta #243

Eparoh

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

>:(   Aprovechando que las matemáticas me lo permiten, te bajo el sueldo a la mitad.

La maldición (o virtud) del cero :'(

Las dudas están todas claras, salvo esto de la última demostración:

Si vale para \( n\geq 1 \), entonces, por la fórmula azul y la hipótesis de inducción (y aquí es donde se aplica la idea de la cuasidemostración anterior):

\( R(s|_{n+1},0) = \left<R(s|_n, 0), s_n\right>_2\leq \left<R(\left<m\right>_\infty\frown s|_n, 0), s_n\right>=R(\left<m\right>\frown s|_{n+1},0). \)

Veo que la primera igualdad es por lo azul. La desigualdad, contando que haya una errata y le falte el subíndice \( 2 \), supongo que es consecuencia de la hipótesis de inducción y de esto

De la definición de par ordenado se sigue inmediatamente que

\( x<x'\land y\leq y'\rightarrow \left<x, y\right>_2<\left<x', y'\right>_2 \)

Pero, la última igualdad no la veo. ¿Es ahí donde dices que se usa la idea de la cuasidemostración? ¿O con eso te referías a la desigualdad?

Por último, solo por curiosidad, ¿cómo llegas a estas demostraciones? Porque, aunque entiendo todos los pasos, yo no me veo capaz de llegar a algo así ni en un millón de años...

Voy a ponerme ahora con la sustitución, a ver si termino de leerlo esta mañana y me subes de nuevo el sueldo :laugh:

Un saludo.

28 Julio, 2023, 12:36 pm
Respuesta #244

Eparoh

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

Parece que esta vez me he adelantado ;D

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 \( t\in S_m(\mbox{Sub}(\zeta)) \) tal que \( \forall i<m\ t_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^tt_1\cdots S_x^tt_m. \)
En cualquier otro caso, definimos \( S_x^t\zeta = 0 \).

Un par de dudas:

  • La sustitución debemos entenderla como un funtor triádico definido mediante el teorema de recursión de la respuesta #17, tal que si \( x \) no es una variable, \( t \) no es un término y \( \zeta \) no es una expresión entonces vale \( 0 \), o debemos entenderlo como que para cada variable \( x \) y término \( t \) definimos mediante el teorema de recursión de la respuesta #17 un funtor monádico.
  • Se te ha olvidado definir la sustitución sobre las fórmulas :P

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 {\color{red}\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}}){\color{red} \cancel{)}}\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}. \)

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

¿Con introducir notación rutinaria a que te refieres en este caso?

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.

Una cuestión sobre este caso en concreto. Al formalizar la definición, se definiría un funtor \( S_{x_1\cdots x_n}^{t_1\cdots t_n}\theta \) para cada \( n \) metamatemático o sería un único funtor triádico que cubriese todos los casos, teniendo en cuenta que los argumentos fueran sucesiones de \( n \) variables, \( n \) términos, etc.

Un saludo.

28 Julio, 2023, 02:11 pm
Respuesta #245

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero, la última igualdad no la veo. ¿Es ahí donde dices que se usa la idea de la cuasidemostración? ¿O con eso te referías a la desigualdad?

Me refería a la desigualdad. La última igualdad sale también de la fórmula azul aplicada a \( \left<m\right>_\infty\frown s|_{n+1} \) y teniendo en cuenta que \( (\left<m\right>_\infty\frown s|_{n+1})|_n = \left<m\right>_\infty\frown s|_n \), pues en ambos casos estamos eliminando el último término de la sucesión.

Por último, solo por curiosidad, ¿cómo llegas a estas demostraciones? Porque, aunque entiendo todos los pasos, yo no me veo capaz de llegar a algo así ni en un millón de años...

Pues eso no es fácil de explicar, pero el principio es que tienes que partir de que si algo es elemental (en el sentido de que es una relación entre cosas finitas que no involucra ningún infinito por ningún lado) entonces tiene que poder probarse en ARP y, en teoría, para encontrar la prueba sólo tienes que encontrar un argumento claro y concluyente de por qué tiene que ser así, y entonces no debería ser difícil formalizarlo. En este caso en concreto la teoría falla un poco, porque el argumento claro y concluyente es la cuasidemostración:

La reducción inicial es evidente: basta probar \( s<\left<m\right>_\infty\frown s \). Pongamos por ejemplo que queremos probar que \( \left<2, 7\right>_\infty <\left<3, 2, 7\right>_\infty \). Esto es lo mismo que

\( \left<1, \left<2, 7\right>_2\right>_2+1 <\left<2, \left<3, 2, 7\right>_3\right>_2+1 \),

luego lo que hay que probar es que \(  \left<2, 7\right>_2\leq \left<3, 2, 7\right>_3 \) o, en general:

\( \left<s_0,\ldots, s_n\right>_n\leq \left<m, s_0, \ldots, s_n\right>_{n+1} \).

Y aquí es donde aparece la maldición diabólica, y es que no podemos enunciar esto así cuando \( n \) no es un número concreto, sino que meramente \(  = \ell(s) \), para un \( s \) arbitrario. Luego el problema esencial es cómo escribir esto sin hacer referencia a funtores \( \left<\right>_n \) concretos. Esto nos lleva a que nuestra única arma es la definición de las proyecciones \( p^\infty_n \) (donde aquí \( n \) sí que es una variable arbitraria) y con ellas al funtor \( R \) que usamos para definirlas.

Observamos entonces que si tengo un \( s \) arbitrario (no nulo), lo que hemos visto es que basta probar que, considerando a \( s\dot-1 \) y a \( \left<m\right>_\infty \frown s\dot-1 \) como pares ordenados, la segunda componente del primero es menor o igual que la del segundo, y esto, en términos de \( R \) es que

\( R(s, 0) \leq R(\left<m\right>_\infty\frown s, 0) \).

Esto expresa en general la relación  \(  \left<2, 7\right>_2\leq \left<3, 2, 7\right>_3 \) o \( \left<2, 7, 5, 9\right>_4\leq \left<3, 2, 7, 5, 9\right>_5 \), etc.  Y lo que muestra la cuasidemostración es que esto se debe a que

\( \left<2, 7, 5, 9\right>_4= \left<\left<2, 7, 5\right>_3, 9\right>_2\qquad \left<3, 2, 7, 5, 9\right>_5 = \left<\left<3, 2, 7, 5\right>_4, 9\right>_2\ \).

Así: las dos sucesiones que queremos comparar son pares ordenados con la misma segunda componente, y es claro que

\( \left<2, 7, 5\right>_3\leq \left<3, 2, 7, 5\right>_4\rightarrow \left<2, 7, 5, 9\right>_4\leq\left<3, 2, 7, 5, 9\right>_5 \),

lo que permite una prueba por inducción, pero para ello hay que probar (y, lo más difícil, enunciar) en general la relación azul. Aquí es donde tenemos que tener en cuenta que

\( \left<3, 2, 7, 5\right>_4 = R(\left<3, 2, 7, 5\right>_\infty,0) \)

por lo que, lo que la relación azul, enunciada en general, es que si \( \ell(s) = n+1 \), entonces \( R(s, 0)= \left<R(s|_n, 0), s_n\right> \), y esto es precisamente la fórmula azul de la demostración (bueno, la igualdad previa, de la cual se deduce inmediatamente la fórmula azul).

Lo que expresa esa fórmula es que si pensamos en \( s \) como una sucesión finita, entonces \( R(s, 0) \) no es más que el número natural que codifica esa misma sucesión finita, pero con longitud fija (lo que NO podemos expresar diciendo que si \( s = \left<s_0, \ldots, s_{n-1}\right>_\infty \), entonces \( R(s, 0) = \left<s_0, \ldots, s_{n-1}\right>_n \)) y que, por lo tanto, \( R(s, 0) \) es el par ordenado que tiene como primera componente la sucesión con un término menos, y como segunda componente el término que falta.

Así pues, ya hemos reducido el problema a algo muy concreto y puramente técnico: la igualdad

\( R(s, 0)= \left<R(s|_n, 0), s_n\right> \).

Ahora bien, si \( \ell(s)=n+1 \), en principio tenemos que

\( R(s, 0) = \left<R(s, 1), x\right>_2 \)

y, viendo ejemplos concretos y yendo a la definición de \( p^\infty_n \), es fácil ver que \( x = p^\infty_n(s) = s_n \). La parte que me resultó más difícil fue probar que \( R(s, 1) = R(s|_n, 0) \), hasta que vi que el truco era recurrir a que las proyecciones \( p^\infty_i \) determinan cada número natural. En el fondo era lógico, pues las proyecciones son lo único que tenemos para hablar de sucesiones genéricas.

El truco era pensar que los dos miembros de \( R(s, 1) = R(s|_n, 0) \) tienen que ser la sucesión \( s|_n \), pero vista como sucesión de longitud fija \( n \) (la determinada por el funtor \( \left<\right>_n \) que NO existe cuando \( n \) es genérico) y la forma de probar la igualdad es encapsularlas en una sucesión usual (dada por \( \left<\right>_\infty \)). La sucesión usual que tiene a \( R(s|_n, 0) \) como segunda componente es \( s|_n \), mientras que la sucesión usual que tiene a \( R(s, 1) \) como segunda componente es la que he definido como \( s^* \) en la demostración, y probando que \( s^* = s|_n \) y pasando a las segundas componentes (siempre restando 1 antes) obtenemos la igualdad buscada. Y hay un camino natural para probar la igualdad \( s^* = s|_n \), que es probar que ambas tienen las mismas proyecciones. Comprobar eso ya es poco más que una aplicación rutinaria de las definiciones (en un razonamiento inductivo).

Más o menos, ése fue el camino que seguí.

Voy a ponerme ahora con la sustitución, a ver si termino de leerlo esta mañana y me subes de nuevo el sueldo :laugh:

En cuanto pueda me pongo con tu segundo mensaje.

28 Julio, 2023, 02:35 pm
Respuesta #246

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Parece que esta vez me he adelantado ;D

Bueeeeno, te triplico el sueldo.

La sustitución debemos entenderla como un funtor triádico definido mediante el teorema de recursión de la respuesta #17, tal que si \( x \) no es una variable, \( t \) no es un término y \( \zeta \) no es una expresión entonces vale \( 0 \), o debemos entenderlo como que para cada variable \( x \) y término \( t \) definimos mediante el teorema de recursión de la respuesta #17 un funtor monádico.

Podríamos hacer las dos cosas, pero tener un funtor triádico es mucho más potente que tener infinitos funtores, así que eso hay que entender. Observa que en toda la definición recurrente \( x, t \) se mantienen fijos, por lo que no hay problema en tomarlos como parámetros fijos del funtor triádico.

Se te ha olvidado definir la sustitución sobre las fórmulas :P

¡Siempre acusando los detalles más nimios e irrelevantes!    ;)

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

¿Con introducir notación rutinaria a que te refieres en este caso?

Tal y como hemos definido las cosas, una \( n \)-tupla \( s \) tiene componentes \( s_0, \ldots, s_{n\dot-1} \), pero los matemáticos prefieren en estos casos referirse a ellas como \( s_1, \ldots, s_n \). Sólo supone adoptar el convenio de llamar \( \bar s_i \equiv s_{i\dot-1} \), de modo que \( s_0, \ldots, s_{n\dot-1} \) es lo mismo que \( \bar s_1, \ldots, \bar s_n \) y luego decir: "a partir de ahora sobreentenderemos las barritas y no las pondremos".

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.

Una cuestión sobre este caso en concreto. Al formalizar la definición, se definiría un funtor \( S_{x_1\cdots x_n}^{t_1\cdots t_n}\theta \) para cada \( n \) metamatemático o sería un único funtor triádico que cubriese todos los casos, teniendo en cuenta que los argumentos fueran sucesiones de \( n \) variables, \( n \) términos, etc.

De nuevo se puede hacer las dos cosas, pero tener un único funtor triádico es más potente, así que lo entendemos así.

29 Julio, 2023, 10:05 am
Respuesta #247

Eparoh

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

Me refería a la desigualdad. La última igualdad sale también de la fórmula azul aplicada a \( \left<m\right>_\infty\frown s|_{n+1} \) y teniendo en cuenta que \( (\left<m\right>_\infty\frown s|_{n+1})|_n = \left<m\right>_\infty\frown s|_n \), pues en ambos casos estamos eliminando el último término de la sucesión.

Hola, pero eso último que pones no es cierto, ¿no? Quiero decir que \( (\left<m\right>_\infty\frown s|_{n+1})|_n = \left<m\right>_\infty\frown s|_{n{\color{red} \dot{-}1}} \), ¿no? Porque la longitud de \( \left<m\right>_\infty\frown s|_{n+1} \) es \( n+2 \), ¿no?

Entonces, no me cuadra aún la última igualdad :-\

El resto de cosas están todas claras (por cierto, impresionante el camino recorrido para obtener la demostración  :aplauso:), aunque me he dado cuenta de esta otra errata ::)

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 \( {\color{red} s}\in S_m(\mbox{Sub}(\zeta)) \) tal que \( \forall i<m\ {\color{red} s}_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \) y \( \zeta = f{\color{red} s}_0\cdots {\color{red} s}_{m\dot- 1} \), entonces definimos

    \( S_x^t\zeta = fS_x^t{\color{red} s}_{\color{red} 0}\cdots S_x^t{\color{red} s}_{\color{red} 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 \)

Un saludo.

29 Julio, 2023, 10:46 am
Respuesta #248

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola.

Me refería a la desigualdad. La última igualdad sale también de la fórmula azul aplicada a \( \left<m\right>_\infty\frown s|_{n+1} \) y teniendo en cuenta que \( (\left<m\right>_\infty\frown s|_{n+1})|_n = \left<m\right>_\infty\frown s|_n \), pues en ambos casos estamos eliminando el último término de la sucesión.

Hola, pero eso último que pones no es cierto, ¿no? Quiero decir que \( (\left<m\right>_\infty\frown s|_{n+1})|_n = \left<m\right>_\infty\frown s|_{n{\color{red} \dot{-}1}} \), ¿no? Porque la longitud de \( \left<m\right>_\infty\frown s|_{n+1} \) es \( n+2 \), ¿no?

Entonces, no me cuadra aún la última igualdad :-\

 :banghead:   Es que hay una errata en el párrafo que citas. En realidad es

\( (\left<m\right>_\infty\frown s|_{n+1})|_{n+1} = \left<m\right>_\infty\frown s|_n \).

Ésta es la igualdad que encaja en la demostración: Creo que así queda más claro:

\( R(\left<m\right>_\infty\frown s|_{n+1},0) ={\color{blue} R((\left<m\right>_\infty\frown s)|_{n+2},0) = \left<R((\left<m\right>\frown s)|_{n+1},0), s_n\right>_2} =\left<R(\left<m\right>\frown s|_n,0), s_n\right>_2  \).

Lo que pasa es que \( (\left<m\right>_\infty\frown s)|_{n+2} = \left<m\right>_\infty\frown s|_{n+1} \), y esto es lo que se restringe a \( n+1 \) (no a \( n \), como había puesto yo) para obtener \( (\left<m\right>\frown s)|_{n+1} =\left<m\right>\frown s|_n  \).

He añadido estos pasos a la demostración, para que quede más clara.

Ahora estoy un poco ocupado, pero en cuanto pueda añado un mensaje al hilo.

29 Julio, 2023, 11:12 am
Respuesta #249

Eparoh

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

Vale, ahora ya lo he entendido. También hay que darse cuenta de que \( s_n=(\left<m\right>_\infty\frown s)_{n+1} \) y así ya queda exactamente en la forma dada por la fórmula azul y ya todo cuadra.

Un saludo.