Autor Tema: La Aritmética Recursiva Primitiva

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

23 Julio, 2023, 04:20 pm
Respuesta #20

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En este mensaje y los siguientes vamos a ver que, entre las muchas cosas que pueden formalizarse en ARP se encuentra la propia construcción de ARP. Para ello sólo necesitamos aprovechar que los ocho signos de \( \mathcal L_{\rm arp} \) pueden ser lo que más nos convenga y elegir concretamente ocho números naturales (los ocho primeros, por decir algo). Todo lo que sigue ha de entenderse como definiciones y teoremas en ARP:

Definición Llamaremos signos de \( \color{blue}\mathcal L_{\rm arp} \) a

\( {\color{blue}0} \equiv 0,\quad {\color{blue} S} \equiv 1, \quad  {\color{blue}p}\equiv 2,\quad {\color{blue} c}\equiv 3,\quad {\color{blue} \kappa}\equiv 4,\quad {\color{blue} \rho} \equiv 5, \quad {\color{blue} x}\equiv 6,\quad {\color{blue} =}\equiv 7.
 \)

El conjunto de signos de \( {\color{blue}\mathcal L_{\rm arp}} \) es, pues, el conjunto

\( \mbox{Sig}({\color{blue}\mathcal L_{\rm arp}}) \equiv \{{\color{blue} 0},\quad {\color{blue} S},\quad{\color{blue} p},\quad{\color{blue} c},\quad {\color{blue} \kappa},\quad{\color{blue}\rho},\quad{\color{blue} x},\quad{\color{blue} =}\}. \)

Notemos que a partir de aquí el color no es un mero adorno, sino que es significativo. Por ejemplo, \( S \) y \( \color{blue}S \) son dos cadenas de signos de \( \mathcal L_{\rm arp} \) distintas entre sí. La primera tiene longitud 1, mientras que la segunda tiene longitud 2, ya que \( {\color{blue}S}\equiv 1 \equiv S0 \).

Diremos que \( \zeta \) es una cadena de signos de \( {\color{blue}\mathcal L_{\rm arp}} \) si cumple

\( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\equiv \forall i<\ell(\zeta)\ \zeta_i\in \mbox{Sig}({\color{blue}\mathcal L_{\rm arp}}).
 \)

Esta definición incluye a la cadena de signos vacía \( 0 \) de longitud \( 0 \).

En el mensaje anterior hemos definido la yuxtaposición de una sucesión de sucesiones: \( \zeta_0\ldots \zeta_n \), y es claro que la yuxtaposición de cadenas de signos de \( \color{blue}\mathcal L_{\rm arp} \) es de nuevo una cadena de signos de \( \color{blue}\mathcal L_{\rm arp} \).

Si \( \zeta\equiv s_0\cdots s_n \) es cualquier cadena metamatemática de signos \( s_i \) de \( \mathcal L_{\rm arp} \), llamaremos \( \color{blue}\zeta \) al único numeral que, según el último teorema de la respuesta #7, cumple

\( \mathop\vdash\limits_{\rm ARP}{\color{blue}\zeta} = {\color{blue}s_0}\cdots {\color{blue}s_n} = \left<{\color{blue}s_0},\ldots, {\color{blue} s_n}\right>. \)

(A partir de aquí escribiré \( \left<\right> \) en lugar de \( \left<\right>_\infty \).)

[Copiado de Eparoh] Es sencillo ver entonces que si \( \zeta \) y \( \psi \) son dos cadenas metamatemáticas de signos de \( \mathcal L_{\rm arp} \) y \( \zeta \psi \) es su yuxtaposición (metamatemática), entonces

\( \mathop\vdash\limits_{\rm ARP} {\color{blue} \zeta \psi} = {\color{blue} \zeta} \frown {\color{blue}\psi}. \)

La prueba se realiza por inducción (metamatemática) sobre la longitud de \( \psi \).

Nota Con esto hemos introducido una ambigüedad en la notación. En el caso de un signo de \( \mathcal L_{\rm arp} \), como por ejemplo \( p \), la notación \( \color{blue}p \) puede hacer referencia a dos numerales distintos. Según la definición inicial de este mensaje es \( {\color{blue}p} \equiv 2 \), pero según la definición que acabamos de dar (viendo a \( p \) como una cadena de signos de longitud \( 1 \)) tenemos que \( \left<{\color{blue}p}\right> = \left<2\right> = 4 \), luego \( {\color{blue}p} \equiv 4 \). En general, según este segundo criterio, tenemos que

\( {\color{blue} 0} \equiv 1,\quad {\color{blue}S} \equiv 2, \quad {\color{blue}p}\equiv 4,\quad {\color{blue}c}\equiv 7, \quad {\color{blue}\kappa}\equiv 11,\quad {\color{blue} \rho} \equiv 16, \quad {\color{blue} x}\equiv 22, \quad {\color{blue}=} \equiv 29.
 \)

En la práctica el contexto siempre dejará claro cuándo consideramos que una expresión como \( \color{blue} s \) hace referencia a un signo de \( {\color{blue}\mathcal L_{\rm arp}} \) o a la cadena de signos de longitud \( 1 \) correspondiente.

Por ejemplo, tenemos que \( p^2_1 \equiv pS0SS0 \), y en ARP se demuestra que

\( \left<{\color{blue} p},{\color{blue} S}, {\color{blue} 0}, {\color{blue} S}, {\color{blue} S}, {\color{blue} 0}\right> = \left<2, 1, 0, 1, 1, 0\right>= 14\,621\,784\,001\,269\,145\,854\,811,
 \)
luego,

\( {\color{blue}p^2_1}\equiv 14\,621\,784\,001\,269\,145\,854\,811 \)

(entendiendo el miembro derecho como un \( 0 \) precedido del número indicado de funtores \( S \)).

Numerales Diremos que \( N \) es un numeral si cumple

\( N\in \mbox{Num}({\color{blue}{\mathcal L_{\rm arp}}})\equiv \ell(N)>0\land \forall i <\ell(N)\dot- 1\, N_i = {\color{blue} S}\land N_{\ell(N)\dot- 1}={\color{blue} 0}.
 \)

Consideramos el funtor definido por

\( N_0 = {\color{blue} 0},\qquad N_{n+1} = {\color{blue}S} N_n. \)

(El miembro derecho hay que entenderlo como la yuxtaposición \( {\color{blue}S}\frown N_n \).)

Una simple inducción prueba que \( N_n\in \mbox{Num}({\color{blue}\mathcal L_{\rm arp}}) \) y, más aún, los numerales de esta forma son los únicos que hay, pues si definimos el indice de un numeral como \( \mbox{ind}(N) = \ell(N)\dot-1 \), tenemos que \( \mbox{ind}(N_n) = n \) y que

\( N\in \mbox{Num}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{ind}(N) = n\rightarrow N = N_n. \)

Es claro que si \( \bar n \) es el numeral (metamatemático) correspondiente al número natural \( n \), entonces en ARP se demuestra que \( {\color{blue}\bar n} = N_{\bar n} \). Por ejemplo: \( {\color{blue}SSSS0} \equiv N_4 \). Esto se prueba por inducción (metamatemática) sobre \( n \).

Notemos que no es lo mismo el numeral (metamatemático) \( 4\equiv SSSS0 \) que el numeral (formalizado) \( N_4 = {\color{blue}SSSS0} \equiv 352\,942\,601 \).

Por otro lado, el funtor \( N \) que hemos definido un poco más arriba es algo más general que la sucesión de numerales \( {\color{blue} 0}, {\color{blue}S0}, {\color{blue}SS0}, \ldots  \), pues esto son únicamente términos sin variables, mientras que el funtor \( N \) nos permite considerar el término \( N_n \), donde \( n \) es una variable de ARP, una variable que al sustituirla por un numeral, como \( \bar 4\equiv SSSS0 \), da lugar a un término (que se demuestra) igual al numeral \( {\color{blue}SSSS0} \).

Proyecciones Definimos el funtor diádico

