Does there exist a function $g\in \mathbb{N}^\mathbb{N}$ s.t. $\{f\mid f\circ f=g\}$ is not empty and finite? I'm struggling with this question and can't figure it out.
The question was too long for the title so I will write it once more:
Does there exist a function $g : \mathbb{N} \longrightarrow \mathbb{N}$ such that the set $\{f\mid f : \mathbb{N} \longrightarrow \mathbb{N} \text{ and }f\circ f=g\}$ is not empty and finite?
Thank you.
 A: $g(n)=n+2$ will do the trick.
Since this $g$ is injective, $f$ must be injective too, so under $f$ each natural number will have one successor and zero or one predecessor.
Also there are exactly two numbers that have no pre-predecessor, and that is only possible if there is exactly one number with no predecessor. There also can be no cycles in the action of $f$, because there are no cycles in the action of $g$. So the action of $f$ is fully specified by giving an enumeration of the natural numbers, and $f$ then just gives the successor of each of them.
The first two numbers in the enumeration must be the ones not hit by $g$, that is, $1$ and $2$. This makes the possible enumerations:
$$ 1,2,3,4,5,6,7,8,\ldots \quad \text{and}\quad 2,1,4,3,6,5,8,7\ldots $$
The first of these gives rise to $f(n)=n+1$, the other to
$$ f(n) = \begin{cases} n-1 & \text{for even }n \\ n+3 & \text{for odd }n \end{cases}$$
and these are the only $f$ that produce $n\mapsto n+2$ when iterated twice.
A: Don't shoot me if I'm wrong, but I think this would be a huge hint:

Let $X$ be a set. It holds that $\lvert X\rvert \leq 1$ if and only if
  for every function $f : X \to X$, there is a function $g : X\to X$
  with $f = g\circ g$.

The proof of this can be found in this link: Is every function $f : \mathbb N \to \mathbb N$ a composition $f = g\circ g$?
