3
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ What have you tried so far? $\endgroup$ – Matteo Jan 27 at 15:44
  • $\begingroup$ I tried copying the IVT but could not connect it with an increasing function $\endgroup$ – The Poor Jew Jan 27 at 15:46
  • 1
    $\begingroup$ I think you can apply squeeze theorem after doing binary search $\endgroup$ – Mark Jan 27 at 15:47
  • $\begingroup$ 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. $\endgroup$ – Matteo Jan 27 at 15:54
  • $\begingroup$ @Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know. $\endgroup$ – Clement C. Jan 27 at 16:10
1
$\begingroup$

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 $.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Matteo Jan 28 at 19:12
  • $\begingroup$ @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. $\endgroup$ – Mark Jan 29 at 3:30
3
$\begingroup$

Hint

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Jan 28 at 6:05
2
$\begingroup$

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 \begin{equation} f(b_n)<b_n,\tag{1}\label{eq:down} \end{equation} and \begin{equation} f(a_n)>a_n.\tag{2}\label{eq:up} \end{equation} Furthermore we have \begin{equation}b_n - a_n \leq \frac{1}{2^n}.\tag{3}\label{eq:diff}\end{equation} 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.