¿Existe una función $g\in \mathbb{N}^\mathbb{N}$ s.t. $\{f\mid f\circ f=g\}$ no es vacío y finito?

Question

Estoy luchando con esta pregunta y no puedo resolverla. La pregunta era demasiado larga para el título, así que la escribiré una vez más:

¿Existe una función $g : \mathbb{N} \longrightarrow \mathbb{N}$ tal que el conjunto $\{f\mid f : \mathbb{N} \longrightarrow \mathbb{N} \text{ and }f\circ f=g\}$ no es vacío y finito?

Gracias.

Answer 1

$g(n)=n+2$ hará el truco.

Dado que este $g$ es inyectiva, $f$ debe ser también inyectiva, por lo que bajo $f$ cada número natural tendrá un sucesor y cero o un predecesor.

También hay exactamente dos números que no tienen predecesor, y eso sólo es posible si hay exactamente un número sin predecesor. Tampoco puede haber ciclos en la acción de $f$ porque no hay ciclos en la acción de $g$ . Así que la acción de $f$ se especifica completamente dando una enumeración de los números naturales, y $f$ entonces sólo da el sucesor de cada uno de ellos.

El los dos primeros los números de la enumeración deben ser los que no han sido alcanzados por $g$ Es decir, $1$ y $2$ . Esto hace que las posibles enumeraciones:

$$ 1,2,3,4,5,6,7,8,\ldots \quad \text{and}\quad 2,1,4,3,6,5,8,7\ldots $$ El primero de ellos da lugar a $f(n)=n+1$ el otro a $$ f(n) = \begin{cases} n-1 & \text{for even }n \\ n+3 & \text{for odd }n \end{cases}$$ y estos son los únicos $f$ que producen $n\mapsto n+2$ cuando se itera dos veces.

Answer 2

No me disparen si me equivoco, pero creo que esto sería una gran pista:

Dejemos que $X$ sea un conjunto. Se sostiene que $\lvert X\rvert \leq 1$ si y sólo si para toda función $f : X \to X$ existe una función $g : X\to X$ con $f = g\circ g$ .

La prueba de ello se encuentra en este enlace: ¿Es cada función $f : \mathbb N \to \mathbb N$ una composición $f = g\circ g$ ?