This question is of course inspired by the question [How to solve f(f(x))=cosx](https://mathoverflow.net/questions/17605/how-to-solve-ffx-cosx)
and Joel David Hamkins' answer, which somehow gives a formal trick for solving equations of the form $f(f(x))=g(x)$ on a *bounded* interval. [EDIT: actually he can do rather better than this, solving the equation away from a bounded interval (with positive measure)].


I've always found such questions ("solve $f(f(x))=g(x)$") rather vague because I always suspect that solutions are highly non-unique, but here are two precise questions which presumably are both very well-known:


Q1) Say $g:\mathbf{R}\to\mathbf{R}$ is an arbitrary function. Is there always a function $f:\mathbf{R}\to\mathbf{R}$ such that $f(f(x))=g(x)$ for all $x\in\mathbf{R}$?


Q2) If $g$ is as above but also assumed continuous, is there always a continuous $f$ as above?


The reason I'm asking is that these questions are surely standard, and perhaps even easy, but I feel like I know essentially nothing about them. Apologies in advance if there is a well-known counterexample to everything. Of course Q1 has nothing to do with the real numbers; there is a version of Q1 for every cardinal and it's really a question in combinatorics.


EDIT: Sergei Ivanov has answered both of these questions, and Gabriel Benamy has raised another, which I shall append to this one because I only asked it under an hour ago:


Q3) if $g$ is now a continuous function $\mathbf{C}\to\mathbf{C}$, is there always continuous $f$ with $f(f(x))=g(x)$ for all $x\in\mathbf{C}$?


EDIT: in the comments under his answer Sergei does this one too, and even gives an example of a continuous $g$ for which no $f$, continuous or not, can exist.


Related MO questions: [f(f(x))=exp(x) and other functions just in the middle between linear and exponential](https://mathoverflow.net/questions/4347/ffxexpx-1-and-other-functions-just-in-the-middle-between-linear-and-expo), and [Does the exponential function has a square root](https://mathoverflow.net/questions/12081/does-the-exponential-function-have-a-square-root).



solving $f(f(x))=g(x)$
Q1: No. Let $g(0)=1, g(1)=0$ and $g(x)=x$ for all $x\in\mathbb R\setminus\{0,1\}$.
Assuming $f\circ f=g$, let $a=f(0)$, then $f(a)=1$ and $f(1)=g(a)=a$ since $a\notin\{0,1\}$.
Then $g(1)=f(f(1))=f(a)=1$, a contradiction.


Q2: No. Let $g(x)=-x$ or, in fact, any decreasing function $\mathbb R\to\mathbb R$. Then $f$ must be injective and hence monotone. Whether $f$ is increasing or decreasing, $f\circ f$ is increasing.