\( p^n_k = {\color{blue} p} N_k N_n. \)

(Nuevamente, en el miembro derecho sobreentendemos dos \( \frown \), como en la definición del funtor \( N \).)

Llamaremos proyecciones a las cadenas de signos que cumplen

\( \pi\in \mbox{Proy}({\color{blue}\mathcal L_{\rm arp}})\equiv \pi \in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \exists kn<\ell(\pi)(1\leq k\leq n\land \pi =p^n_k).
 \)

Si \( \pi\in \mbox{Proy}({\color{blue}\mathcal L_{\rm arp}}) \), podemos calcular:

\( k(\pi) = (\mu i<\ell(\pi)\ \pi_i = {\color{blue} 0})\dot- 1,\qquad n(\pi) = \ell(\pi)\dot -(k(\pi)+ 3), \)

y es fácil ver que

\( \pi\in \mbox{Proy}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \pi = p^{n(\pi)}_{k(\pi)}. \)

Por ejemplo, si \( \pi \equiv p^3_2 = {\color{blue} pSS0SSS0} \), vemos que \( k(\pi) = 3\dot- 1=2 \) y que \( n(\pi) = 8\dot-(2+3) = 3 \).

Los números \( k(\pi) \) y \( n(\pi) \) se llaman índice y rango de \( \pi \), respectivamente. Por definición tenemos que \( 1\leq k(\pi)\leq n(\pi) \).

Es fácil ver que si \( 1\leq k\leq n \) son números naturales metamatemáticos, entonces

\( \mathop\vdash\limits_{\rm ARP}{\color{blue}p^n_k} = p^{\bar n}_{\bar k}, \)

donde \( \bar k \) y \( \bar n \) son los numerales (metamatemáticos) de ARP correspondientes a \( k \) y \( n \), respectivamente.

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

  • \( \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 \( 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 \( 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, \( \mbox{rang}_n(\zeta)=0 \). Llamaremos funtores de \( {\color{blue}\mathcal L_{\rm arp}} \) a las cadenas de signos que cumplen

\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\equiv f\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)>0. \)

Así, cada funtor \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) tiene asociado un rango \( \mbox{rang}(f)>0 \).

A partir de las definiciones precedentes (y suprimiendo precisiones técnicas), es fácil ver que todo funtor \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) se encuentra en uno de los casos siguientes:

  • \( f = {\color{blue} S} \) (en cuyo caso \( f \) es un funtor monádico),

  • \( f = {\color{blue} c} \) (en cuyo caso \( f \) es un funtor monádico),

  • \( f = p^n_k \), para ciertos índices \( 1\leq k\leq n \) (y entonces \( f \) es un funtor \( n \)-ádico),

  • \( f = {\color{blue}\kappa}(h, g_0,\ldots, g_{m\dot-1}) \), donde \( h \) es un funtor \( m \)-ádico y los \( g_i \) forman una sucesión de funtores \( n \)-ádicos (y entonces \( f \) es un funtor \( n \)-ádico),

  • \( f = {\color{blue}\rho}(g, h) \), donde \( g \) es un funtor \( n \)-ádico y \( h \) es un funtor \( n+2 \)-ádico (y entonces \( f \) es un funtor \( n+1 \)-ádico).

Es evidente que un mismo funtor no puede estar a la vez en en dos de estos casos, pues el signo inicial \( f_0 \) es distinto en cada uno de ellos, pero, más aún, en los casos \( 4 \) y \( 5 \) los funtores que componen \( f \) también están unívocamente determinados.

Demostración
En primer lugar definimos el funtor

\( \mbox{R}(\zeta,n) = \mu \zeta'\in \mbox{Sub}(\zeta)\exists \zeta''\in \mbox{Sub}(\zeta)(\ell(\zeta'')=n\land \zeta = \zeta''\zeta').
 \)

Es fácil ver que si \( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}}) \) y \( \ell(\zeta)\geq n \), entonces \( R(\zeta,n) \) es la cadena que resulta de quitarle a \( \zeta \) sus \( n \) primeros signos.

A su vez definimos

\( \mbox{PN}(\zeta)=\mu \zeta'\in \mbox{Sub}(\zeta)\exists k\leq \ell(\zeta)(\zeta' = N_k\land \zeta = N_k\ R(\zeta,k+1)).
 \)

Así, \( \mbox{PN}(\zeta) \) es el numeral con el que empieza \( \zeta \) si es que realmente empieza por un numeral, y es \( 0 \) (que es también la cadena vacía) si no es el caso. Es fácil probar entonces que

\( \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \mbox{PN}(N_k\zeta)=N_k. \)

Esto implica que el primer numeral de una cadena de signos (si existe) está unívocamente determinado, es decir, que una misma cadena de signos no puede descomponerse de dos formas distintas de modo que el primer fragmento sea un numeral.

Ahora definimos un funtor monádico \( \mbox{PF} \) con la propiedad de que, si \( f \) es un funtor, entonces

\( \mbox{PF}(f\zeta)=f, \)

es decir, que \( \mbox{PF} \) proporciona el primer funtor de su argumento, mientras que si \( \zeta \) es una cadena que no empieza por un funtor, entonces \( \mbox{PF}(\zeta)=0 \) es la cadena vacía.

Para ello definimos \( \mbox{PF}(0) = 0 \) y, para cadenas de longitud no nula, distinguimos varios casos:

  • Si \( \zeta_0 = {\color{blue}S} \), entonces \( \mbox{PF}(\zeta) = {\color{blue} S} \),

  • Si \( \zeta_0 = {\color{blue}c} \), entonces \( \mbox{PF}(\zeta) = {\color{blue}c} \),

  • Si \( \zeta_0 = {\color{blue}p} \), calculamos \( \bar k\equiv \mbox{PN}(R(\zeta,1)) \). Si no es la cadena vacía,  calculamos \( \bar n\equiv\mbox{PN}(R(\zeta, 1+\ell(\bar k))) \). Si tampoco es la cadena vacía y además \( 2\leq \ell(\bar k)\leq \ell(\bar n) \), entonces \( \mbox{PF}(\zeta) = \zeta|_{\ell(\bar k)+\ell(\bar n)+1}. \)

  • Si \( \zeta_0 = {\color{blue}\kappa} \), calculamos \( h\equiv \mbox{PF}(R(\zeta, 1)) \). Si no es la cadena vacía (y, por consiguiente, es un funtor), llamamos \( m\equiv \mbox{rang}(h) \) y consideramos el funtor definido por \( F(\zeta, 0) = \left<{\color{blue}\kappa} h, R(\zeta, 1+\ell(h))\right> \) y

    \( F(\zeta, n+1) = \cases{\left<\smash{F(\zeta, n)_0\frown \mbox{PF}(F(\zeta,n)_1),R(F(\zeta,n)_1,\ell(\mbox{PF}(F(\zeta,n)_1)))}\right>, &si $\mbox{PF}(F(\zeta,n)_1)\neq 0$,\cr
    \left<0, 0\right>&si $\mbox{PF}(F(\zeta,n)_1)=0$.}
     \)

    Así, si \( F(\zeta, m) = \left<0,0\right> \), definimos \( \mbox{PF}(\zeta) = 0 \) y en caso contrario hacemos \( \mbox{PF}(\zeta)=F(\zeta, m)_0 \).

    Lo que hace \( F \) es quitarle a \( \zeta \) la cadena inicial \( {\color{blue}\kappa} h \) y luego ir quitándole funtores mientras sea posible. Lo que hemos hecho es decir que si se le pueden quitar \( m \) funtores, entonces \( \mbox{PF}(\zeta) \) es la yuxtaposición de \( \color{blue}\kappa \) y los \( m+1 \) funtores que hemos quitado.

  • Si \( \zeta_0 = {\color{blue}\rho} \), calculamos \( g = \mbox{PF}(R(\zeta, 1)) \). Si es un funtor, calculamos \( h =  \mbox{PF}(R(\zeta, 1+\ell(h))) \). Si es un funtor y \( \mbox{rang}(h)=\mbox{rang}(g)+2 \), definimos \( \mbox{PF}(\zeta)={\color{blue}\rho} g h \)
En cualquier otro caso,  \( \mbox{PF}(\zeta)=0 \).

Ahora una inducción rutinaria muestra que cumple lo requerido, es decir, que si \( f \) es un funtor y \( \zeta \) es una cadena de signos arbitraria, entonces \( \mbox{PF}(f\zeta) = f \), lo que prueba que el primer funtor de una cadena de signos está unívocamente determinado.

Usando esto es inmediato comprobar que la descomposición de un funtor como composición o recursión es única.
[cerrar]

Observemos también que una simple inducción sobre la longitud de \( f \) prueba que si \( f \) es un funtor (metamatemático) de rango \( n \), entonces

\( \mathop\vdash\limits_{\rm ARP}{\color{blue} f}\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{ran}({\color{blue} f}) = \bar n, \)

donde \( \bar n \) es el numeral (metamatemático) asociado a \( n \).

Enumeración de funtores Es interesante observar que podemos enumerar los funtores de \( \mathcal L_{\rm arp} \). Para ello observamos que si \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( {\color{blue}\kappa}({\color{blue}S} ,f) \) es otro funtor del mismo rango, pero mayor como número natural. Esto nos permite definir los funtores

\( \mbox{SF}(f)= \mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land f<g), \)

\( \mbox{SFR}(f)=\mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \land \mbox{rang}(g)=\mbox{rang}(f)\land f<g).
 \)

que calculan el menor funtor mayor que uno dado, y el menor funtor del mismo rango mayor que uno dado. A su vez:

\( f_0 = {\color{blue}S},\qquad f_{k+1} = \mbox{SF}(f_k), \)

\( f^n_0 =\mu g\leq p^n_1(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g)=n),\qquad f^n_{k+1} = \mbox{SFR}(f^n_k),
 \)

de modo que

\( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}),\qquad  f_k^n\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f^n_k)=n,
 \)

\( k<k'\rightarrow f_k<f_{k'}\land f^n_k<f^n_{k'}, \)
(de donde se sigue por inducción que \( k\leq f_k \), \( k\leq f^n_k \)), y a su vez

\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \exists! k\leq f\ f = f_k, \)

\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)=n\rightarrow \exists! k\leq f\ f = f^n_k. \)

Veamos, como ejemplo, la prueba del primero de estos dos hechos:

Demostración
Dado un funtor \( f \), tomando \( m\equiv f \), se cumple que \( f\leq f_m<f_{m+1} \), luego podemos considerar \( r\equiv \mu m\leq f+1(f< f_m) \). Claramente, no puede ser \( r = 0 \), luego si hacemos \( k = r\dot- 1 \), tenemos que \( f_k\leq f<f_{k+1} = \mbox{SF}(f_k) \). La definición de SF implica entonces que \( f = f_k \).
[cerrar]

Variables Consideramos el funtor definido por

\( x_n = {\color{blue} x} N_n. \)

Llamaremos variables a las cadenas de signos que cumplen

\( \xi\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\equiv \xi \in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \exists n\leq \ell(\xi)\,\xi = x_n.
 \)

El índice de una variable es \( \mbox{ind}(\xi) = \ell(\xi)\dot-2 \). Es fácil probar que

\( \xi\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{ind}(\xi) = n\rightarrow \xi = x_n. \)

Si \( x \) es la variable (metamatemática) de índice \( n \), es fácil ver que

\( \mathop\vdash\limits_{\rm ARP}{\color{blue} x} = x_{\bar n}, \)

donde \( \bar n \) es el numeral (metamatemático) correspondiente a \( n \).

Términos Para definir los términos de \( {\color{blue}\mathcal L_{\rm arp}} \) definimos un funtor \( F \) que tome el valor \( 1 \) sobre los términos y \( 0 \) en otro caso. Escribiendo

\( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\equiv F(\zeta)=1, \)
la definición es:

  • Si \( \zeta\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \).

  • Si \( \zeta = \color{blue}0 \), entonces \( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \).

  • 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))(\forall i<m\ {t_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})}\land \zeta = ft_0\cdots t_{m\dot-1}). \)
En cualquier otro caso, \( \zeta\notin \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \). Es claro entonces que

\( \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\leftrightarrow \zeta = {\color{blue} 0}\lor \zeta\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\lor \exists f\in \mbox{Sub}(\zeta)\exists m\leq \ell(f)\exists t\in S_m( \mbox{Sub}(\zeta))(f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land m = \mbox{rang}(f)\land \)

\( \forall i< m\ t_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta = ft_0\cdots t_{m\dot-1}). \)

Sin tecnicismos, tenemos que \( t \) es un término si y sólo si \( t= \color{blue} 0 \) o bien \( t \) es una variable, o bien existe un funtor \( m \)-ádico \( f \) y una sucesión de \( m \) términos tal que \( t = ft_0\cdots t_{m\dot-1} \).

En la práctica, en este último caso, escribiremos \( t = f(t_0,\ldots, t_{m\dot- 1}) \). Como en el caso de los funtores, es pura rutina comprobar que si \( t \) es de esta forma, entonces \( m \) y los términos \( t_i \) están unívocamente determinados.

Demostración
Definimos un funtor \( \mbox{PT} \) tal que si \( t \) es un término, entonces \( \mbox{PT}(t\zeta) = t \), es decir, que \( \mbox{PT} \) asigna a cada cadena el término por el que empieza, si es que existe, o \( 0 \) en caso contrario. Para ello definimos $\mbox{PT}(0) = 0$ y, para cadenas de longitud no nula, distinguimos varios casos:

  • Si \( \zeta_0 = \color{blue} 0 \), entonces \( \mbox{PT}(\zeta) = \color{blue} 0 \).

  • Si \( \zeta_0 =  \color{blue}x \), llamamos \( N\equiv \mbox{PT}(R(\zeta, 1)) \). Si \( N\in \mbox{Num}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( \mbox{PT}(\zeta)={\color{blue} x} N \).

  • Si \( f \equiv \mbox{PF}(\zeta) \) es un funtor, llamamos \( m\equiv \mbox{rang}(f) \) y consideramos el funtor definido por \( F(\zeta, 0) = \left<f,R(\zeta, \ell(f))\right> \) y

    \( F(\zeta, n+1) = \cases{\left<\smash{F(\zeta, n)_0\frown \mbox{PT}(F(\zeta,n)_1),R(F(\zeta,n)_1,\ell(\mbox{PT}(F(\zeta,n)_1)))}\right>&si $\mbox{PT}(F(\zeta,n)_1)\neq 0$,\cr \left<0, 0\right>& si $\mbox{PT}(F(\zeta,n)_1)=0$.}
     \)

    Finalmente, si \( F(\zeta, m) \neq \left<0,0\right> \), definimos \( \mbox{PT}(\zeta)=F(\zeta, m)_0 \).
En cualquier otro caso, \( \mbox{PT}(\zeta) = 0 \).

Es fácil ver que el funtor PT cumple lo requerido:

\( t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \mbox{PT}(t\zeta) = f, \)
es decir, que PT extrae el primer término de cualquier cadena de signos, y con eso es fácil probar la unicidad de la expresión de un término construido a partir de un funtor.
[cerrar]

Por último observemos que una simple inducción sobre la longitud de \( t \), prueba que si \( t \) es un término (metamatemático), entonces

\( \mathop\vdash\limits_{\rm ARP}{\color{blue} t}\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}). \)

Fórmulas Definimos las fórmulas de \( {\color{blue}\mathcal L_{\rm arp}} \) como las cadenas de signos que cumplen:

\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\equiv \alpha\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\land \exists t_1t_2\in \mbox{Sub}(\alpha)
 \)

\( (t_1, t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \alpha =  {\color{blue}=}\, t_1t_2). \)

En la práctica escribiremos \( t_1{\color{blue}=} \ t_2 \) en lugar de \( {\color{blue} =}\ t_1t_2 \). Podemos definir los funtores

