Función de los naturales en los naturales

Publicado por ^DiAmOnD^ | 20 diciembre, 2010 | Juegos | 9 |

Vamos con el problema semanal. Hoy la cosa va de funciones en los naturales:

Demostrar que no existe ninguna función $f: \mathbb{N} \rightarrow \mathbb{N}$ tal que:

$f(f(n))=n+1, \; \forall n \in \mathbb{N}$

A por él.

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉

5 1 vote

Article Rating

Comparte:

Sobre el Autor

^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes encontrarme también en Twitter, en Instagram, en Geogebra.org y en Facebook.

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$ .

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX, te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Name*

Email*

Website

Name*

Email*

Website

9 Comments

más antiguo

más reciente más votado

Tweets that mention Función de los naturales en los naturales | Gaussianos -- Topsy.com

20/12/2010 08:26

[…] This post was mentioned on Twitter by gaussianos. gaussianos said: Gaussianos.com: Función de los naturales en los naturales http://bit.ly/gPdNMD […]

Responde

Sergio

20/12/2010 10:20

Consideramos $f(f(f(n)))$ que por una parte es $f(n+1)$ y por otra $f(n)+1$ . Por lo tanto, $f(n+1)-f(n)=1, \forall n \in \mathbb{N}$ . Es decir, $\exists n_{0}\in\mathbb{N}$ tal que $f(n)=n+n_{0}$ .

Por hipótesis, $f(f(n+1))-f(f(n))=1, \forall n \in \mathbb{N}$ y por lo tanto, $n_{0}=0.5\not\in\mathbb{N}$ , por lo que no puede existir tal $f:\mathbb{N}\rightarrow\mathbb{N}$

Responde

Tito Eliatron

20/12/2010 11:08

Yo lo había pensado más o menos igual. Dejo algún detalle más.

$f(n+1)=f[ff(n)]=fff(n)=ff[f(n)]=f(n)+1$ , por lo que $f(n+1)=f(n)+1$ y, por inducción, se llega a que $f(n)=f(1)+n-1$ .

Pero $n+1=ff(n)=f[f(1)+n-1]=f(1)+[f(1)+n-1]-1=2(f(1)-1)+n$ de donde $2(f(1)-1)=1$ y $f(1)=\frac{1}{2}$ lo que es imoposible.

Responde

Gulliver

20/12/2010 11:50

Generalizando, no existe ninguna función $f:\mathbb{N} \to \mathbb{N}$ tal que $f \circ f$ sea inyectiva y $\mathbb{N} \smallsetminus f(f(\mathbb{N}))$ sea finito y de cardinalidad impar y por tanto no existe tampoco ninguna función tal que $f(f(n)) = n+a$ con $a$ natural impar.

Esto se deduce de si $f \circ f$ es inyectiva entonces $f$ también lo es y de que los elementos de $\mathbb{N} \smallsetminus f(f(\mathbb{N}))$ van en pares $x$ y $f(x)$ para los que $x \in \mathbb{N} \smallsetminus f(\mathbb{N})$ .

Responde

Bitacoras.com

20/12/2010 13:33

Información Bitacoras.com…

Valora en Bitacoras.com: Vamos con el problema semanal. Hoy la cosa va de funciones en los naturales: Demostrar que no existe ninguna función tal que: A por él. Entra en Gaussianos si quieres hacer algún comentario sobre este artículo, consultar ……

Responde

Gulliver

20/12/2010 15:28

Generalizando más, dada $g:\mathbb{N} \to \mathbb{N}$ inyectiva, se puede encontrar una condición necesaria y suficiente para que exista $f:\mathbb{N} \to \mathbb{N}$ tal que $g = f \circ f$ .

Aplicando repetidamente $g$ a cada número natural, las órbitas producidas pueden ser finitas o infinitas. Son finitas y periódicas cuando al aplicar $n$ veces la función $g$ a un número da como resultado el mismo número. Son infinitas cuando a partir de un número $x \in \mathbb{N} \smallsetminus g(\mathbb{N})$ aplicando repetidas veces $g$ va dando como resultado números siempre diferentes. La condición necesaria y suficiente para que exista $f$ es que el número de órbitas de $g$ con la misma cardinalidad sea par.

En el caso en que $g(n) = n + 1$ , aplicando $g$ repetidamente al número 1 aparecen todos los números naturales, así que solo hay una órbita y es infinita. No se cumple la condición para que exista $f$ .

Responde

Gulliver

20/12/2010 17:27

Rectifico, dado $g: \mathbb{N} \to \mathbb{N}$ inyectiva, la condición necesaria y suficiente para que exista $f: \mathbb{N} \to \mathbb{N}$ tal que $g = f \circ f$ es que para las órbitas de $g$ con cardinalidad par o infinita el número de órbitas con la misma cardinalidad sea par o infinito.

