7 edited tags
6 added 445 characters in body; edited tags

This question is of course inspired by http://mathoverflow.net/questions/17605/how-to-solve-ffx-cosxthe 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.

5 edited tags
4 drew attention to more amazing observations of Ivanov.