\( T_1(\alpha) = \mbox{PT}(R(\alpha,1)),\qquad T_2(\alpha) =  R(\alpha, 1+\ell(T_1(\alpha))), \)

de modo que
\( t_1, t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow T_1(t_1{\color{blue}=} \, t_2) = t_1\land  T_2(t_1{\color{blue}=} \, t_2) = t_2. \)

\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow T_1(\alpha),T_2(\alpha)\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \alpha = T_1(\alpha){\color{blue} =}\,T_2(\alpha).
 \)

Esto significa que los dos términos que componen una fórmula están unívocamente determinados.

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

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

Diremos que \( \theta \) es una expresión de \( \color{blue}\mathcal L_{\rm arp} \) si cumple

\( \theta\in \mbox{Exp}({\color{blue}\mathcal L_{\rm arp}})\equiv \theta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\lor \theta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}).
 \)

Sustitución Definimos ahora la sustitución de una variable por un término en una expresión, distinguiendo casos:

  • Si \( \zeta\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}}) \),

    \( S_x^t\zeta \equiv \cases{t& si $\zeta = x$,\cr \zeta&si $\zeta\neq x$.} \)

  • Si \( \zeta = {\color{blue}0} \), entonces \( S_x^t {\color{blue}0} = \color{blue} 0 \).

  • Si\(  f = \mbox{PF}(\zeta) \) es un funtor y \( \mbox{rang}(f)=m \) y existe \( s\in S_m(\mbox{Sub}(\zeta)) \) tal que \( \forall i<m\ s_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \) y \( \zeta = ft_0\cdots t_{m\dot- 1} \), entonces definimos

    \( S_x^t\zeta = fS_x^ts_0\cdots S_x^ts_{m\dot-1}. \)

  • Si \( \zeta_0= {\color{blue} =} \) y existen \( t_1, t_2\in \mbox{Sub}(\zeta) \) tales que \( \zeta = {\color{blue} =} t_1t_2 \), definimos \( S_x^t\zeta={\color{blue} =} S_x^tt_1S_x^tt_2 \)
En cualquier otro caso, definimos \( S_x^t\zeta = 0 \). Es claro entonces que (suponiendo en cada caso \( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})) \):

  • \( S_x^t{\color{blue}0} = {\color{blue}0} \).
  • \( y\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^ty=\cases{t&si $y=x$,\cr y&si $y\neq x$.} \)

  • \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)=n\land \ell(s)= n\land \forall i<n\ s_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^tfs_0\cdots s_{n\dot-1} = fS_x^ts_0\cdots S_x^ts_{n\dot-1}. \)

  • \( t_1, t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^t(t_1{\color{blue} =} \, t_2)=S_x^tt_1{\color{blue} =}\ S_x^tt_2 \).

Es fácil ver que

\( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^t\zeta\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}),
 \)

\( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \zeta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^t\zeta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}),
 \)

así como que \( si x, t, \theta \) son, respectivamente, una variable, un término y una expresión metamatemáticas, entonces

\( \mathop\vdash\limits_{\rm ARP} S_{\color{blue} x}^{\color{blue} t}{\color{blue} \theta} = {\color{blue} S_x^t\theta}. \)

Nota Hasta aquí hemos detallado las definiciones y las demostraciones en ARP para que el lector se haga una idea de lo que supone formalizar en ARP, pero tenemos que insistir en que no es nada práctico exponer las definiciones y demostraciones con este nivel de detalle, ni en ARP ni en cualquier otra teoría axiomática formal.

La forma habitual de trabajar de los matemáticos en cualquier teoría formal no es detallar todas las definiciones y argumentos hasta el punto de que sea evidente cómo se formalizan en una teoría axiomática en particular, sino sólo hasta el punto de que se entiendan las ideas relevantes, dando por hecho que formalizar los pasos técnicos que no ofrecen ninguna dificultad conceptual es una pura rutina que no aporta nada salvo el hecho de confirmar que lo que se está diciendo es formalizable en una teoría dada, pero normalmente uno puede convencerse de que esto es así sin necesidad de especificar todos los detalles ad nauseam.

Por ejemplo, comparemos las condiciones que definen la sustitución de una variable por un término tal y como las enunciamos en su momento al introducir ARP informalmente y cómo las hemos enunciado aquí. Si nos fijamos, concretamente, en la tercera condición. En su momento la enunciamos así:

\( S_x^tf(t_1,\ldots, t_n)\equiv f(S_x^tt_1,\ldots, S_x^tt_n) \),

y ahora:

\( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f)=n\land \ell(s)= n\land \forall i<n\ s_i\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow S_x^tfs_0\cdots s_{n\dot-1} = fS_x^ts_0\cdots S_x^ts_{n\dot-1}. \)

Vemos que la diferencia consiste en que en la versión informal sobreentendemos que \( f \) es un funtor \( n \)-ádico, que \( t \) es un término, etc., mientras que en la versión formalizada hemos explicitado estas hipótesis para asegurarnos de que la fórmula que presentamos es realmente un teorema de ARP, y no un mero fragmento de teorema.

En la práctica, no hay ningún inconveniente (al contrario, tiene muchas ventajas) en formular los teoremas de ARP en un lenguaje más laxo, por ejemplo diciendo (así, con palabras) que si \( x \) es una variable, \( t \) es un término, \( f \) es un funtor \( n \)-ádico y \( t_1,\ldots, t_n \) son términos, entonces

\( S_x^tf(t_1,\ldots, t_n)\equiv f(S_x^tt_1,\ldots, S_x^tt_n), \)

sin necesidad de escribir una fórmula técnica en forma de implicación que contenga todas las hipótesis, y eso es lo que haremos de ahora en adelante. (Notemos que hemos aprovechado para introducir la costumbre habitual de numerar las sucesiones de \( 1 \) a \( n \) en lugar de empezar en \( 0 \) y acabar en \( n\dot- 1 \), que también se puede formalizar a cambio de introducir algo más de notación rutinaria.)

En cuanto a los argumentos, a la hora de juzgar si un determinado concepto o un determinado argumento son formalizables en ARP, el mejor método no es ponerse a escribir una formalización detallada, sino reflexionar sobre si la definición o la demostración pueden realizarse acotando siempre a priori los cuantificadores que empleemos.

Por ejemplo, para completar la exposición sobre la sustitución nos faltaría definir la sustitución múltiple:

\( S_{x_1\cdots x_n}^{t_1\cdots t_n}\theta = S_{y_1}^{t_1}\cdots S_{y_n}^{t_n}S_{x_1}^{y_1}\cdots S_{x_n}^{y_n}\theta,
 \)

donde \( y_1,\ldots, y_n \) son variables cualesquiera que no estén en \( t_1,\ldots, t_n \) ni en \( \theta \). Formalizar esta definición requiere definir funtores que calculen las variables contenidas en una sucesión de expresiones, y que calculen una biyección entre esas variables y otras nuevas, y otros que apliquen sustituciones de forma recurrente, etc., pero el lector que haya analizado las pruebas que hemos dado en esta sección debería convencerse de que no hay nada que impida detallar toda esa construcción de modo que sea obviamente formalizable en ARP, y por eso mismo sería una pérdida de tiempo ponerse a escribir todos esos detalles en un papel.

Con esto hemos formalizado en ARP el lenguaje \( \mathcal L_{\rm arp} \). Falta formalizar la lógica de ARP.

29 Julio, 2023, 05:04 pm
Respuesta #21

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Nos falta muy poco para acabar de formalizar ARP en ARP, pero hacemos aquí un pequeño paréntesis para ver algo interesante que podemos probar con lo visto hasta ahora.

Todo este mensaje debería ir en rojo, pero, precisamente porque no hay que distinguir párrafos rojos de párrafos negros, lo dejo en negro.

Tratemos ahora de formalizar en ARP la definición de la función denotada por un funtor. Un posible enunciado sería el siguiente:

