# 3rd iterate of a continuous function equals identity function

If $f: \mathbb{R} \to \mathbb{R}$ is continuous, and $\forall x \in \mathbb{R} :\;(f \circ f \circ f)(x) = x$, show that $f(x) = x$.

The condition that $f$ is continuous on $\mathbb{R}$ is crucial for the proof. I can find functions such as $\displaystyle\frac{x-3}{x+1}$ that satisfies $(f \circ f \circ f)(x) = x$.
I have tried to negate the conclusion to see if there's a contradiction, but got stuck.

-
might be generalised to $f(x)=\frac{x+b}{x+a}$, with $a^2+a+(1+b)=0$ and $a+1\neq 0$. See here. – draks ... Feb 28 '12 at 11:48
Possibly relevant nitpick: $(x-3)/(x+1)$ isn't a function $\mathbb{R} \to \mathbb{R}$ – Hurkyl Feb 28 '12 at 15:04
I suppose you can remedy that issue by extending it to send $-1 \to -1$. – Hurkyl Feb 28 '12 at 15:13

Pick any $x$ and look at the three numbers $x,f(x),f(f(x))$. If any two of them are equal, then they are all equal by applying $f$ and using $f \circ f \circ f = id$, and so $x = f(x) = f(f(x))$.

So suppose they are distinct. Without loss of generality, you can assume $x$ to be between $f(x)$ and $f(f(x))$ (if it's not, pick $f(x)$ or $f(f(x))$ in place of $x$). Then, by the intermediate value theorem, there exist a number $y$ between $x$ and $f(x)$ such that $f(y) = x$. Then, $y = f(f(f(y))) = f(f(x))$, which is impossible because $f(f(x))$ cannot be between $x$ and $f(x)$ ($x$ is between the other two)

-
Nice you did not used the whole continuity, but only the intermediate value theorem which holds for derivatives. – checkmath Feb 28 '12 at 13:25
Hi, this solution is really interesting. Thank you. – Geralt of Rivia Feb 28 '12 at 14:02

First note that $f$ must be either increasing or decreasing by the intermediate value theorem, as if $f(x)=f(y)$ then $x=f(f(f(x)))=f(f(f(y)))=y$. Suppose $f$ is increasing. Suppose we have some $a\in\mathbb R,\epsilon_1>0$ such that $f(x)>x$ for all $x\in(a,a+\epsilon_1)$. Pick some $0<\epsilon_2<\epsilon_1$ such that $f(x)\in (a,a+\epsilon_1)$ for all $x\in (a,a+\epsilon_2)$, which must exist as $\lim\limits_{\epsilon_2\to 0^+}f(a+\epsilon_2)-(a+\epsilon_2)=0$ and for $\epsilon_2<\epsilon_1$ the expression in the limit is positive. Do the same for $0<e_3<e_2$ such that $f(x)\in (a+\epsilon_2)$ for $x\in (a,a+\epsilon_3)$. Then $$a+\epsilon_3/2=f(f(f(a+\epsilon_3/2)))>f(f(a+\epsilon_3/2))>f(a+\epsilon_3/2)>a+\epsilon_3/2$$ which is a contradiction. The same can be done if we have $f(x)<x$ for $x\in (a,a+\epsilon_1)$, so $f(x)-x$ cannot be positive or negative on any open interval, hence by continuity it cannot be positive or negative anywhere in $\mathbb R$ by continuity, hence $f(x)=x$ for all $x$. To conclude, we note that $f$ cannot be decreasing, as the same procedure gives us $f(x)=-x$ for all $x$, so $f(f(f(x)))=-x\neq x$.

-
thank you for the hint. – Geralt of Rivia Feb 28 '12 at 14:01
After assuming that f is increasing (strictly), if there is x such that f(x)>x we can have the immediate contradiction: f(f(x))>f(x) and x=f(f(f(x))) > f(f(x)) > f(x) > x just by the fact that f(x) is increasing. (Same for f(x)<x). – Geralt of Rivia Feb 28 '12 at 17:17

Let's consider the case of the circle. Your example, continuously extended to the projective line (i.e. the circle) by $f(-1) = \infty$ and $f(\infty) = 1$ really is a continuous function satisfying $f(f(f(x))) = x$.

Let $f$ be any continuous function of the circle satisfying $f(f(f(x))) = x$ but not $f(x) = x$ identically. Suppose $a$ is not a fixed point. Then, $a$, $b = f(a)$, and $c = f(b)$ are three different points.

Since $f$ is continuous and invertible, I claim that it must send the directed arc $ab$ (the one that doesn't pass through $c$) to the directed arc $bc$, and also $bc \mapsto ca$ and $ca \mapsto ab$.

I assert that every continuous function on the circle satisfying $f(f(f(x))) = x$ identically that is not $f(x) = x$ is of the above form. Conversely, any choice of $a, b, c$ and choice of invertible orientation preserving maps $ab \mapsto bc$ and $bc \to ca$ has this property.

In particular, each such function has no fixed points.

Now, back to the line. If $f$ is a continuous function satisfying $f(f(f(x))) = x$, then it is invertible, and we can extend it to a continuous function of the circle by $f(\infty) = \infty$. This also satisfies $f(f(f(x))) = x$ and has a fixed point -- therefore $f$ satisfies $f(x) = x$.

In the end, it's probably the same underlying idea as mercio had, but I still thought it interesting to treat the circle anyways.

-

Alex Becker's solution is close to what i was working on:

Suppose there is $a \in \mathbb{R}$ such that f(a) > a. Consider the continuous function g(x) = f(x) -x, we have g(a)>0.
$\forall \epsilon, \exists \delta: \left | x -a \right |<\delta, \left |g(x)-g(a) \right |<\epsilon$. Choose $\epsilon = g(a)$ then we have $g(x)>0$ or $f(x)>x$ on $(a-\delta, a+\delta)$.
$a+ \delta/2 = f(f(f(a+ \delta/2)))>f(f(a+ \delta/2))>f(a+ \delta/2)>a+ \delta/2$ which is a contradiction.
The case f(a) < a is similar
Therefore, $\forall x \in \mathbb{R}, f(x) = x$
Edit: i think i need to prove that f(x) is increasing first!

-