Is every function $f : \mathbb N \to \mathbb N$ a composition $f = g\circ g$? 
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$.

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

A: 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.
A: 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!