Teorema Existe un funtor diádico \( \phi \) tal que las afirmaciones siguientes son teoremas de ARP:

  • \( \phi({\color{blue}S}, \left<n\right>) = s_0+1 \).

  • \( \phi({\color{blue}c}, s)=0 \).

  • \( 1\leq k\leq n\rightarrow \phi(p^n_k, s) = s_{k\dot- 1} \).

  • \( h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(h)=m\land \ell(g)=m\land \forall i<m(g_i\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g_i)=n)\land \ell(s)=n\rightarrow \phi({\color{blue}\kappa}(h, g_1,\ldots, g_n), s)=\phi(h,\prod\limits_{i<m}\left<\phi(g_i,s)\right>) \),
    donde el producto indica la concatenación de sucesiones.

  • \( g, h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g) = n\land \mbox{rang}(h)=n+2\land \ell(s)=n\rightarrow \phi({\color{blue}\rho}(g, h), s\frown \left<0\right>)=\phi(g, s)\land  \)

    \( \phi({\color{blue}\rho}(g, h),s\frown \left<k+1\right>)=\phi(h, s\frown \left<k\right>\frown \left<\phi({\color{blue}\rho}(g, h),s\frown\left<k\right>)\right>) \)

Relajando el formalismo por caridad cristiana, este "teorema" afirma que el funtor \( \phi \) cumple (bajo las hipótesis obvias en cada caso):

  • \( \phi({\color{blue}S},\left<n\right>) = n+1 \).

  • \( \phi({\color{blue}c}, \left<n\right>) = 0 \).

  • \( \phi(p^n_k, \left<m_1,\ldots, m_n\right>) = m_k \).

  • \( \phi({\color{blue}\kappa}(h, g_1,\ldots, g_m), \left<s_1,\ldots, s_n\right>) =\phi(h,\left<\phi(g_1,\left<s_1,\ldots, s_n\right>),\ldots,\phi(g_m,\left<s_1,\ldots, s_n\right>) \right>) \).

  • \( \phi({\color{blue}\rho}(g, h),\left<s_1,\ldots, s_n, 0\right>) = \phi(g, \left<s_1,\ldots, s_n\right>)\land
    \phi({\color{blue}\rho}(g, h),\left<s_1,\ldots, s_n,k+1\right>) = \phi(h,\left<s_1,\ldots, s_n,k, \phi({\color{blue}\rho}(g, h),\left<s_1,\ldots, s_n,k\right>)\right>) \).

Admitiendo esto, una simple inducción sobre la longitud de \( f \) prueba que si \( f \) es un funtor \( n \)-ádico, \( k_1,\ldots, k_n \) son números naturales y \( \bar k_i \) es el numeral correspondiente a \( k_i \), entonces

\( \mathop\vdash\limits_{\rm ARP}\phi({\color{blue}f},\left<\bar k_1,\ldots, \bar k_n\right>)=\overline{F(f)(k_1,\ldots, k_n)}, \)               (*)

donde \( F(f) \) es la función denotada por el funtor \( f \).

Sin embargo el "teorema" anterior es falso. Vamos a demostrar que no existe un funtor \( \phi \) que cumpla (*). El lector que crea que debería poder definirse un funtor \( \phi \) que cumpla las condiciones indicadas debería tratar de dar una definición detallada formalizable en ARP, y si la encuentra, entonces es que no ha acabado de entender qué hace falta para que una construcción sea formalizable en ARP.

Por otro lado, es fácil programar un ordenador para que, si le damos como entrada un funtor \( n \)-ádico \( f \) de ARP y una \( n \)-tupla \( \left<k_1,\ldots, k_n\right> \), nos dé como respuesta \( F(f)(k_1,\ldots, k_n) \). En otras palabras, la función diádica \( H(f, s) \) que, cuando el número \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( \mathcal L_{\rm arp} \) y \( s \) es una sucesión de longitud \( n \), calcula

\( H(f, s) = F(f)(s_0,\ldots, s_{n-1}) \)

(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva (si lo fuera, un funtor \( \phi \) que la denotara cumpliría (*)).

Supongamos que existiera el funtor \( \phi \). Entonces podríamos definir un funtor monádico mediante

\( f(k) = \phi(f^1_k,\left<k\right>)+1. \)

En otras palabras, para calcular \( f(k) \) calculamos el \( k \)-ésimo funtor monádico, lo evaluamos en \( k \) y le sumamos \( 1 \) al resultado. Tenemos entonces que

\( {\color{blue}f}\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}({\color{blue} f})=1. \)

Puesto que \( \mu u\leq {\color{blue} f}{\color{blue} f} = f^1_u \) es un término sin variables, podemos considerar el número \( k \) que denota, de modo que, según el teorema final de la respuesta #7, se cumple que

\( \mathop\vdash\limits_{\rm ARP}\bar k = \mu u\leq {\color{blue} f} {\color{blue} f} = f^1_u, \)

donde \( \bar k \) es el numeral que denota al número \( k \). Esto implica que

\( \mathop\vdash\limits_{\rm ARP}{\color{blue} f} = f^1_{\bar k}. \)

Por el mismo teorema aplicado al término \( f(\bar k) \), tenemos que

\( \mathop\vdash\limits_{\rm ARP}f(\bar k) = \overline{F(f)(k)}. \)

Combinando todo esto concluimos que en ARP se podría demostrar que

\( f(\bar k) = \phi(f^1_{\bar k},\left<\bar k\right>)+1 = \phi({\color{blue} f},\left<\bar k\right>)+1 = \overline{F(f)(k)}+1=f(\bar k)+1,
 \)

y esto implica a su vez que \( 0 = 1 \), lo cual no puede probarse en ARP, luego no existe el funtor \( \phi \).

Nota En el argumento anterior subyace el hecho siguiente: si enumeramos todas las funciones monádicas recursivas primitivas, \( f_0^1, f_1^1, f_2^1, \ldots \) la función dada por \( f(k) = f^1_k(k)+1 \) puede calcularla un ordenador, pero no es recursiva primitiva, pues entonces sería una de las \( f^1_k \), y entonces \( f^1_j(j) = f(j) = f_j^1(j)+1 \), lo cual es imposible.

En particular, no es posible formalizar en ARP el concepto de "el número natural denotado por un término respecto de una valoración", es decir, no existe ningún funtor diádico tal que si \( t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}}) \) y \( v \) es una valoración (definida, por finitud, sobre las variables que aparecen en \( t \)), entonces \( \psi(t, v) \) pueda interpretarse como el número denotado por \( t \) cuando sus variables se interpretan según \( v \).

Más precisamente, no puede suceder que \( \psi \) cumpla, en particular, que, si \( t \) es un término metamatemático sin variables, entonces

\( \mathop\vdash\limits_{\rm ARP}\psi({\color{blue} t}, 0) = \overline{N(t)}, \)

donde \( N(t) \) es el número natural denotado por \( t \). En tal caso, el funtor

\( f(k) = \psi(f^1_k(N_k),0)+1, \)

donde ahora \( N \) es el funtor que a cada número natural le asigna su numeral correspondiente en \( {\color{blue}\mathcal L_{\rm arp}} \), nos llevaría a la misma contradicción que antes: si \( \mathop\vdash\limits_{\rm ARP}({\color{blue} f} = f^1_{\bar k}) \), entonces

\( f(\bar k) = \psi(f^1_{\bar k}(N_{\bar k}), 0)+1 = \psi({\color{blue} f}({\color{blue} k}), 0)+1 = \psi({\color{blue}f(\bar k)},0)+1 \)

\( = \overline{N(f(\bar k))}+1 = \overline{F(f)(k)}+1=f(\bar k)+1. \)

