Proof regarding a fixed point

Question

Show that for any strictly increasing function $f:[0,1]\to[0,1]$ there is a fixed point such that $f(x)=x$. ( The function isn't necessarily continuous) .

Any ideas ?

Answer 1

If $f(x)=x$ for some $x<1,$ then we're done. Suppose not. Note that $0<f(0).$ (Why?) Since $f$ is monotone non-decreasing on $[0,1]$, then for every $x_0\in(0,1],$ we have that $\lim_{x\to x_0^-}f(x)$ exists--namely, it is the least upper bound of the set $\{f(x):0<x<x_0\}$--and moreover $$\lim_{x\to x_0^-}f(x)\le f(x_0)\le 1\tag{$\star$}$$ for any such $x_0.$ (Why?)

I claim that $x<f(x)$ for every $x\in[0,1).$ It follows from this and from $(\star)$ that $f(1)=1.$ (Do you see why?) Let me give an outline of a proof of my claim, with some fairly straightforward gaps to fill in.

We've already seen that $0<f(0),$ so it remains to show that $x<f(x)$ for all $0<x<1.$ Consider the set $$E=\Bigl\{x\in(0,1]:t<f(t)\text{ for all }t\in(0,x)\Bigr\}.$$ Now, $0<f(0),$ so for all $x\in\bigl(0,f(0)\bigr),$ we have $x<f(x).$ (Why?) Hence, $E$ is non-empty. Furthermore, given any $x'\in E$ and any $x\in(0,x'),$ we have $x\in E.$ (Why?) Hence, $E$ is an interval, necessarily of the form $(0,b)$ or $(0,b]$ for some $0<b\le1.$ (Why?)

Take any $0<x_0<b.$ Since $x_0\in E,$ by assumption, then $x<f(x)$ for all $0<x<x_0.$ Thus, taking the limit as $x\to x_0^-$ in the inequality $x<f(x)<f(x_0)$ (do you see why the second part of the inequality holds?), we have by the first part of $(\star)$ that $$x_0\le\lim_{x\to x_0^-}f(x)\le f(x_0).$$ But $x_0<1,$ so by assumption, $f(x_0)\ne x_0,$ and so $x_0<f(x_0).$ Since $x_0\in(0,b)$ was arbitrary, then $x<f(x)$ for all $x\in(0,b),$ and so $b\in E$ by definition of $E.$ Thus, $E=(0,b].$ It remains only to show that $b=1.$

By way of contradiction, suppose not, so that $E=(0,b]$ for some $0<b<1.$ Now, since $x<f(x)$ for all $x\in(0,b)$ by definition of $E,$ then $(\star)$ allows us (through similar work to the above) to conclude that $b<f(b).$

By definition of $E,$ given $x\in(b,1],$ there is some $t\in(b,x)$ such that $f(t)\le t.$ (Why?) Consequently, for all $\epsilon>0,$ there is some $t\in(b,b+\epsilon)$ such that $f(t)\le t.$ (Why?) In other words, $b$ is a limit point of the set of all $t\in[0,1]$ such that $f(t)\le t,$ and is necessarily less than all such $t$ by the work above, meaning in particular that $b$ is the greatest lower bound of the set of all such $t$ (why?)--let's call this set $F.$ Let $y_0$ be the greatest lower bound of the set $\bigl\{f(t):t\in F\}.$ Then $$y_0\le f(t)\le t$$ for all $t\in F,$ and so $y_0$ is a lower bound for $F.$ Since $b$ is the greatest lower bound of $F,$ then $y_0\le b<f(b).$ Since $y_0$ is the greatest lower bound of $\bigl\{f(t):t\in F\},$ then $f(b)$ is not a lower bound of that set, so there is some $t\in F$ such that $f(t)<f(b).$ But $0<b<t\le1,$ and $f$ is monotone non-decreasing on $[0,1],$ so $f(b)\le f(t).$ Thus, we have the desired contradiction.

---

There are several gaps to fill in, here, as I pointed out. Please let me know if there are any that you're unable to fill in, and I'll see if I can get you "unstuck" when I have a moment.

To provide some intuition for the claim I made, recall/observe that $f$ has only jump discontinuities (if any). So, the idea is that $f(x)$ starts out greater than $x.$ As we move to the right in the interval, $f(x)$ and $x$ continue to increase. Eventually, $x$ may "catch up" to $f(x)$--that is, there might be some $x_0$ such that $\lim_{x\to x_0^-}f(x)=x_0$--but if this happens, then $x_0\le f(x_0)$ by $(\star)$ and $f(x_0)\ne x_0$ by assumption, so $x_0<f(x_0).$ Another potential worry is that $x$ may suddenly "pass" $f(x)$--that is, there might be some $x_0$ such that $\lim_{x\to x_0^-}f(x)>x_0$ and yet $f(x_0)<x_0$--but this is actually impossible by $(\star),$ so we don't have to worry about that.

So, the upshot is, any time $x$ "catches up" to $f(x),$ $f(x)$ will "jump ahead" to prevent an actual meeting...until finally (when $x=1$), there's nowhere else to jump to, and $x$ catches $f(x)$ at last.

Answer 2

Suppose $f(0)>0$, and let $x_0:=\sup\{x\in[0,1]|f(x)>x\}$. If $f(x_0)=x_0$, we're good. If $f(x_0)>x_0$, let $\delta:=f(x_0)-x_0$, and it follows from $f$ being increasing that for any $x_0<x<x_0+\delta$, $f(x)>x$, a contradiction to $x_0$ being an upper bound. If $f(x_0)<x_0$, a similar argument shows that for some $\delta$, for any $x_0-\delta<x<x_0,\;f(x)<x$, in contradiction to $x_0$ being the least upper bound.

Answer 3

You don't need a strictly increasing function, just a function $f:[0,1]\to[0,1]$ which is nondecreasing, i.e., $x\le y\Rightarrow f(x)\le f(y)$.

Let $A=\{x\in[0,1]:x\le f(x)\}$ and let $a=\sup A$; I claim that $f(a)=a$.

If $x\le f(x)$ then $f(x)\le f(f(x))$, that is,

(1) $x\in A\Rightarrow f(x)\in A$.

If $x\in A$, then $x\le\sup A=a$ and $x\le f(x)\le f(a)$, showing that $f(a)$ is an upper bound for $A$, so $f(a)\ge\sup A$, that is,

(2) $a\le f(a)$,

in other words,

(3) $a\in A$.

From (3) and (1) it follows that

(4) $f(a)\in A$,

so $f(a)\le\sup A=a\le f(a)$, so $f(a)=a$, Q.E.D.