04 Abril, 2020, 11:11 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Propiedad de Funciones de Ackermann  (Leído 1802 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« : 08 Mayo, 2010, 13:06 »

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
[texx]s(x)=x+1[/texx]

[texx]f_{0}(x)=x+1=s(x)[/texx]
[texx]f_{k+1}(x)=f_{k}^{(x+2)}(x)[/texx]

Es decir:
[texx]f_{1}(x)=s^{(x+2)}(x)=2x+2[/texx]
[texx]f_{2}(x)=(s^{(x+2)})^{x+2}(x)[/texx]

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
[texx]* Sea \; k \in \mathbb{N} ,\; f_{k} \in FRP[/texx]
[texx]* Sea \; a > b ,\; f_{k}(a) > f_{k}(b)[/texx]
[texx]* Sea \; x,k \in \mathbb{N} ,\; f_{k}(x) > x[/texx]
[texx]* Sea \; k \in \mathbb{N} ,\; f_{k+1}(x) > f_{k}(x)[/texx]

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
[texx]f_{k+1}(a)=f_{k}^{a+2}(a)>f_{k}^{a+2}(b)[/texx]  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?
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.869



Ver Perfil
« Respuesta #1 : 08 Mayo, 2010, 13:56 »

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 [texx]f_ {k}(a)>b[/texx]  para cualquier [texx]a>b[/texx] y [texx]k\in\mathbb{N}[/texx] y aplicando nuevamente la tercera propiedad podemos deducir que [texx]f^{m}_{k}(a)>b[/texx] para cualesquiera [texx]m\geq 1[/texx], [texx]a>b[/texx] y [texx]k\in\mathbb{N}[/texx]. Usaremos esto en nuestra prueba de la monotonía de las funciones de Ackermann.

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

[texx]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)[/texx]

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

Saludos.
En línea
Leusss
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 315


Ver Perfil
« Respuesta #2 : 08 Mayo, 2010, 14:02 »

Hola, Eze. Así lo hice yo:

Para k=0:

[texx]a>b \Longrightarrow{a+1>b+1} \Longrightarrow{f_0(a) > f_0(b)}[/texx]

Supongo que vale para k=n, es decir [texx]f_k(a)>f_k(b)[/texx]

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

[texx]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))}[/texx]
Usando repetidas veces la propiedad para k=0, llegamos a que:

[texx]f_0^{f_k(b)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(b))[/texx] y ademas, con el mismo razonamiento [texx]f_0^{f_k(a)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(a))[/texx]

Por lo tanto [texx]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))}[/texx]

Que ya es un avance importante. Si repetís el proceso pero esta vez aplicando la [texx]f_1[/texx], 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ó  :sonrisa_amplia:.
En línea
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #3 : 08 Mayo, 2010, 14:32 »

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 [texx]x>y \Longrightarrow{f^{x}_{k}(x)>f^{y}_{k}(x)}[/texx] y no se si es tan trivial como lo planteas (al menos no lo veo directamente como para no tener que probarlo)
En línea
Leusss
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 315


Ver Perfil
« Respuesta #4 : 08 Mayo, 2010, 14:39 »

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

En fin, toda la demostración solo llega al caso [texx]f_1[/texx] creciente. Pero creo que repitiendo el algoritmo de demostración anterior llegas a [texx]f_2[/texx] y así en adelante. Es menos fuerte, verdad, pero sospecho que es válido :lengua_afuera:.
En línea
EnRlquE
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Brazil Brazil

Mensajes: 5.869



Ver Perfil
« Respuesta #5 : 08 Mayo, 2010, 14:44 »

Hola.

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

Saludos.
En línea
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #6 : 08 Mayo, 2010, 19:15 »

Por si no te diste cuenta Leo escribiste esto:

[texx]f_0^{f_k(b)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(b))[/texx] y ademas, con el mismo razonamiento [texx]f_0^{f_k(a)+2}(f_k(a)) > f_0^{f_k(b)+2}(f_k(a))[/texx]


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


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

Para k=0:

[texx]a>b \Longrightarrow{a+1>b+1} \Longrightarrow{f_0(a) > f_0(b)}[/texx]

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

Veamos para [texx]k+1[/texx]
[texx]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)}[/texx]

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

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

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

En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!