Show that there are no functions $f: \mathbb R \to \mathbb R$ which have the intermediate value property and $f(f(x))=\cos^2(x)$ Show that there are no functions $f: \mathbb R \to \mathbb R$ which have the Darboux property (the intermediate value property) and $f(f(x))=\cos^2(x) ; \  \forall \ x\in \mathbb R$.
I guess that I'd have to use the fact that $f(f(x)) \in [0,1]$, but I'm not sure how
 A: ok so i took this with me on easter and found a proof. i'll post more details later, first only a few hints to get you started. as you already found out, $f|_{[0,\frac{\pi}{2}]}$ is injective; actually, for each $n\in\mathbb{Z}$, $f|_{[n\frac{\pi}{2},(n+1)\frac{\pi}{2}]}$ is injective. using the IVP, show that each $f|_{[n\frac{\pi}{2},(n+1)\frac{\pi}{2}]}$ is continuous, hence $f$ must be continuous everywhere. show that without loss of generality we can assume $f\ge0$ and $f(-x)=f(x)$. show $f$ is periodic with period $\pi$ (so $f$ attains its maximum and minimum at the endpoints of each $[n\frac{\pi}{2},(n+1)\frac{\pi}{2}]$) and a few more things to derive a contradiction using $x=0$ and $x=\frac{\pi}{2}$. you may or may not need the fact that $f$ has exactly one fixed point $x^*$, and $x^*\in(0,1)$, and $x^*$ is also a fixed point of $\cos^2(x)$
EDIT
A solution is a function that satisfies andreea's problem (we want to prove that no such exists). Let $f$ denote any solution, unless stated otherwise. IVP stands for intermediate value property, and monotone refers to either monotonically increasing or monotonically decreasing.

Lemma 1 Let $J$ be any set, $I\subseteq J$ any subset, and $f:J\rightarrow J$ any function. Then 
$$(f\circ f)|_I \quad \text{is injective} \quad \Longrightarrow \quad f|_I \quad \text{is injective.}$$
Proof Suppose $(f\circ f)|_I$ is injective, $x,y\in I$, and $f(x)=f(y)$. Then $f(f(x))=f(f(y))$, hence $x=y$.

Take $J=\mathbb{R}$, $n\in\mathbb{Z}$, $I=[n\frac{\pi}2,(n+1)\frac{\pi}2]$. Since $f\circ f=\cos^2$ and $\cos^2|_{[n\frac{\pi}2,(n+1)\frac{\pi}2]}$ is injective, this yields:

Proposition 1  $f|_{[n\frac{\pi}2,(n+1)\frac{\pi}2]}$ is injective.

$\quad$

Proposition 2  $f|_{[n\frac{\pi}2,(n+1)\frac{\pi}2]}$ is strictly monotone.
Proof Suppose $f(n\frac{\pi}2)<f((n+1)\frac{\pi}2)$. We'll show that $f|_{[n\frac{\pi}2,(n+1)\frac{\pi}2]}$ is strictly monotonically increasing.
Take $x,y\in(n\frac{\pi}2,(n+1)\frac{\pi}2)$ such that $x<y$. Suppose $f(x)>f(y)$. Note that
  $$ f(x)>\max\{f(n\frac{\pi}2),f(y)\}\quad\text{or}\quad f(y)<\min\{f(x),f((n+1)\frac{\pi}2)\} $$
  where the left equality holds whenever $f(n\frac{\pi}2)<f(x)$, and the right one whenever $f(y)<f((n+1)\frac{\pi}2)$ (there's some overlap, but this has no influence on the proof). In the 'left' case, by the IVP, $f$ must touch $\max\{f(n\frac{\pi}2),f(y)\}$ at least twice on $[n\frac{\pi}2,y]$, in contradiction to injectivity. In the 'right' case, the same applies to $\min\{f(x),f((n+1)\frac{\pi}2)\}$. Hence necessarily $f(x)<f(y)$.
Analogously, if $f(n\frac{\pi}2)>f((n+1)\frac{\pi}2)$ then $f|_{[n\frac{\pi}2,(n+1)\frac{\pi}2]}$ is strictly monotonically decreasing.

$\quad$

Lemma 2 Let $a,b\in\mathbb{R}$, and $f:[a,b]\rightarrow\mathbb{R}$ be a strictly monotone function with the IVP. Then $f$ is continuous.
Proof Without loss of generality, assume $f$ is increasing; otherwise take $-f$, since 'taking the negative' doesn't influence continuity. Choose $x\in[a,b]$ and $\epsilon>0$. Note that, by the IVP, there exist $x_-,x_+\in[a,b]$ such that
  $$ f(x_-)=\min\{f(x)-\epsilon, f(a)\} \quad \text{and} \quad f(x_+)=\min\{f(x)+\epsilon, f(b)\}$$
  Set $\delta=\min\{|x-x_-|,|x-x_+|\}\backslash\{0\}$ (i.e. we ignore the $x_-$ or $x_+$ term if $x_-=f(a)$ or $x_+=f(b)$, respectively). Then, for any $y\in(x-\delta,x+\delta)\cap[a,b]$, by monotonicity,
  $$ f(x_-)\le f(y)\le f(x_+) $$
  hence
  $$ f(x)-\epsilon<f(y)<f(x)+\epsilon\text. $$

Take $a=n\frac{\pi}2$, $b=(n+1)\frac{\pi}2$. Then $f|_{[n\frac{\pi}2,(n+1)\frac{\pi}2]}$ is continuous. In particular, $f(x)$ is both left continuous and right continuous at $x=n\frac{\pi}2$, for any $n\in\mathbb{Z}$, and we get:

Proposition 3 $f$ is continuous.

Note that, for any $x\in\mathbb{R}$,
$$
f(\cos^2(x)) = \cos^2(f(x)) \in [0,1]
$$
Thus we can define the (continuous) function $\tilde f:\mathbb{R}\rightarrow[0,\pi]$ by
$$
\tilde f(x)=\arccos\sqrt{f(\cos^2(x))}
$$
It is easy to see that $g$ is also a solution:
$$
\tilde f(\tilde f(x)) = \arccos\sqrt{f(\cos^2(\arccos\sqrt{f(\cos^2(x))}))}
\\ = \arccos\sqrt{f(f(\cos^2(x)))}
\\ = \arccos\sqrt{\cos^2(\cos^2(x))}
\\ = \cos^2(x)
$$
Without loss of generality, assume henceforth that $f=\tilde f$. This gives:

Proposition 4 
  
  
*
  
*$f$ is nonnegative
  
*$f$ is even
  
*$f$ is periodic with period $\pi$.
  

Note that $f(f(\frac{\pi}2))=0$, so $0\in\operatorname{im}f$ ; by periodicity and monotonicity, $f$ attains the value $0$ at one endpoint of each interval $[n\frac{\pi}2,(n+1)\frac{\pi}2]$. Focusing on the interval $[0,\frac{\pi}2]$, we have two cases:


*

*$f(0)=0$, or

*$f(\frac{\pi}2)=0$


If (1.), then
$$
0 = f(0) = f(f(0)) = \cos^2(0) = 1 \text;
$$
if (2.), then
$$
0 < f(0) = f(f(\frac{\pi}2)) = \cos^2(\frac{\pi}2) = 0 \text;
$$
both contradictions. We conclude that no such $f$ exists.