A su vez, esto implica que no es posible definir un funtor diádico \( \vDash \alpha[v] \) tal que si \( \alpha \)  es una fórmula de ARP y \( v \) es una valoración definida sobre las variables que aparecen en \( \alpha \), entonces \( \vDash {\color{blue}\alpha}[{\color{blue}v}] \) tome el valor \( 1 \) o \( 0 \) según si \( \alpha \) es satisfecha o no respecto de la valoración \( v \). Al menos, no es posible definirlo formalizando tal cual la definición de satisfacción que hemos dado y, aunque fuera posible formalizar la satisfacción, ni aun así se podría definir un funtor \( \vDash \alpha \) que distinga si una fórmula es verdadera o falsa, pues tampoco podríamos formalizar en ARP el "para toda valoración" que requiere la definición.

En general, podemos decir que ARP es capaz de formalizar su propia sintaxis, pero no puede formalizar su propia semántica.

02 Agosto, 2023, 11:18 pm
Respuesta #22

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En este mensaje completamos la formalización de ARP.

Los axiomas de ARP

Los axiomas de ARP son las definiciones de los funtores (distintos de \( S \)). El lector debería examinar la definición de estos axiomas y convencerse de que no hay ningún inconveniente que impida formalizar esa definición y convertirla en una fórmula \( \alpha\in \mbox{Ax} \)(ARP) de ARP. Los detalles son muy laboriosos, pero vamos a esbozarlos.

Recordemos que hemos definido \( x_k \) como la variable de índice \( k \) de \( {\color{blue}\mathcal L_{\rm arp}} \). Podemos definir la definición del funtor \( p^n_k \) como:

\( A_p(k, n) = p^n_k(x_0,\ldots, x_{n\dot- 1})\ {\color{blue} =}\ x_{k\dot- 1}. \)

Para dar más detalles sobre el término concreto que estamos expresando con el miembro izquierdo tendríamos que definir el funtor

\( \xi_n = \prod\limits_{i<n}\left<x_i\right> \)

que a cada \( n \) le asigna la sucesión de las \( n \) primeras variables de \( {\color{blue}\mathcal L_{\rm arp}} \) (más laxamente: \( \xi_n = \left<x_0, \ldots, x_{n\dot- 1}\right> \)), y definir

\( A_p(k, n) = {\color{blue}=} \ {\color{blue} p}\, N_k\,  N_n\,\xi_n\, x_{k\dot- 1}, \)

pero no ganamos nada encriptando así la definición. La definición de los axiomas de ARP empieza así:

\( \alpha \in \mbox{Ax} \)(ARP) \( \equiv \alpha = {\color{blue }c(x_0)=0}\lor \exists kn\leq \ell(\alpha)(1\leq k\leq n\land \alpha = A_p(k, n))\lor \cdots
 \)

donde falta completar la disyunción con otra fórmula correspondiente a los funtores definidos por composición y otras dos correspondientes a los funtores definidos por recursión.

Veamos cómo sería la fórmula correspondiente a las composiciones. La idea básica es que

\( A_\kappa(h, g) = \kappa(h, g_1,\ldots, g_m)(x_1,\ldots x_n)\ {\color{blue} =} \ h(g_1(x_1,\ldots, x_n), \ldots, g_m(x_1,\ldots, x_n)).
 \)

Más técnicamente sería:

\( A_\kappa(h, g) = {\color{blue} =}\ {\color{blue} \kappa}\, h\,g\,\xi_n\,h\prod\limits_{i<\ell(g)}g_i\xi_n. \)

y para añadir esto en la fórmula \( \alpha \in \mbox{Ax} \)(ARP) hay que incluir cuantificadores

\( \exists h\in\mbox{Sub}(\alpha)\exists mn\leq \ell(\alpha)\exists g\in S_m(\mbox{Sub}(\alpha))
 \)
y las hipótesis

\( h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(h) = m\land \forall i<m(g_i\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g_i) = n),
 \)
pero comprimiendo toda esta información en una fórmula sólo volvemos ilegible una definición tan clara como la que dimos en su día.

Dejamos a cargo del lector formalizar (si lo cree imprescindible) la definición de los axiomas de los funtores definidos por recursión. El caso es que así podemos completar la definición de una fórmula \( \alpha \in \mbox{Ax} \)(ARP) que se corresponde con la definición informal, y en particular permite probar que si \( \alpha \) es un axioma (metamatemático) de ARP, entonces

\( \mathop\vdash\limits_{\rm ARP}{\color{blue}\alpha} \in \mbox{Ax} \)(ARP).

Deducciones Seguidamente, el lector debería convencerse de que no hay nada que impida formalizar en ARP la definición informal de deducción. El resultado tiene que ser una fórmula

\( \Pi\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\alpha\equiv  d_{\ell(d)\dot- 1}=\alpha\land  \forall i<\ell(d)\, (d_i\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\land(d_i\in \Pi\lor d_i\in \mbox{Ax} \)(ARP)\( \lor \cdots)),
 \)

donde los puntos suspensivos representan cuatro fórmulas más en la disyunción que expresan que \( d_i \) se sigue de fórmulas precedentes por una de las cuatro reglas de inferencia de ARP, pero no ganamos nada condensando dichas reglas en fórmulas de ARP. Basta observar que para formalizarlas no tenemos que hacer referencia a nada que no podamos acotar en términos de la sucesión \( d \) o de sus términos.

Omitiremos el conjunto de premisas \( \Pi \) cuando sea vacío, es decir, que

\( \mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\alpha\ \equiv\ \emptyset\!\!\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\alpha \)

y entonces diremos que \( d \) es una demostración de \( \alpha \) en ARP.

En este punto nos encontramos con un detalle que hay que tener presente, y es que no podemos definir una fórmula \( \Pi\mathop\vdash\limits_{\rm \color{blue}ARP}\alpha \), omitiendo la deducción \( d \) mediante un cuantificador existencial, ya que no tenemos forma de acotarlo.

Más llanamente: no podemos definir en ARP una fórmula que diga que una fórmula es un teorema de ARP, lo cual es razonable, porque "ser un teorema" no es totalmente finitista. No hay una forma de comprobar en un número finito de pasos si una fórmula dada es un teorema o no. Mejor dicho, la única forma de hacerlo consiste en encontrar una demostración. Por eso en ARP no podemos decir "\( \alpha \) es un teorema", sino que tenemos que decir necesariamente "\( d \) es una demostración de \( \alpha \)".

Por ejemplo, si queremos enunciar en ARP las reglas de inferencia de la doble negación tenemos que formular algo del estilo de

\( \{\lnot\lnot\alpha\}\mathop\vdash\limits_{\rm \color{blue}ARP}^{f(\alpha)}\alpha \)

donde \( f \) es un funtor que, a cada fórmula \( \alpha \) le hace corresponder una deducción de \( \alpha \) a partir de \( \lnot\lnot\alpha \) (donde \( \lnot \) es aquí un funtor monádico). Como sabemos deducir \( \alpha \) a partir de \( \lnot\lnot\alpha \), sabemos cómo definir un funtor que nos dé una deducción.

