[Click]

Hola, estoy demostrando propiedades sobre las funciones de Ackermann. Para los que no conocen esta familia de funciones las presento brevemente aquí
Son funciones que van de naturales a naturales, esta es su definición:

Llamaré sucesor de x a la función
\( s(x)=x+1 \)

\( f_{0}(x)=x+1=s(x) \)
\( f_{k+1}(x)=f_{k}^{(x+2)}(x) \)

Es decir:
\( f_{1}(x)=s^{(x+2)}(x)=2x+2 \)
\( f_{2}(x)=(s^{(x+2)})^{x+2}(x) \)

Y así sucesivamente, para más información: http://es.wikipedia.org/wiki/Funci%C3%B3n_de_Ackermann

Esta familia de funciones presenta varias propiedades
\( * Sea \; k \in \mathbb{N} ,\; f_{k} \in FRP \)
\( * Sea \; a > b ,\; f_{k}(a) > f_{k}(b) \)
\( * Sea \; x,k \in \mathbb{N} ,\; f_{k}(x) > x \)
\( * Sea \; k \in \mathbb{N} ,\; f_{k+1}(x) > f_{k}(x) \)

Mi problema es que no logro demostrar la segunda (que las funciones de Ackermann son crecientes)
Lo intento hacer por inducción pero siempre me termino "pisando la cola" y llegando a expresiones como
\( f_{k+1}(a)=f_{k}^{a+2}(a)>f_{k}^{a+2}(b) \)  y aquí no puedo decir que esta es la función de Ackermann evaluada en b porque está potenciada a la "a+2" y no a la "b+2"
Lo intenté de varias maneras, pero siempre me encontré con el mismo problema
Alguien me puede ayudar?

[EnRlquE]

Hola.

 Mostraremos por inducción que las funciones de Ackermann son crecientes, pero antes de eso intenta probar la tercera propiedad (ésta no es muy difícil), a partir de esta puedes deducir que \( f_ {k}(a)>b \)  para cualquier \( a>b \) y \( k\in\mathbb{N} \) y aplicando nuevamente la tercera propiedad podemos deducir que \( f^{m}_{k}(a)>b \) para cualesquiera \( m\geq 1 \), \( a>b \) y \( k\in\mathbb{N} \). Usaremos esto en nuestra prueba de la monotonía de las funciones de Ackermann.

 Para \( k=0 \) es claro que \( f_{0} \) es creciente, supongamos que \( f_ {k} \) es creciente y probemos que \( f_{k+1} \) también lo es. Para esto consideremos naturales \( a,\;b \) con \( a>b \). Por lo que vimos al inicio tenemos que \( f^{a-b}_{k}(a)>b \), luego como por hipótesis \( f_{k} \) es creciente tenemos que \( f_{k}(f^{a-b}_{k}(a))>f_{k}(b) \), y aplicando reiteradas veces \( f_{k} \) a la anterior desigualdad, deducimos que

\( f_{k}^{b+2}(f_{k}^{a-b}(a))>f_{k}^{b+2}(b)\;\Longrightarrow\;f_{k}^{a+2}(a)>f_{k}^{b+2}(b) \)

 De donde se concluye que \( f_{k+1}(a)>f_{k+1}(b) \). Cualquier duda, pregunta.

Saludos.

[Leusss]

Hola, Eze. Así lo hice yo:

Para k=0:

\( a>b \Longrightarrow{a+1>b+1} \Longrightarrow{f_0(a) > f_0(b)} \)

Supongo que vale para k=n, es decir \( f_k(a)>f_k(b) \)

\( f_k(a)>f_k(b) \Longrightarrow{f_0(f_k(a))>f_0(f_k(b))} \)(como mostramos en el caso k=0)

\( f_0(f_k(a))>f_0(f_k(b)) \Longrightarrow{f_0(f_0(f_k(a)))>f_0(f_0(f_k(b)))} \Longrightarrow{f_0^2(f_k(a))>f_0^2(f_k(b))} \)
Usando repetidas veces la propiedad para k=0, llegamos a que:

\( f_0^{f_k(b)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(b)) \) y ademas, con el mismo razonamiento \( f_0^{f_k(a)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(a)) \)

Por lo tanto \( f_0^{f_k(a)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(b)) \Longrightarrow{f_1(f_k(a))>f_1(f_k(b))} \)

Que ya es un avance importante. Si repetís el proceso pero esta vez aplicando la \( f_1 \), se deberia llegar a la conclusión pero no la escribo porque es muy engorrosa.

Saludos.
EDIT: La demostración de Braguildur es mucho más concisa pero bueno es lo que me salió  .

[Click]

La demostración de Braguildur la había pensado y sí, sale fácilmente así. Sin embargo, busco demostrarlo sin usar propiedades que están más adelante de la que estoy probando.

En cuanto a la tuya Leo no la veo muy fuerte porque usas que \( x>y \Longrightarrow{f^{x}_{k}(x)>f^{y}_{k}(x)} \) y no se si es tan trivial como lo planteas (al menos no lo veo directamente como para no tener que probarlo)

[Leusss]

Yo no supuse eso. Mostre \( f_0(a)>f_0(b) \Longrightarrow{f_0^{m}(a)>f_0^{m}(b)} \) simplemente porque primero mostre que \( a>b \Longrightarrow{f_0(a)>f_0(b)} \) y que lo primero es aplicar "m" veces esa propiedad.. o "m-1"...

En fin, toda la demostración solo llega al caso \( f_1 \) creciente. Pero creo que repitiendo el algoritmo de demostración anterior llegas a \( f_2 \) y así en adelante. Es menos fuerte, verdad, pero sospecho que es válido .

[EnRlquE]

Hola.

 Si prefieres puedes mostrar por inducción sobre \( k \) que para \( a>b \) y cualquier \( m\geq1 \) se verifica que \( f^{m}_{k}(a)>b \), sin hacer ninguna alusión a la tercera propiedad, es solo cuestión de gustos.

Saludos.

[Click]

Por si no te diste cuenta Leo escribiste esto:

\( f_0^{f_k(b)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(b)) \) y ademas, con el mismo razonamiento \( f_0^{f_k(a)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(a)) \)

Que a menos que yo entienda mal es decir esto:  \( x>y \Longrightarrow{f^{x}_{k}(a)>f^{y}_{k}(a)} \)
donde:
\( k=0 \) En realidad k es k porque despues harías lo mismo para todos los demás naturales
\( x=f_k(a) + 2 \)
\( y=f_k(b) + 2 \)


Yo lo había hecho así, viendo que es mejor usar la hipótesis inductiva que el caso base

Para k=0:

\( a>b \Longrightarrow{a+1>b+1} \Longrightarrow{f_0(a) > f_0(b)} \)

Supongo que vale para k, es decir \( a>b \Longrightarrow f_k(a)>f_k(b) \)

Veamos para \( k+1 \)
\( a>b \Longrightarrow{f_k(a) > f_k(b)} \Longrightarrow{f_k^2(a) > f_k^2(b)} \Longrightarrow \ldots \Longrightarrow{f_k^{a+2}(a) > f_k^{a+2}(b)}\Longrightarrow{f_{k+1}(a) > f_k^{a+2}(b)} \)

Me queda por probar que
\( a>b \Longrightarrow{f_k^{a+2}(b)>f_k^{b+2}(b)=f_{k+1}(b)} \)

Creo que esta es una propiedad demostrable  \( x>y \Longrightarrow{f^{x}_{k}(a)>f^{y}_{k}(a)} \)

Pero si me explicás como sale con lo que vos hacés Leo me ahorrás el trabajo...