Is every function $f : \mathbb N \to \mathbb N$ a composition $f = g\circ g$?

Question

True or wrong: For every function $f: \mathbb N \rightarrow \mathbb N$ there is a function $g: \mathbb N \rightarrow \mathbb N$ with $f=g \circ g$.

Answer 1

Consider the mapping $$f : \mathbb N\to\mathbb N, x\mapsto\begin{cases}1 & \text{if }x = 2 \\2 & \text{if }x = 1 \\ x & \text{ otherwise.}\end{cases}$$

Assume $g : \mathbb N\to\mathbb N$ is a mapping with $f = g\circ g$.

We have $g(1) \neq 1$, because otherwise $f(1) = g(g(1)) = g(1) = 1$.

Furthermore $g(1) \neq 2$, because otherwise $g(2) = g(g(1)) = f(1) = 2$ and thus $f(2) = g(g(2)) = g(2) = 2$.

So $y := g(1) \notin\{1,2\}$ and therefore $f(y) = y$.

We continue with $g(y) = g(g(1)) = f(1) = 2$.

It follows that $g(2) = g(g(y)) = f(y) = y$, so $$f(1) = g(g(1)) = g(y) = g(g(2)) = f(2).$$ Contradiction.

Remark

Based on the above argument, we get the following generalization:

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

Answer 2

No.

For example, take $f:\mathbb{N}\to\mathbb{N}$ to be $f(x)=\begin{cases} 2 & x=1\\ 1 & x=2\\ x & x>2\\ \end{cases}$.

Assume that there is $g:\mathbb{N}\to\mathbb{N}$ such that $f=g\circ g$.

Notice that $g(1)\neq1$ since $g(1)=1\Rightarrow f(1)=g(g(1))=g(1)=1\neq f(1)$ and similarly $g(2)\neq 2$. Also $g(1)\neq 2$ since $g(1)=2\Rightarrow f(1)=g(g(1))=g(2)\neq 2=f(1)$. From here it follows that $f(g(1))=g(1)$ because $g(1)\neq 1,2$.

We also know that $g(1)\neq g(2)$ because $g(g(1))\neq g(g(2))$.

But we also deduce that $g(1)=f(g(1))=g(g(g(1)))=g(f(1))=g(2)$, which contradicts the previous line.

Answer 3

Shay and Azimut have found the perfect counter-example, and I just want to say a word about how one might come up with such a counter-example.

Let $S_n$ be the symmetric group on $\{1, \dots, n\}$. A necessary condition for a permutation $\sigma \in S_n$ to admit a square root is that it be even: indeed, the squares of $S_n$ all lie in the kernel of the sign $S_n \to \{\pm 1\}$.

With this in mind, the permutation of $\mathbf N$ which switches $1$ and $2$ is a natural candidate for a function which has no square root. Indeed, if one could speak of its sign, it should be negative. Unfortunately, one cannot speak of the sign of an arbitrary permutation of $\mathbf N$. One can, however, speak of the sign of a permutation which is almost everywhere the identity. Permutations of $\mathbf N$ which leave almost all elements fixed form a subgroup of the group of all permutations of $\mathbf N$, which identifies with the direct limit $\mathbf S_{\infty}$ of the direct system $S_1 \to S_2 \to S_3 \to \dots$. The sign homomorphisms are compatible with the maps of the direct system, and determine a sign homomorphism $\mathbf S_{\infty} \to \{\pm 1\}$. Azimut and Shay's map is an "odd" element of $\mathbf S_{\infty}$, and therefore cannot admit a square root inside $\mathbf S_{\infty}$.

Unfortunately, this is not sufficient to see that their map admits no square root, because there are permutations of $\mathbf N$ which are not in $\mathbf S_{\infty}$, but whose square is. Thus, one still needs to argue (as they do) that their map cannot admit a square root in the bigger group $S_{\mathbf N}$. But perhaps, it is still interesting to have this source of intuition!