Sin más que esta obligación de explicitar siempre las demostraciones de los teoremas a los que hagamos referencia, el lector debería convencerse de que nada —salvo la brevedad de la vida— le impide demostrar todos los resultados que hemos expuesto en este hilo sobre ARP que no involucren conceptos semánticos. Por ejemplo, la formalización del teorema de deducción consiste en definir funtores \( D \), \( P \), \( D' \) de modo que

\( \Pi\cup\{\alpha\}\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\beta\rightarrow \left(\Pi\cup P(d, \alpha)\mathop{\vdash}\limits_{\rm \color{blue}ARP}^{D(d, \alpha)}\alpha{\color{blue}\rightarrow} \beta\right)\land \forall \gamma\in P(d,\alpha)\!\!\! \mathop{\vdash}\limits_{\rm \color{blue}ARP}^{D'(d, \alpha, \gamma)}\!\!\!\!\gamma \)

(con todas las hipótesis y conclusiones adicionales del teorema, es decir, hay que suponer que la deducción \( d \) no usa las reglas \( S_1 \) o \( I_0 \) respecto a variables que estén en \( \alpha \) y podemos concluir que la deducción \( D(d, \alpha) \) sólo usa estas reglas respecto de variables para las que ya se usaban en \( d \)).

Podemos asegurar que existen tales funtores (sin necesidad de definirlos explícitamente) porque la demostración del teorema de deducción es totalmente constructiva: determina completamente qué teoremas \( P(d, \alpha) \) necesitamos tomar como premisas (y cuáles son sus demostraciones) y cómo construir una deducción de \( \alpha\rightarrow \beta \) a partir de una deducción de \( \beta \).

Pero todos estos detalles son irrelevantes. Lo importante es que el lector debería convencerse de que ahora puede releer todo lo dicho en este hilo no en color rojo considerando que está leyendo teoremas de ARP, en el mismo sentido que si abre cualquier libro de álgebra o de cálculo diferencial puede entender que está leyendo teoremas de ZFC a pesar de que no vea en ninguna parte chirimbolitos lógicos y axiomas ni nada de todo eso.

La respuesta a la pregunta: ¿qué es necesario suponer para estudiar metamatemáticamente la lógica formal (sin entrar en semántica (modelos, etc.)? es: como máximo (las versiones informales de) los axiomas y reglas de inferencia de ARP, lo cual es muy poco suponer.

08 Agosto, 2023, 12:55 am
Respuesta #23

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hemos definido la aritmética recursiva primitiva de forma muy particular, muy diferente a las teorías axiomáticas que consideran más habitualmente los lógicos y los matemáticos. Esta forma de presentarla es interesante porque deja bien claros cuales son sus (escasos) presupuestos. Los axiomas de ARP son más definiciones que axiomas (es verdad que afirman implícitamente que es posible definir funciones por composición y recursión, pero es discutible hasta qué punto eso es algo más que una definición), y sus reglas de inferencia son absolutamente elementales. La única con "sustancia" es el principio de inducción, y está restringido a meras igualdades de funciones computables.

Sin embargo, es posible revestir la aritmética recursiva primitiva de una lógica de primer orden usual, sin restricciones en el uso de "para todo" y "existe". La forma de hacerlo es la siguiente:

Consideramos un lenguaje formal cuyos signos sean:
  • Variables: \( x_0, x_1, x_2, \ldots, \)
  • La constante \( 0 \),
  • Todos los funtores de \( \mathcal L_{\rm arp} \),
  • El igualador \( = \)
  • Los conectores lógicos \( \lnot, \rightarrow, \lor, \land, \leftrightarrow \) (aunque algunos pueden suprimirse y definirse en términos de los otros),
  • Los cuantificadores \( \forall, \exists \) (aunque también podemos definir uno en términos del otro).
Llamamos ARP\( ^+ \) a la teoría axiomática (en el sentido usual de la lógica de primer orden) que tiene por axiomas las afirmaciones siguientes:

  • Todos los axiomas de ARP (es decir, los que definen cada funtor excepto \( S \)).
  • \( Sx\neq 0 \)
  • \( Sx = Sy\rightarrow x = y \)
  • \( \alpha(0)\land \forall x(\alpha(x)\rightarrow \alpha(Sx))\rightarrow \forall x\, \alpha(x), \)
    donde \( \alpha(x) \) es cualquier fórmula sin cuantificadores.
Aquí hay que entender que ARP\( ^+ \) incluye además los axiomas lógicos y las reglas de inferencia usuales de la lógica de primer orden, que hacen que a partir de los axiomas anteriores se pueda deducir todo lo que un matemático diría que se puede deducir.

Así tenemos una teoría matemática "usual", es decir, sin limitaciones de carácter lógico, como que nos impidan usar cuantificadores, y cosas así. Lo más parecido es la exigencia de que sólo podemos usar el principio de inducción para fórmulas sin cuantificadores.

En estos términos, cada fórmula de \( \mathcal L_{\rm arp} \) es también una fórmula del lenguaje de ARP\( ^+ \). Y puede probarse lo siguiente:

Teorema: Una fórmula del lenguaje \( \mathcal L_{\rm arp} \) es demostrable en ARP\( ^+ \) si y sólo si es demostrable en ARP.

Más aún, se puede probar que los conectores y los cuantificadores acotados definidos aritméticamente en ARP son equivalentes a los signos lógicos de ARP\( ^+ \), es decir, que, por ejemplo, una fórmula como

\( x = 0\lor \exists y\leq  x\, x = y+1 \)

puede entenderse de dos formas, una en la que \( \lor \) y \( \exists y\leq x \) son los definidos aritméticamente en ARP y otra en la que son los signos lógicos del lenguaje de ARP\( ^+ \), pero ambas fórmulas son equivalentes en ARP\( ^+ \).

Esto se traduce en que si llamamos fórmulas \( \Delta_0 \) a las fórmulas del lenguaje de ARP\( ^+ \) en las que sólo aparecen cuantificadores acotados, todas ellas son equivalentes a fórmulas de ARP, es decir, a meras igualdades entre términos, y en particular son equivalentes a fórmulas sin cuantificadores. Esto implica que, en realidad, el principio de inducción en ARP\( ^+ \) es válido para fórmulas \( \Delta_0 \), es decir, para fórmulas en las que todos los cuantificadores están acotados.

De este modo, podemos trabajar en ARP\( ^+ \) sin limitaciones lógicas, es decir, usando cuantificadores a voluntad, con la garantía de que todos los teoremas que demostremos con tal libertad que sean enunciables en el lenguaje de ARP, serán de hecho demostrables en ARP.

En la práctica la diferencia es menor de lo que parece, pues igualmente tenemos que ir acotando cuantificadores para justificar que las fórmulas a las que queremos aplicar el principio de inducción tienen todos sus cuantificadores acotados.

Así pues, ARP\( ^+ \) es una teoría axiomática de primer orden "usual", pero que permite reconocer en ella los teoremas de ARP. Podríamos haber definido así ARP, pero entonces no estaría claro por qué restringir el principio de inducción a fórmulas sin cuantificadores es sinónimo de "finitismo estricto". Sería algo plausible, en todo caso, pero no podríamos ver lo que realmente supone esa restricción.

Pero podemos ir más lejos:

Consideremos ahora el lenguaje \( \mathcal L_a \) de la aritmética, cuyos signos son:
  • Variables,
  • La constante \( 0 \),
  • Los funtores \( S, +, \cdot \),
  • El igualador \( = \)
  • Los conectores lógicos y los cuantificadores.
Identificando los funtores \( S, +, \cdot \) con los del lenguaje de ARP, podemos identificar cada fórmula de \( \mathcal L_a \) con una fórmula del lenguaje de ARP, pero ahora no tenemos todos los funtores que nombran las funciones recursivas primitivas.

La aritmética de Peano es la teoría axiomática sobre este lenguaje cuyos axiomas son:

  • \( Sx\neq 0 \)
  • \( Sx = Sy\rightarrow x = y \)
  • \( x+0 = x \)
  • \( x+Sy = S(x+y) \)
  • \( x\cdot 0 = 0 \)
  • \( x\cdot Sy = x\cdot y + x \)
  • \( \alpha(0)\land \forall x(\alpha(x)\rightarrow \alpha(Sx))\rightarrow \forall x\, \alpha(x), \)
    para toda fórmula \( \alpha(x) \) de \( \mathcal L_a \).
En \( \mathcal L_a \) podemos definir la relación de orden como \( x\leq y\equiv \exists z\, z+x = y \), y podemos definir igualmente las fórmulas \( \Delta_0 \) como las fórmulas que sólo tienen cuantificadores acotados. Si restringimos el principio de inducción a fórmulas \( \Delta_0 \) obtenemos la llamada Aritmética con Inducción Abierta (IA), y es claro que todo teorema de IA es un teorema de ARP\( ^+ \), pero IA es mucho más débil, porque no tenemos en ella todos los funtores de ARP.

Sin embargo, la situación es muy distinta si restringimos el principio de inducción a una clase de fórmulas ligeramente más amplia: la de las fórmulas de tipo \( \Sigma_1 \), que son las fórmulas de la forma \( \exists x\alpha \), donde \( \alpha \) es una fórmula \( \Delta_0 \).

La teoría que resulta de restringir en AP el principio de inducción a fórmulas de tipo \( \Sigma_1 \) recibe el nombre de \( {\rm I}\Sigma_1 \), y sucede que está estrechamente relacionada con ARP.

Por una parte:
Todas las funciones recursivas primitivas son definibles en \( {\rm I}\Sigma_1 \).

Precisar lo que significa esto exactamente requiere algunos tecnicismos, pero la idea es la siguiente:

Llamemos ARP\( ^{++} \) a la teoría que resulta de extender ARP\( ^+ \) admitiendo la inducción para fórmulas de tipo \( \Sigma_1 \). Entonces, toda fórmula \( \alpha \) del lenguaje de ARP\( ^+ \) es equivalente en ARP\( ^{++} \) a otra fórmula \( \alpha^* \) de \( \mathcal L_a \), es decir, a una fórmula en la que sólo aparecen los funtores \( S, +,\cdot \), de modo que \( \alpha \) es un teorema de ARP\( ^{++} \)  si y sólo si \( \alpha^* \)  es un teorema de \( {\rm I}\Sigma_1 \).

Por lo tanto, \( {\rm I}\Sigma_1 \) es equivalente a ARP\( ^{++} \), en el sentido de que cualquier teorema expresable en ARP\( ^{++} \) puede expresarse (y demostrarse) también en \( {\rm I}\Sigma_1 \).

Aparentemente, estas dos teorías son más fuertes que ARP o ARP\( ^+ \), pues cuentan con el principio de inducción para fórmulas de tipo \( \Sigma_1 \), pero en realidad no es así:

Teorema Toda fórmula de tipo \( \Sigma_1 \) es demostrable en ARP\( ^+ \) si y sólo si es demostrable en ARP\( ^{++} \) o (equivalentemente) en \( {\rm I}\Sigma_1 \).

En particular, toda fórmula \( \alpha \) del lenguaje de ARP es equivalente a una fórmula \( \alpha^* \) de \( \mathcal L_a \), de modo que \( \alpha \) es demostrable en ARP si y sólo si \( \alpha^* \) es demostrable en \( {\rm I}\Sigma_1 \).

Así pues, ARP está perfectamente identificada dentro de \( {\rm I}\Sigma_1 \), que no es sino la aritmética de Peano con la inducción restringida a fórmulas \( \Sigma_1 \). En esta teoría se puede definir todo lo definible en ARP y todos los teoremas de \( {\rm I}\Sigma_1 \) equivalentes a fórmulas de \( \mathcal L_{\rm arp} \) son teoremas de ARP.

En particular, la consistencia de ARP implica la de \( {\rm I}\Sigma_1 \).

Así pues, para hacer "matemática estrictamente finitista" no hace falta encerrarse en una teoría extraña, sino que basta trabajar en AP restringiendo el principio de inducción a fórmulas de tipo \( \Sigma_1 \). Por supuesto no es evidente en absoluto que esta restricción sea sinónimo de "finitismo estricto", y de ahí que tenga interés haber definido independientemente ARP, así como los teoremas que la relacionan con \( {\rm I}\Sigma_1 \).

Pero todavía se puede ensanchar más el alcance de la matemática finitista si pasamos a considerar teorías de segundo orden.

En una aritmética de segundo orden tenemos dos clases de objetos: números naturales y conjuntos de números naturales. También tenemos una relación de pertenencia \( n\in A \) que expresa si un número \( n \) es o no un elemento de un conjunto \( A \), pero no se trata de una teoría de conjuntos porque los conjuntos no pueden ser elementos de otros conjuntos. Los elementos de los conjuntos son siempre números.

La teoría RCA\( _0 \) es la aritmética de segundo orden que, además de los axiomas y reglas de inferencia lógicas necesarias para que se pueda razonar en ellas como lo razonan los matemáticos, tenemos los axiomas de \( {\rm I}\Sigma_1 \) y dos axiomas de segundo orden, el de extensionalidad:

\( \forall XY(\forall n(n\in X\leftrightarrow n\in Y)\rightarrow X = Y) \)

(donde las variables en mayúsculas son variables de segundo orden, que representan conjuntos) y la variable minúscula es una variable de primer orden, que representa números)

y el axioma de comprensión:
\( \exists X\forall n(n\in X\leftrightarrow \phi(n)) \)

restringido a fórmulas \( \phi(n) \) de tipo \( \Delta_1^0 \). Para entender qué son estas fórmulas, definimos primero las fórmulas de tipo \( \Delta_0^0 \), que son las fórmulas que pueden tener variables de segundo orden libres (sin cuantificar) y variables de primer orden con cuantificadores acotados (el superíndice 0 indica que pueden aparecer variables de segundo orden sin cuantificar, al contrario que en las fórmulas \( \Delta_0 \), en las que no hay variables de segundo orden).

Las fórmulas \( \Sigma_1^0 \) son las de la forma \( \exists u\,\phi(u) \) (donde \( \phi \) es una fórmula \( \Delta_0^0 \), con posibles variables libres de primer y segundo orden).

Las fórmulas \( \Pi_1^0 \) son las de la forma  \( \forall u\,\phi(u) \), y las fórmulas \( \Delta_1^0 \) son las que son equivalentes tanto a una fórmula \( \Sigma_1^0 \) como a una fórmula \( \Pi_1^0 \).

Restringir el axioma de comprensión a fórmulas \( \Delta_1^0 \) tiene una interpretación muy natural: los conjuntos \( \Delta_1^0 \) (es decir, los conjuntos definibles por fórmulas \( \Delta_1^0 \)) son los conjuntos computables, es decir, los conjuntos para los que un ordenador nos puede decir en un tiempo finito si cualquier número natural dado pertenece o no al conjunto.

Pues bien, todo teorema de \( {\rm I}\Sigma_1 \) resulta ser claramente un teorema de RCA\( _0 \), pero también tenemos un recíproco:

Teorema Una fórmula de \( \mathcal L_a \) es un teorema de RCA\( _0 \) si y sólo si lo es de \( {\rm I}\Sigma_1 \).

En particular, cualquier teorema que probemos en RCA\( _0 \) que sea expresable en el lenguaje de ARP es un teorema de ARP y, más en particular, si ARP es consistente, también lo es RCA\( _0 \).

Pero en RCA\( _0 \) se puede definir el concepto de modelo de un lenguaje formal de primer orden, y casi se puede demostrar el teorema de completitud de Gödel, es decir, que una teoría es consistente si y sólo si tiene un modelo. El "casi" es porque para demostrar el teorema de completitud hace falta un axioma más, el llamado lema de König débil, pero de nuevo estamos de suerte: la teoría WKL\( _0 \) que resulta de añadir este axioma a RCA\( _0 \) cumple también el teorema anterior:

Teorema Una fórmula de \( \mathcal L_a \) es un teorema de WKL\( _0 \) si y sólo si lo es de \( {\rm I}\Sigma_1 \).

Se podría filosofar sobre si WKL\( _0 \) es o no una teoría "finitista", pero, desde luego, es una teoría "avalada por el finitismo", en el sentido de que es consistente si lo es ARP, y en ella no se puede demostrar ningún teorema expresable en el lenguaje de ARP que no sea ya demostrable en ARP. Sin embargo en ella se puede formalizar casi todo lo que hemos puesto en rojo en este hilo y mucho más de mismo estilo (como el teorema de completitud).

El "casi" ahora se debe a que en ella podemos definir lo que es un modelo de ARP, y podemos demostrar que ARP es consistente si y sólo si tiene un modelo, pero seguimos sin poder definir en ella el modelo natural de ARP, es decir, no podemos definir la función que a cada funtor le asigna la función que denota. (Los hechos enunciados en rojo se pueden probar para "un" modelo arbitrario de ARP, pero no para "el" modelo natural.)

Ninguno de los hechos que he mencionado aquí es evidente. El único propósito de este mensaje final de este hilo es dar una idea de cómo se relaciona ARP con otras teorías aritméticas.