Veamos algunos ejemplos sencillos de lo que supone trabajar en ARP. Probar las propiedades básicas de la suma y el producto nos ha dado un poco de guerra porque todavía no teníamos plenamente desarrollada la lógica de ARP, por lo que conviene comparar con lo que cuesta ahora estudiar la potenciación.
A partir de ahora ya no escribiremos nunca \( St \), sino que en su lugar escribiremos \( t+1 \), puesto que la fórmula \( Sx = x+1 \) es un teorema de ARP que nos permite transformar cualquier expresión que contenga un término \( St \) por la que resulta de sustituirlo por \( t+1 \), y viceversa.
Potenciación Con lo que sabemos de ARP, para definir la potenciación de números naturales basta con definirla como el funtor diádico determinado por las fórmulas
\( x^0 = 1,\qquad x^{y+1} = x^y\cdot x \)
Sabemos que estas ecuaciones son ciertamente la definición de un funtor de ARP, y las propiedades siguientes se demuestran fácilmente por inducción, sin necesidad de ninguna idea específica de ARP, es decir, con los mismos argumentos con los que podemos verlas demostradas en cualquier libro que exponga la aritmética elemental:
- \( x^{y+z}=x^yx^z \),
- \( (xy)^z=x^zy^z \),
- \( (x^y)^z = x^{yz} \),
- \( x>0\rightarrow 0^x=0 \),
- \( 1^x =x \),
- \( x\leq y\rightarrow x^z\leq y^z \),
- \( x\geq 1\land y\leq z\rightarrow x^y\leq x^z \),
- \( x\geq 2\rightarrow y< x^y \).
Veamos la última como ejemplo:
Demostración
Razonamos por inducción sobre \( y \). Para \( y=0 \) es inmediato. Supuesto cierto para \( y \), o bien \( y=0 \), en cuyo caso se cumple que \( y+1=1< x=x^1=x^{y+1} \), o bien \( y\geq 1 \), en cuyo caso
\( x^{y+1}=x^y\cdot x \geq x^y\cdot 2> y\cdot 2=y+y\geq y+1. \)
División euclídea El teorema de la división euclídea dice que, para todo dividendo \( D \) y todo divisor \( d\neq 0 \), existen un único cociente \( c \) y un único resto \( r \) tales que \( D = dc+r \) y \( 0\leq r<d \).
El problema a la hora de formalizar esto en ARP es que no podemos formalizar el "existen". Ahora bien, esto tiene dos soluciones posibles. Una es observar que, necesariamente, \( c\leq D \) y \( r<d \), por lo que podemos formalizar la existencia como \( \exists c\leq D \exists r\leq d \). En general, para enunciar un teorema de existencia en ARP tenemos que ser capaces de acotar los números que queremos probar que existen.
Pero en realidad podemos hacer algo más fino, y es definir funtores que calculen explícitamente los números cuya existencia queremos probar. Vamos a emplear esta estrategia. Para ello definimos los funtores diádicos:
\( c(D, d)=\mu u\leq D\, D<d(u+1),\qquad r(D, d)=D\dot{-} d\cdot c(D, d) \),
y con ellos vamos a probar el teorema siguiente. Notemos que la primera afirmación es la existencia del cociente y el resto euclídeos y la segunda es la unicidad:
Teorema 1) \( d\neq 0\rightarrow D = d\cdot c(D, d)+r(D, d)\land r(D, d)<d \).
2) \( d\neq 0\land D = d\cdot c+ r\land r<d\rightarrow c = c(D, d)\land r = r(D, d) \).
Demostración
1) Como \( d\neq 0 \), tenemos que \( 1\leq d \), luego
\( D\leq dD<dD+d=d(D+1), \)
y esto prueba que \( \exists u\leq D\,D<d(u+1) \), luego \( D<d\cdot (c(D, d)+1) \). Tiene que ser \( d\cdot c(D, d)\leq D \), pues si fuera \( D<d\cdot c(D,d) \), entonces \( c(D, d)\neq 0 \), luego, llamando \( c'\equiv c(D, d)\dot{-} 1 \), se cumpliría \( c(D, d)=c'+1 \), luego \( c'<c(D, d) \) y \( D<d\cdot (c'+1) \), en contra de la minimalidad de \( c(D,d) \). Así pues:
\( d\cdot c(D, d)\leq D<d\cdot (c(D, d)+1). \)
Por la definición de \( \leq \), la primera desigualdad implica que
\( D=d\cdot c(D, d)+r(D,d). \)
Tiene que ser \( r(D, d)<d \), pues si \( d\leq r(D, d) \), entonces
\( d+(r(D, d)\dot{-} d)=r(D, d) \)
y así
\( D=d\cdot c(D, d)+d+(r(D, d)\dot{-} d)=d\cdot (c(D, d)+1)+(r(D, d)\dot{-} d), \)
luego \( d\cdot (c(D, d)+1)\leq D \), contradicción.
2) Tenemos que \( dc\leq D=dc+r<dc+d=d(c+1) \), luego la minimalidad de \( c(D, d) \) implica que \( c(D, d)\leq c \). Si la desigualdad fuera estricta, \( c(D, d)+1\leq c \), luego
\( D<d(c(D, d)+1)\leq dc\leq dc+r=D, \)
y tenemos una contradicción. Por lo tanto, \( c=c(D, d) \), y como
\( d\cdot c(D, d)+r(D, d)=D=d\cdot c+r=d\cdot c(D, d)+r, \)
también \( r=r(D, d) \).
Por ejemplo, ahora podemos clasificar a los números naturales en
pares e
impares, según si \( r(D, 2)=0 \) o \( r(D, 2)=1 \). Equivalentemente, por la unicidad de la división euclídea, los números pares son los de la forma \( 2n \) y los impares los de la forma \( 2n+1 \). Es fácil probar que
\( r(ab,2)=r(a, 2)r(b, 2), \)
de modo que el producto de par por par o par por impar es par, mientras que el producto de impares es impar.
Pares ordenados Ahora podemos formalizar la definición de par ordenado que dimos en
este mensaje. Informalmente, el par ordenado \( \left<x, y\right>_2 \) determinado por dos números naturales \( x,y \) es el número natural
\( \left<x, y \right>_2 = \dfrac{(x+y)(x+y+1)}2+x \).
La formalización en ARP es ahora muy simple:
Definición Consideramos el funtor definido por:
\( \left<x, y\right>_2=c\bigl((x+y)(x+y+1), 2\bigr)+x. \)
Claramente, el dividendo en el funtor cociente euclídeo es el producto de un número par por uno impar, por lo que la división es exacta, es decir, \( r\bigl((x+y)(x+y+1), 2\bigr)=0 \), por lo que el teorema de la división euclídea nos da que
\( 2\left<x, y\right>_2=(x+y)(x+y+1)+2x. \)
Observemos ahora que
\( (z+1)(z+2)=z^2+3z+2\geq 2z+2>2z. \)
Por lo tanto, si definimos el funtor
\( F(z)=\mu u\leq z+1\ (2z<u(u+1)), \)
tenemos que \( z+1 \) cumple la propiedad considerada, luego
\( 2z<F(z)(F(z)+1)\qquad \mbox{y}\qquad F(z)\leq z+1. \)
No puede ser \( F(z)=0 \), luego si definimos \( G(z)=F(z)\dot{-} 1 \), se cumple que \( F(z)=G(z)+1 \) y, como \( G(z)<F(z) \), no puede cumplir la propiedad que define a \( F \), luego
\( G(z)(G(z)+1)\leq 2z<(G(z)+1)(G(z)+2),\qquad G(z)\leq z. \)
Observemos además que si un \( r \) cumple
\( r(r+1)\leq 2z<(r+1)(r+2), \)
necesariamente \( r=G(z) \), pues por la minimalidad de \( F \) tenemos \( F(z)\leq r+1 \), luego \( G(z)\leq r \) y, si la desigualdad fuera estricta, \( G(z)+1\leq r \), luego
\( (G(z)+1)(G(z)+2)\leq r(r+1)\leq 2z, \)
y tenemos una contradicción. Definimos el funtor
\( z_1=c\bigl(2z\dot{-} G(z)(G(z)+1),2\bigr). \)
Es fácil ver que el argumento de \( c \) es par, por lo que
\( 2z=G(z)(G(z)+1)+2z_1 \).
Además se cumple que \( z_1\leq G(z) \), pues si fuera \( G(z)<z_1 \), entonces
\( 2G(z)<2z_1=2z\dot{-} G(z)(G(z)+1), \)
luego \( 2G(z)+G(z)(G(z)+1)<2z \), luego \( G(z)^2+3G(z)+1\leq 2z \). Otra vez, distinguiendo casos según si \( G(z) \) es par o impar, se comprueba que el miembro izquierdo siempre es impar, por lo que no puede darse la igualdad, luego
\( (G(z)+1)(G(z)+2)=G(z)^2+3G(z)+2\leq 2z, \)
en contradicción con la construcción de \( G \).
Por lo tanto, \( z_1\leq G(z) \), luego el funtor
\( z_2=G(z)\dot{-} z_1 \)
cumple \( G(z)=z_1+z_2 \) y
\( 2z=G(z)(G(z)+1)+2z_1=(z_1+z_2)(z_1+z_2+1)+2z_1=2\left<z_1,z_2\right>_2, \)
luego \( z=\left<z_1,z_2\right>_2 \).
El teorema siguiente recoge las propiedades que hemos demostrado de los funtores \( \left<x,y\right>_2 \), \( z_1 \) y \( z_2 \) junto con algunas más:
Teorema Se cumple:
- \( z=\left<z_1,z_2\right>_2 \),
- \( z_1+ z_2\leq z \),
- \( z=\left<x, y\right>_2\rightarrow x=z_1\land y=z_2 \).
Demostración
Ya hemos demostrado la primera afirmación, y también la segunda, pues hemos visto que \( z_1+z_2 = G(z)\leq z \).
Si \( z=\left<x, y\right>_2 \), llamando \( r=x+y \), tenemos que \( 2z=r(r+1)+2x \), con \( x\leq r \), luego
\( r(r+1)\leq 2z\leq r^2+r+2x\leq r^2+3r<r^2+3r+2=(r+1)(r+2), \)
y antes hemos probado que esto implica \( r=G(z)=z_1+z_2 \), luego
\( (z_1+z_2)(z_1+z_2+1)+2z_1=2z=r(r+1)+2x \)
implica que \( 2x=2z_1 \), luego \( x=z_1 \), y entonces \( z_1+z_2=x+y \) implica que \( y=z_2 \).
Con esto hemos probado que cada número natural \( z \) se expresa de forma única como un par \( \left<z_1,z_2\right>_2 \) de números naturales. Tanto la función que a cada par de números naturales le asigna el número \( \left<z_1,z_2\right>_2 \) como las proyecciones que a cada \( z \) le asignan sus coordenadas \( z_1 \) y \( z_2 \) son funciones recursivas primitivas.
Sucesiones finitas Ahora podemos formalizar la codificación de las sucesiones finitas de números naturales expuesta en
este mensaje.
Concretamente, podemos considerar el funtor
\( \left<x, y, z\right>_3=\left<\left<x, y\right>_2, z\right>_2 \)
y las proyecciones \( z^3_1=(z_1)_1 \), \( z^3_2=(z_1)_2 \), \( z^3_3=z_2 \), de modo que
\( z=\left<z_1,z_2,z_3\right>,\qquad z = \left<u, v, w\right>_3\rightarrow u = z_1\land v=z_2\land w=z_3. \)
Así, podemos identificar los números naturales con las ternas de números naturales. En general, podemos definir los funtores
\( \left<x_1,\ldots, x_n\right>_n=\left<\left<x_1,\ldots, x_{n-1}\right>_{n-1},x_n\right>_2 \)
y las proyecciones
\( p^n_i(z)=p^{n-1}_i(z_1) \), para \( i<n \),
\( p^n_n(z)=z_2 \).
Si definimos \( \left<x\right>_1=x \), estas definiciones coinciden con las que ya teníamos en el caso \( n=2 \).
Nota Observemos que no hemos definido un funtor \( \left<x_1,\ldots, x_n\right>_n \) de rango \( n+1 \), sino infinitos funtores de rango \( n \). Igualmente, la definición de las proyecciones no es la definición de un único funtor \( p^n_i(z) \) de rango \( 3 \), sino que estamos definiendo infinitos funtores de rango \( 1 \), cada uno con su propia definición.
Razonando por inducción sobre \( n \), se prueba sin dificultad que
\( z=\left<p^n_1(z),\ldots, p^n_n(z)\right>_n,\quad z=\left<x_1,\ldots, x_n\right>_n\rightarrow x_1=z_1\land \cdots \land x_n=z_n.
\)
(Ojo, no me refiero a aplicar ninguna de las reglas de inducción de ARP, sino que las fórmulas anteriores representan infinitos teoremas de ARP, y lo que digo es que, suponiendo que ya hemos demostrado los teoremas correspondientes a \( n \), podemos probar los correspondientes a \( n+1 \), con lo que tenemos infinitas demostraciones, cada una más larga que la anterior.)
Finalmente definimos una nueva familia de infinitos funtores:
\( \left<x_1,\ldots, x_n\right>^n_\infty=\left<n \dot{-}1,\left<x_1,\ldots, x_n\right>_n\right>_2+1. \)
De este modo, ya no tenemos que un mismo natural codifica sucesiones de longitudes distintas, sino que, con este criterio, cada número natural no nulo \( s \) codifica una única sucesión (siempre podemos interpretarlo como un par, considerar el \( n \) que sale de sumar \( 1 \) a su primera componente, e interpretar su segunda componente como una sucesión de longitud \( n \) precisamente.
Podemos considerar que el número natural \( 0 \) codifica la sucesión vacía que tiene \( 0 \) términos. Más precisamente, definimos la
longitud de un número natural como
\( \ell(s)=(1\dot{-}(1\dot{-} s))((s\dot{-}1)_1+1). \)
Así, \( \ell(0)=0 \), mientras que si \( s\neq 0 \), entonces \( \ell(s)>0 \) y \( (s\dot{-}1)_1=\ell(s)\dot{-}1 \).
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)=(1\dot{-} i)R\bigl(s, (s\dot{-}1)_1\bigr)+(1\dot{-} (1\dot{-} i))R\bigl(s, (s\dot{-} 1)_1\dot{-} i\bigr)_2. \)
Notemos que la segunda definición se puede expresar más naturalmente, así:
\( 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) \).
Notemos que \( \ell(s)\leq s \) y \( \forall i<\ell(s)\, s_i\leq s \).
Veamos que todo número natural, visto como sucesión, está unívocamente determinado por sus proyecciones.
Teorema \( \ell(s)=\ell(t)\land (\forall i<\ell(s)\, s_i=t_i)\rightarrow s=t \).
Demostración
Si \( \ell(s)=\ell(t)=0 \), entonces \( s=t=0 \). Supongamos que \( \ell(s)=\ell(t)>0 \). Entonces
\( l=(s\dot{-} 1)_1=\ell(s)\dot{-} 1=\ell(t)\dot{-} 1=(t\dot{-} 1)_1. \)
Veamos por inducción que
\( i\leq l \rightarrow R(s, l\dot{-} i)=R(t, l\dot{-} i). \)
Para \( i=0 \) tenemos que
\( R(s, l)=s_0=t_0=R(t, l). \)
Si es cierto para \( i<l \), entonces \( i+1\leq l \), luego \( i+1+(l\dot{-} (i+1))=l \), de donde \( (l\dot{-}(i+1))+1=l\dot{-} i \). Por lo tanto,
\( R(s, l\dot{-}(i+1))_1=R(s, (l\dot{-} (i+1))+1)=R(s, l\dot{-} i)=R(t, l\dot{-} i)=R(t, l\dot{-} (i+1))_1. \)
Por otra parte,
\( R(s, l\dot{-}(i+1))_2=s_{i+1}=t_{i+1}=R(t, l\dot{-}(i+1))_2, \)
luego \( R(s, l\dot{-}(i+1))=R(t, l\dot{-}(i+1)) \). Esto completa la inducción y, aplicándolo a \( i=l \) obtenemos
\( (s\dot{-} 1)_2=R(s, 0)=R(t, 0)=(t\dot{-} 1)_2, \)
pero \( (s\dot{-} 1)_1=l=(t\dot{-} 1)_1 \), luego de hecho \( s\dot{-} 1=t\dot{-} 1 \), luego \( s=t \).
Una comprobación rutinaria muestra que
\( p^\infty_i(\left<x_0,\ldots, x_{n-1}\right>^n_\infty)=x_i, \)
lo que prueba que toda sucesión finita de números naturales está codificada por un número natural. En la práctica podemos omitir el superíndice \( n \) en el funtor \( \left<x_0,\ldots, x_{n-1}\right>^n_\infty \), puesto que éste se deduce del número de argumentos.
No debemos confundir un número natural \( n \) con la sucesión de longitud \( 1 \) que lo tiene como único término. Ésta viene dada por el funtor
\( \left<n\right>_\infty = \left<0,n\right>_2+1. \)
Manipulación de sucesiones Definimos ahora algunos conceptos elementales sobre sucesiones, como lo que significa que una sucesión extienda a otra, o lo que es el principio y el final de una sucesión hasta o desde una posición prefijada, etc.
Observemos que, una vez queda claro que estos conceptos son definibles en ARP, lo que cuesta dar pruebas detalladas no se debe a limitaciones lógicas de ARP, sino a que son conceptos técnicos, de modo que costaría lo mismo dar las mismas pruebas en una teoría tan cómoda desde un punto de vista lógico como ZFC. De hecho, la moraleja que el lector debería sacar de estos ejemplos es que, una vez comprobado que los conceptos se pueden definir, las demostraciones de las propiedades básicas son pura rutina, sin que el hecho de estar trabajando en ARP sea determinante para nada.
Diremos que una sucesión \( t \)
extiende a otra \( s \) si
\( s\sqsubseteq t\equiv \ell(s)\leq \ell(t)\land \forall i<\ell(s)\, s_i=t_i. \)
Es fácil ver que:
- \( s\sqsubseteq s \),
- \( s\sqsubseteq t\land t\sqsubseteq s\rightarrow s=t \),
- \( s\sqsubseteq t\land t\sqsubseteq u\rightarrow s\sqsubseteq u \),
- \( 0\sqsubseteq s \),
Definimos
\( s\frown\left<n\right>= (1\dot{-} s)\left<n\right>_\infty+(1\dot{-} (1\dot{-} s))(\left<\ell(s),\left<(s\dot{-} 1)_2,n\right>_2\right>_2+1).
\)
Una comprobación rutinaria muestra que
\( \ell(s\frown \left<n\right>)=\ell(s)+1,\quad s\sqsubseteq s\frown \left<n\right>,\quad (s\frown \left<n\right>)_{\ell(s)}=n.
\)
Vemos así que \( s\frown \left<n\right> \) no es sino la sucesión que resulta de añadir \( n \) como último término a la sucesión representada por \( s \). Más en general, definimos
\( s\frown t = F(s, t, \ell(t)), \)
donde \( F \) es el funtor dado por
\( F(s,t, 0)=s,\qquad F(s, t,n+1)=F(s, t, n)\frown \left<t_n\right>. \)
De nuevo una comprobación rutinaria muestra que
\( \ell(s\frown t)=\ell(s)+\ell(t), \quad \forall i<\ell(s) (s\frown t)_i=s_i,\quad \forall i<\ell(t)\,(s\frown t)_{\ell(s)+i}=t_i.
\)
En particular, \( s\sqsubseteq s\frown t \).
Definimos la
restricción de una sucesión mediante el funtor dado por
\( s|_0=0,\qquad s|_{i+1}=s|_i\frown \ \left<s_i\right>. \)
Es fácil probar que \( i\leq \ell(s)\rightarrow \ell(s|_i)=i\land s|_i\sqsubseteq s. \) Más aún, si \( t\sqsubseteq s \), entonces \( t=s|_{\ell(t)} \).
Similarmente definimos \( s|^i= F(s, i, \ell(s)\dot{-} i) \), donde
\( F(s,i, 0)=s_i,\qquad F(s, i, n+1)=F(s, i, n)\frown \left<s_{i+n}\right>. \)
Así, si \( i\leq \ell(s) \), se cumple que \( \ell(s|^i)=\ell(s)\dot{-}i \) y \( s=s|_i\frown s|^i \).
A partir de este momento ya no usaremos más los funtores \( \left<x_1,\ldots, x_n\right>_n \) ni sus proyecciones correspondientes, sino que siempre que hablemos de sucesiones de números naturales consideraremos los funtores \( \left<x_1,\ldots, x_n\right>_\infty \) y las proyecciones dadas por el funtor \( p^\infty_i(s) \), de rango \( 2 \).
Si \( F(x_1,\ldots, x_{n+1}) \) es un funtor de rango \( n+1 \), podemos definir a partir de él otro funtor igualmente de rango \( n+1 \) dado por
\( F|_0(x_1,\ldots, x_n)=0,\ F|_{x+1}(x_1,\ldots, x_n)=F|_x(x_1,\ldots, x_n)\frown \left<F(x_1,\ldots, x_n, x)\right>.
\)
Es claro que \( \ell(F|_x(x_1,\ldots, x_n))=x \) y
\( \forall i<x\, F|_x(x_1,\ldots, x_n)_i=F(x_1,\ldots, x_n, i). \)
Más explícitamente:
\( F|_x(x_1,\ldots, x_n) = \left<F(x_1,\ldots, x_n,0),\ldots, F(x_1,\ldots, x_n,n-1)\right>_\infty. \)
Con esto podemos definir un funtor \( F(x_1, \ldots, x_n, n) \) suponiendo definidos los valores \( F(x_1,\ldots, x_n,0),\ldots, F(x_1,\ldots, x_n,n-1) \). Más precisamente:
Teorema (Recursión completa) Si \( G \) es un funtor de rango \( n+2 \), existe un funtor \( F \) de rango \( n+1 \) tal que\( F(x_1,\ldots, x_n, x)=G(x_1,\ldots, x_n, x, F|_x(x_1,\ldots, x_n)). \)
Demostración
Definimos un funtor \( H \) mediante
\begin{array}{r@{\ }c@{\ }l}
H(x_1,\ldots, x_n,0)&=&0,\\[1mm]
H(x_1,\ldots, x_n,x+1)&=&H(x_1,\ldots, x_n,x)\frown \left<G(x_1,\ldots, x_n, x, H(x_1,\ldots, x_n, x))\right>.
\end{array}
Y a su vez,
\( F(x_1,\ldots, x_n, x)=H(x_1,\ldots, x_n,x+1)_x. \)
Veamos que \( F \) cumple lo requerido. Por aligerar la notación escribiremos \( \bar x \) en lugar de \( x_1,\ldots, x_n \). En primer lugar, una simple inducción nos da que \( \ell(H(\bar x,x))=x \). En segundo lugar, \( H(\bar x, x)=F|_x(\bar x) \). En efecto, para \( x=0 \) es
\( H(\bar x,0)=0=F|_0(\bar x), \)
y si vale para \( x \), entonces, como \( \ell(H(\bar x, x+1))=x+1 \), la definición de \( H \) implica que
\( H(\bar x, x+1)=H(\bar x, x)\frown \left<H(\bar x, x+1)_x\right>, \)
luego por la hipótesis de inducción y la definición de \( F \):
\( H(\bar x, x+1)=F|_x(\bar x)\frown \left<F(\bar x,x)\right>=F|_{x+1}(\bar x) \).
Finalmente probamos por inducción que \( F \) cumple la propiedad del enunciado:
\( F(\bar x,0)=H(\bar x,1)_0=G(\bar x,0,0)=G(\bar x, 0, F|_0(\bar x)), \)
\( F(\bar x, x+1)=H(\bar x, x+2)_{x+1}=G(\bar x, x+1, H(\bar x, x+1))=G(\bar x, x+1, F|_{x+1}(\bar x)). \)
Por ejemplo, ahora podemos definir la sucesión de Fibonacci en ARP:
\( F(0) = F(1) = 1, \quad F(n+1) = F(n\dot{-}1)+F(n). \)
Para ajustarnos al teorema anterior definimos el funtor
\( G(x, s) = \cases{1&si $\ell(s)\leq 1$,\cr s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}&si $\ell(s)\geq 2$,} \)
o, equivalentemente,
\( G(x, s) = \chi_{z\leq y}(\ell(s), 1)+\chi_{z\leq y}(2, \ell(s))( s_{\ell(s)\dot{-} 2}+s_{\ell(s)\dot{-} 1}), \)
de modo que \( F(n) = G(n, F|_n) \).
Notemos en general cómo podemos usar funciones características de fórmulas para formalizar en ARP cualquier definición por casos de un funtor.
En el próximo mensaje formalizaremos en ARP la expresión decimal (o en cualquier base) de un número natural. Aparte de que esto es un hecho básico de la aritmética tal y como la manejamos normalmente, veremos que de ahí podemos extraer consecuencias nada triviales sobre la capacidad expresiva de ARP.