# Prove that $f(\mathbb R) = \mathbb R$. Partially solved.

Let $$f:\mathbb R\to \mathbb R$$ and $$f(f(x)) = x + f(x)$$, $$x\in\mathbb R$$

Prove that:
a) $$f$$ is injective

b) $$f(0) = 0$$

c) $$f(\mathbb R) = \mathbb R$$

My solution:

a) Let $$x_1, x_2 \in \mathbb R$$ and $$f(x_1) = f(x_2)$$ then

$$f(f(x_1)) = f(f(x_2))$$

$$x_1 + f(x_1) = x_2 + f(x_2)$$

$$x_1 = x_2$$ therefore $$f$$ is injective.

b) Let $$x=0$$ then $$f(f(x)) = x + f(x)$$

$$f(f(0)) = 0 + f(0)$$

$$f(f(0)) = f(0)$$ but $$f$$ is injective therefore

$$f(0) = 0$$

c) Here is the point where I get stuck. How do I solve this?

I think I have to begin saying, let $$y\in\mathbb R$$ and prove that there is a $$x\in\mathbb R$$ for which $$f(x) = y$$.

• I am not giving the answer, it is just a doubt clearing.If I consider an identity mapping i.e. $f(x)=x$, then we have $f(x)=x+x\implies x=2x\implies x=0$....., does this solution hold for the second question?
– user249332
Sep 8, 2015 at 21:41
• take an arbitrary $y \in \mathbb{R}$ and show that there exists an $x \in \mathbb{R}$ so that $f(x)=y$ so the image of $f$ is the whole $\mathbb{R}$. Probably some reduction ad absurdum (mprr...) will be needed Sep 8, 2015 at 21:41
• If we could show that $f$ is additive, then $x=f(f(x))-f(x)=f(f(x)-x)$. -- And you didn't forget an important condition such as continuity, did you? (That would trvialize part c as $f$ is unbounded) Sep 8, 2015 at 21:41
• Two solutions for $f$ are $f(x)=kx$ where $k^2 =k+1$. These are the only polynomial solutions for $f$. Are there others? Sep 8, 2015 at 23:24
• A remark: By induction, $f^{\circ n}(x)=F_nf(x)+F_{n-1}x$ for $n\ge 0$ ($F_n$ the Fibonacci numbers) Sep 9, 2015 at 6:04

[Note: There have been some important technical revisions since the first version of this answer, which was flawed.]

I realize this is quite old and everyone has likely moved on, but since it got bumped, let me point out that without a continuity assumption or some other additional constraint, this claim is false, i.e., $$f$$ need not be surjective.

One can construct a counterexample as follows. $$\newcommand{\span}{\operatorname{span}}$$

Let $$\mathfrak c=2^{\aleph_0}$$ be the cardinality of $$\mathbb R$$. Let $$\alpha\mapsto r_\alpha$$ be a bijection $$\mathfrak c\to \mathbb R$$, with $$r_0=0$$. Finally, let $$\{b_\alpha\mid \alpha\in \mathfrak c\}$$ be a basis for $$\mathbb R$$ as a vector space over $$\mathbb Q$$, with $$b_0=1$$, such that* for each $$\alpha\in\mathfrak c$$, $$\span(\{b_\beta\mid \beta\leq \alpha\})\supseteq \{r_\beta\mid \beta\leq \alpha\}.$$

We claim that for each $$\alpha\in\mathfrak c$$ there are sets $$D_\alpha\subseteq \mathbb R$$ and maps $$f_\alpha\colon D_\alpha\to D_\alpha$$ such that

1. $$\span(\{b_\beta\mid \beta\leq \alpha\})\supseteq D_\alpha\supseteq \{r_\beta\mid \beta\leq \alpha\}$$.
2. $$f_\alpha(f_\alpha(x))=x+f_\alpha(x)$$, for all $$x\in D_\alpha$$.
3. For $$\beta<\alpha$$, we have $$D_\beta\subseteq D_\alpha$$, and $$f_\alpha|_{D_\beta}=f_\beta$$.
4. $$f_\alpha(D_\alpha)\cap \mathbb Q = \{0\}$$.

This claim follows from transfinite recursion, as we can define $$D_0=\{0\}$$, $$f_0(0)=0$$, and then having defined $$D_\beta$$ and $$f_\beta$$ for each $$\beta<\alpha$$, we define $$D_\alpha$$ and $$f_\alpha$$ as follows:

