# 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.

• Just thinking out loud here: what about $g: \mathbb{N} \rightarrow \mathbb{N}: n \mapsto 0$? – Riley Aug 27 '15 at 19:53
• @Riley there are continuum-many $f$ in that case: Map any subset $A$ of $\mathbb N$ to $0$, map the rest somewhere into $A$. – Hagen von Eitzen Aug 27 '15 at 19:54
• Dang. Too good to be true. – Riley Aug 27 '15 at 19:55
• @Riley actually by $\mathbb{N}$ I meant $\mathbb{N}_+$ so $0$ is not in the values of the image of $g$ but for any $n\in \mathbb{N}_+$ if you will take the function $g$ to be $g(i)=n$ for any $i$ then the above set would be infinite – dorsh605 Aug 27 '15 at 19:56
• @dorsh605 It doesn't matter if you consider $0$ as a natural number or not. $\mathbb{N}$ could be exchanged with any countably infinite set. – Dominik Aug 27 '15 at 19:59

$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.

• Beat me to it: I was just investigating $n\mapsto n+2$! – Brian M. Scott Aug 27 '15 at 20:08
• @Henning Makholm Thanks! would this example work if we change it from $g(n)=n+2$ to $g(n)=n+i$ for any $i>1$? – dorsh605 Aug 27 '15 at 20:25
• @dorsh605: If $i$ is odd, then there is no possible $f$, but with $i=2k\ge 2$, the analysis here results in $(2k)!/k!$ different solutions. – hmakholm left over Monica Aug 27 '15 at 20:34
• @HenningMakholm Got it. Thanks again. – dorsh605 Aug 27 '15 at 20:36

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$?