This question is of course inspired by the question How to solve f(f(x))=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, and Does the exponential function has a square root.

g(x) =x*<sup>2</sup>, then *f(x) =x*<sup>sqrt(2)</sup>. But what if *g(x) = *x*<sup>2</sup> - 1? I can't think of a function that would satisfy Q1. $\endgroup$ – Gabriel Benamy Mar 9 '10 at 16:234more comments