If $$r_\alpha\in D_\beta$$ for some $$\beta<\alpha$$, then define $$D_\alpha=\bigcup_{\beta<\alpha}D_\beta$$ and $$f_\alpha(x)=f_\beta(x)$$ for $$x\in D_\beta$$ (this is well-defined by condition 3.)

If $$r_\alpha\notin \bigcup_{\beta<\alpha}D_\beta$$, then if the $$b_\alpha$$ coefficient of $$r_\alpha$$ is $$0$$, define $$f_\alpha(r_\alpha)=b_\alpha$$, and otherwise define instead $$f_\alpha(r_\alpha)=2r_\alpha$$. Recursively define $$f_\alpha^{k+2}(r_\alpha)=f^k(r_\alpha)+f^{k+1}(r_\alpha)$$ for each $$k\in \mathbb N$$. Crucially, the values in this sequence are distinct (otherwise our definition would be invalid), since in the former case $$r_\alpha$$ and $$b_\alpha$$ are independent, and in the latter case the sequence (a truncated rescaling of the Fibonacci sequence) is strictly monotone.

Now the $$b_\alpha$$ coefficient of each $$f^k_\alpha(r_\alpha)$$ (with $$k\geq 1$$) is nonzero, and by assumption $$f_\alpha^0(r_\alpha)=r_\alpha\notin \bigcup_{\beta<\alpha}D_\beta$$. Therefore $$\{f^k_\alpha(r_\alpha)\mid k\in \mathbb N\}\cap \bigcup_{\beta<\alpha}D_\beta=\emptyset,$$ so that we may extend $$f_\alpha$$ to $$D_\alpha:= \{f^k_\alpha(r_\alpha)\mid k\in \mathbb N\}\cup \bigcup_{\beta<\alpha}D_\beta,$$ defining as before $$f_\alpha(x)=f_\beta(x)$$ for $$x\in D_\beta$$.

The satisfaction of each of the four properties is immediate from the construction.

But then from property 1, we have $$\bigcup_{\alpha\in \mathfrak c}D_\alpha=\mathbb R$$, and so we may define $$f\colon \mathbb R\to \mathbb R$$ by $$f(x)=f_\alpha(x)$$ for $$x\in D_\alpha$$. This is well-defined by property 3, and satisfies $$f(f(x))=x+f(x)$$ by property 2, yet fails to be surjective by property 4.

#### *Remark

To see that there is such a basis, note we can define the basis via transfinite recursion, letting $$b_0=1$$ and having defined $$b_\beta$$ for $$\beta<\alpha\in\mathfrak c$$, letting $$b_\alpha=r_\gamma$$, where $$\gamma$$ is the first ordinal such that $$r_\gamma\notin \span(\{b_\beta\mid \beta<\alpha\})$$ (there will always be such a $$\gamma$$, since $$\{b_\beta\mid \beta<\alpha\}$$ has cardinality smaller than $$\mathfrak c$$ and thus cannot span $$\mathbb R$$).

It then follows from transfinite induction that $$r_\alpha\in \span(\{b_\beta\mid \beta\leq\alpha\})$$ for each $$\alpha$$, which is equivalent to the desired property that $$\span(\{b_\beta\mid \beta\leq\alpha\})\supseteq\{r_\beta\mid\beta\leq\alpha\}$$.

It works if you assume $f(x)$ is continuous.

Claim: Suppose $f(x)$ is continuous and $f(f(x)) = x + f(x)$ for all $x \in \mathbb{R}$. Then $f(\mathbb{R})=\mathbb{R}$.

Proof: We already know that $f(0)=0$ and $f(x)$ is injective. It follows that $f(1)\neq 0$.

-Case 1: Suppose $f(1)>0$. Then (by the intermediate value theorem) we must have: \begin{align} &f(x) > 0 \: \: \mbox{ if $x >0$} \\ &f(x) < 0 \: \: \mbox{ if $x<0$} \end{align}

For all positive integers $n$ we have: \begin{align*} &f(f(n)) = n + f(n) \geq n\\ &f(f(-n)) = -n + f(-n) \leq -n \end{align*} and so $f$ takes arbitrarily large values and arbitrarily small values. By the intermediate value theorem, it must take all values in $\mathbb{R}$.

-Case 2: Suppose $f(1)<0$. Then we must have:

