Prove f has a fixed point if it is increasing but not necessarily continuous

Suppose $$f : [0, 1] \rightarrow [0, 1]$$ is increasing (but not necessarily continuous). Show that there is a number $$x \in [0, 1]$$ with $$f(x) = x$$. (Hint: You can’t apply the IVT directly because the function need not be continuous. Draw a picture and try to copy the proof of the Intermediate Value Theorem.)

I don't understand how copying the IVT and connecting it to my graph would help me prove this since the IVT has nothing to do with increasing functions(or am I wrong about this?)

• What have you tried so far? – dfnu Jan 27 '19 at 15:44
• I tried copying the IVT but could not connect it with an increasing function – user634512 Jan 27 '19 at 15:46
• I think you can apply squeeze theorem after doing binary search – Mark Jan 27 '19 at 15:47
• For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken. – dfnu Jan 27 '19 at 15:54
• @Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know. – Clement C. Jan 27 '19 at 16:10

Start by defining the sequences $$l_n, u_n$$, where the variable names stand for "lower" and "upper". And let $$x_n \equiv (l_n + u_n)/2$$.

$$l_0 \equiv 0, u_0 \equiv 1$$

Now inductively define $$l_k, u_k$$:
If $$f(x_{k-1}) \lt x_{k-1}$$, define $$u_k \equiv x_{k-1}, l_k \equiv l_{k-1}$$ (shift the upper bound down).
If $$f(x_{k-1}) > x_{k-1}$$, define $$u_k \equiv u_{k-1}, l_k \equiv x_{k-1}$$ (shift the lower bound up)

(And if $$f(x_{k-1}) = x_{k-1}$$ we are done, so we can ignore this case).

This part is kind of like the intermediate value theorem, where we keep narrowing the search for our target.

The set $$f([l_k, u_k])$$ is in the square $$[l_k, u_k]\times[l_k, u_k]$$. (Using induction and $$f$$ is increasing. It's kind of clear if you draw a picture.)

For any $$k$$, the square $$[l_k, u_k]\times[l_k, u_k]$$ intersects the diagonal line $$\{ (x, x )\}$$ since it contains $$(l_k, l_k)$$, so if the sequence of nested squares converges, it converges to a point on the diagonal.

But it does converge, since $$[l_k, u_k]$$ converges to some singleton set $$\{ c \}$$.

Putting it all together, $$\forall k, f(c) \in f([l_k, u_k]) \subset [l_k, u_k]\times[l_k, u_k]$$.

$$f([c]) \in \cap_k [l_k, u_k]\times[l_k, u_k]$$.

$$f([c]) \in \{ (c, c) \}$$.

$$f(c) = c$$.

• I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree? – dfnu Jan 28 '19 at 19:12
• @Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument. – Mark Jan 29 '19 at 3:30

Hint

What about $$c=\inf\{x\in [0,1]\mid f(x)\leq x\}$$ if it exist ?

• This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis. – Mark Jan 28 '19 at 6:05

Similar to Mark's solution. It makes use of Completeness principle.

If $$f(0) = 0$$, then $$x = 0$$; if $$f(1) = 1$$, then $$x = 1$$; otherwise let $$a_0=f(0)$$, $$b_0=f(1)$$, and, for $$n=1,2,\dots$$ repeat the following.

(1) Let $$\Delta_n =\frac{a_{n-1}+b_{n-1}}{2}$$,

(2) If $$f\left(\Delta_n\right) = \Delta_n$$, then $$x = \Delta_n$$ and we are done.

(3) If $$f\left(\Delta_n\right) < \Delta_n$$, set $$a_n = a_{n-1}$$, $$b_n = \Delta_n$$.

(4) If $$f\left(\Delta_n\right) > \Delta_n$$, set $$a_n = \Delta_n$$, $$b_n = b_{n-1}$$.

This leads to the construction of a monotonically increasing sequence $$\left(a_n\right)_{n\in \mathbb Z^+}$$ and a monotonically decreasing sequence $$\left(b_n\right)_{n\in \mathbb Z^+}$$, such that $$0=a_0 \leq a_1 \leq \cdots \leq a_n \cdots \leq b_n \cdots \leq b_1 \leq b_0=1,$$ with $$$$f(b_n) and $$$$f(a_n)>a_n.\tag{2}\label{eq:up}$$$$ Furthermore we have $$$$b_n - a_n \leq \frac{1}{2^n}.\tag{3}\label{eq:diff}$$$$ So, by boundedness and monotonicity the two sequences converge (here Completeness comes into play), and by \eqref{eq:diff}, they converge to the same number $$\alpha \in [0,1]$$.

Suppose now $$f(\alpha) > \alpha$$. Then, for sufficiently large $$n$$, $$\alpha \leq b_n < f(\alpha),$$ which, together with \eqref{eq:down} gives $$f(b_n) < b_n < f(\alpha),$$ contradicting monotonicity of $$f$$. Similarly, if $$f(\alpha) < \alpha$$, then, for sufficiently large $$n$$, $$f(\alpha) < a_n \leq \alpha,$$ so that, using \eqref{eq:up}, the inequality $$f(a_n) > a_n > f(\alpha)$$ leads again to a contradiction. Thus, it must be $$f(\alpha) = \alpha$$.

Note

Completeness is necessary for the statement to hold true. As a counterexample consider the function $$f: [0,1]\cap \Bbb Q \rightarrow [0,1]\cap \Bbb Q$$ $$f(x) = -\frac{1}{x-3}.$$ This function is continuous and strictly increasing in its domain, but there is no point in the domain in which $$f(x) = x$$.