Responde

Agus

21/12/2010 22:40

Lanzo una pregunta al ruedo aprovechando que se habla de los Naturales.
¿Consideramos el 0 dentro o fuera del conjunto?

La Wikipedia no se aclara… http://es.wikipedia.org/wiki/N%C3%BAmero_natural

Responde

Mikhe

22/12/2010 04:01

@Tito Eliatron: Muy bien, solo que al final hay una errata no??

$2(f(1) - 1) = 1 \Leftrightarrow f(1) = \frac{3}{2} \notin \mathbb{N}$

Que sigue sin pertenecer a $\mathbb{N}$ , por tanto la demostración queda intacta.

Responde

Ximena

10/01/2011 04:43

Un poco tarde, pero es que hasta ahora pude volver a leer Gaussianos…

Supongo que existe $f$ una función en los naturales tal que $f(f(n))=n+1$ , si evaluamos denuevo tenemos $f(f(f(n)))=f(n+1)$ y así la siguiente fórmula $f(n)+1=f(n+1)$ . La cual nos permite afirmar que f es creciente pues:

como $f(n+1)-f(n)=1$ entonces $f(n+1)-f(n)> 0$ , luego $f(n+1)> f(n)$ y como $n+1>n$ entonces f es estrictamente creciente!!

Por inducción es facil ver que el rango de f es {1,2,3,…}este conjunto tiene minimo el 1. Luego $f(0)=1$ (por ser f creciente) .

Así, Utilizando la fórmula de la hipótesis y $f(0)=1$ se tiene que $f(1)=f(f(0))=0+1=1$ , por otro lado con la fórmula obtenida se tiene $f(1)=f(0)+1=1+1=2$ . Luego $f(1)$ tendría dos imagenes, lo cual contradice que f sea una función.
Por lo tanto no existe tal f.

(La «demostración» es igual incluyendo el cero o no el los Naturales)

Responde

Don Ghaliza

23/01/2014 01:37

Llego a lo mismo que Tito, lo cual lo voy a repetir pero con inducción, quiero demostrar que f(n+k)=f(n)+k para k un número natural, entonces para k=1:
(1) f[f(f(n))]=f(n+1)
(2) f(f[f(n)])=f(n)+1

Obviamente, independientemente de los corchetes son lo mismo, así que:
(3) f(n+1)=f(n)+1

Lo cual se cumple. Ahora, para probar k, lo hacemos para k+1:
(4) f[f(f(n+(k+1)))]=f(n+(k+1))
(5) f(f[f(n+(k+1))])=f(n+k)+1=f[n+(k-1)]+1+1=f[n+(k-2)]+2+1=…(k veces)=f(n)+k+1=f(n)+(k+1)

Lo mismo que anterior se obtiene:
(6) f(n+(k+1))=f(n)+(k+1)

Que también se cumple, por lo que la expresión:
(7) f(n+k)=f(n)+k

Queda ciertamente demostrado. En el (3) hacemos n=0:
(8) f(1)=f(0)+1
(9) f(0)=f(1)-1

Y haciendo lo mismo que lo anterior pero también en la expresión (7):
(10) f(k)=f(0)+k
(11) f(k)=f(1)-1+k

Y cambiando de variable de k a n, queda:
(12) f(n)=f(1)+n-1

Por hipótesis f(n) es natural y como es una sucesión de una suma y una resta entonces f(1) forzosamente debe ser también natural y mayor que 0 para que no de negativo en n=0 (que en esta demostración no nos va a interesar). Entonces:
(13) f[f(n)]=f(1)+f(n)-1
(14) n+1=f(1)+f(1)+n-1-1
(15) 1=2f(1)-2
(16) 1=2(f(1)-1)
(17) f(1)-1=1/2
(18) f(1)=3/2 que no pertenece a los números naturales.

Pero dijimos que, en conclusión en (12), f(1) debería ser un número natural y nos da el resultado que precisamente no es un número natural, así que se presenta una contradicción suponiendo que la f:N->N (natural) existiera.

Ergo, esa función no existe.

Responde

Buscar

Premio Prisma 2018

Suscríbete por mail

Si quieres recibir los artículos de Gaussianos en tu mail, haz click en la imagen.

Últimas entradas

Últimos comentarios

Gaussianos en Facebook

Yo construí el poliedro de Császár

Únete a la iniciativa Yo construí el poliedro de Császár. Haz click en la imagen para conocer todo los detalles.

Y visita este set de Flickr para ver las construcciones de los lectores de Gaussianos.