\begin{align} &f(x) < 0 \quad \mbox{ whenever $x >0$} \\ &f(x) > 0 \quad \mbox{ whenever $x<0$} \end{align}

Suppose there is a finite constant $-M$ such that $f(x) \in [-M,0]$ for all $x\geq 0$ (we reach a contradiction). Then the infinite sequence $\{f(n)\}_{n=1}^{\infty}$ is in the compact interval $[-M,0]$, so the Bolzano-Wierstrass theorem ensures there is a subsequence $n_k$ such that $n_k\rightarrow\infty$ and $f(n_k) \rightarrow x^*$ for some $x^* \in [-M,0]$. But for all $k$ we have: $$f(f(n_k)) = n_k + f(n_k)$$ and taking a limit as $k\rightarrow \infty$ gives $f(x^*) = \infty + x^*$, a contradiction. Thus, $f(x)$ takes arbitrarily small values over $x\geq 0$.

A similar argument shows $f(x)$ takes arbitrarily large values over $x \leq 0$. Hence, by continuity, $f(\mathbb{R}) = \mathbb{R}$.

• Case 2 can only occur if $f(x)=-\frac1\phi x$: By induction $f^{\circ n}(x_0)=F_nf(x_0)+F_{n-1}x_0$, so $\frac1{F_{n-1}}f^{\circ n}(x_0)=\frac{F_n}{F_{n-1}}f(x_0)+x_0\to \phi f(x_0)+x_0\ne 0$ if we pick $x_0$ with $f(x_0)\ne -\frac1\phi x_0$. Hence for large $n$, the numbers $x:=f^{\circ n}(x_0)$ and $f(x)$ have the same sign. For continuous injective $f$ with $f(0)=0$ this means $\operatorname{sgn}f(x)=\operatorname{sgn}x$ for all $x$. Sep 10, 2015 at 5:49
• To continue my previous comment: Assume $\operatorname{sgn}f(x)=\operatorname{sgn} x$ (e.g., $f$ continiuous and not $x\mapsto -\frac1\phi x$). Then $\lim \frac 1{F_{n-1}}f^{\circ n}(x)=\phi f(x)+x$has the same sign as $x$, so that $f$ is not bounded from below and not bounded from above. Sep 10, 2015 at 6:01
• @HagenvonEitzen : Nice observation about Fibonacci. I assume you mean $\phi = \frac{1+\sqrt{5}}{2}$. So if $f(1)<0$ and $f$ is continuous, then $f(x) = (-1/\phi)x$. Sep 11, 2015 at 17:26

The solution (given by my teacher).

Let $y\in \mathbb R$ I'll prove that there is a $x \in \mathbb R$ for which $f(x) = y$

$f(x) = y$

$f(f(x)) = f(y)$

$x + f(x) = f(y)$

$x + y = f(y)$

$x = f(y) - y$

therefore $f(\mathbb R) = \mathbb R$

• Can you do these steps in reverse, or did you actually need to start with $f(x)=y$? Because starting with $f(x)=y$ seems to be assuming what you want to prove.
– Ian
Sep 9, 2015 at 15:25
• You want to prove the existence of $x$ for which $f(x) = y$ is valid. Therefore you take $f(x) = y$ for granted and prove that it actually has a solution, which is $f(y) - y$. I think that this is the logic, I remind you, it isn't my solution but my teacher's. Sep 9, 2015 at 15:30
• As we were discussing in the comments yesterday, this is really "scratch work", rather than a proof. By that I mean that you started with what you want and you reverse engineered a setup in which it should work. But then you need to start from your setup and prove that it does what you want. So this amounts to running through your steps in reverse, but not using any step in which you replace $f(x)$ by $y$ or vice versa. And doing that I run into trouble (but maybe I did some algebra wrong).
– Ian
Sep 9, 2015 at 15:36
• That just shows that if there is an $x$ such that $f(x) = y$, then $x=f(y) -y$. The same working may work in reverse though, to prove if $x = f(y) - y$, then $f(x) = y$. Sep 9, 2015 at 15:36
• My algebra: $x=f(y)-y$ so $x+f(x)=f(y)-y+f(x)$ so $f(f(x))=f(y)-y+f(x)$. But now what? This is still consistent with $f(x)=y$ (if you plug that in you get $f(y)=f(y)$), but it does not show why that must occur.
– Ian
Sep 9, 2015 at 15:40