Función de los naturales en los naturales

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. 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}

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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}) .

    Publica una respuesta
  4. 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 .

    Publica una respuesta
  5. 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.

    Publica una respuesta
  6. @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.

    Publica una respuesta
  7. 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 tienef(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)

    Publica una respuesta
  8. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Tweets that mention Función de los naturales en los naturales | Gaussianos -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos. gaussianos said: Gaussianos.com: Función de los naturales en los naturales http://bit.ly/gPdNMD…
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Vamos con el problema semanal. Hoy la cosa va de funciones en los naturales:…

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.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *