Fourteenth Week of the Course

Bolzano's Intermediate Value Theorem

last updated 1jul13 formerly 26apr11, 23apr12
\begin{document} \maketitle \section{Introduction} In 1817 Bernhard Bolzano published a very modern proof of the \textit{ Intermediate Value Theorem} (IVT) for continuous functions. Unfortunately, he was obliged to publish in an obscure Bohemian journal. Cauchy's 1821 proof was better received. In contrast to Bolzano, Cauchy still used infinitesimals, a concept that found logical vindication only in the past century. Weierstrass' proof in 1854 is the best known. Bolzano needed a lemma, that every bounded, infinite sequence of reals has a convergent subsequence. This, today, is known as the \textit{Bolzano-Weierstrass Theorem} (BWT). The IVT says that if $f$ is continuous on $[a,b]$ and $f(a) \lt u \lt f(b)$ then there exists some $ a \lt c \lt b$ for which $u=f(c)$. Contemporary proofs are usually based on the \textit{Least Upper Bound Principle}(LUBP), that a nonempty, bounded-above set of real numbers has a lub. In a previous lesson we saw the relation between the LUBP and \textit{ Bolzano's Lemma}(BWT) as equivalent axiomatic properties of the real numbers. We next discuss a screen capture of the proof in Wikipedia for Bolzano's IVT.

\section{Proof of the Intermediate Value Theorem} Above, we quote a proof by Wikipedia. The proof is correct, but it leaves several steps to the readeer, which a beginner would easily miss. Either the beginner draws a picture, whence everything stated is "obvious", or is unable to fill in the gaps. Firstly, the Wikipedist uses the "below set", $S = \{x\in [a,b] | f(x) \lt u \} $. Since we assumed that $f(a) < u $ we know that $a \in S$. And since we assumed that $f(b) > u $ we know that $b \in ub(S)$. Stop and think, there something profound going on here. Clearly every $x$ in the interval $[a,b]$ has the property that $x \lt b$. Since the Wikipedia proof assumes that $S \in [a,b]$ , doesn't that make $b$ an upper bound of $S$ as well? Since it is an upper bound whether or not we assume $f(b) > u$, we shall have to use this hypothesis somewhere else in the proof, but not here. Remember, one way to check your proof is to check that every hypothesis is actually used. Note that all the hypothesis says is that $b \notin S$. Next, knowing from the LUBP that $c:= lub(S)$ exists, we expect to be able to deduce our immediate conjecture that $f(c)=u$ just from the following ingredients: \begin{itemize} \item $f$ is continuous at $x=c$ \item $c$ is \textbf{an} upper bound for $S$ \item $c$ is \textbf{the least} of all upper bounds of $S$ \item and, let's not forget that $ b\notin S$ \end{itemize} Since we want to conclude that $f(c)=u$ we'll build a contradiction from assuming it does not. \subsection{The case that $u \lt f(c)$ } We chose the positive number $f(c) - u$ as our continuity epsilon, and obtain a $\delta \gt 0$ so that \[(\forall x \in (c-\delta, c+\delta) )( |f(x)-f(c)| \lt f(c) - u ) .\] Undoing the absolute value we use the left-inequality \[ -(f(c)-u) \lt f(x) - f(c) \Rightarrow u \lt f(x) .\] Recall that we assumed that $c$ was an upper bound for $S$. That means there are no $f(x) < u$ once $c \le x $. But now we have to admit that there aren't any of them in $(c-\delta, c)$ either. So $c-\delta$ is a better upper bound that $c$. This contradicts that $c$ is the \textbf{least} upper bound. So, we can reject half of the assumption that $f(c)\ne u$. \subsection{The case the $ f(c) \lt u $} This time we take the positive number $u-f(c)$ as our continuity epsilon at $c$. We again find a $\delta$ interval about $c$ so that \[ (\forall x \in (c-\delta, c+\delta))(|f(x)-f(c)| \lt u - f(c) ) .\] This time we expect to use the right inequality of the undone absolute values \[ f(x) -f(c) \lt u - f(c) \Rightarrow f(x) \lt u \mbox{ i.e. } x \in S .\] So, we conclude that $(\forall x \in (c, c + \delta))(x \in S).$ Even one element of $S$ to the right of $c$ would put the lie to $c$ being an upper bound. Now we have an entire interval of them, and an uncountably many contradictions. One suffices, and we can reject the other half of the assumption that $f(c)\ne u$.

So where in this proof did we use the mystery hypothesis that $b \notin S$? \subsubsection{Remark on "proof by contradiction"} If you don't like proofs by contradiction because of their twisted logic, here is another way of assembling the proof: So we have two numbers, $f(c)$ and $u$. There are three mutually exclusive possibilities, namely that $f(c) < u$, $f(c) > u $ and $f(c) = u$. The above argument shows that both of the first two cases contradict a previously established fact. So, that leaves the conclusion we had hoped for. Not all proofs by contradiction have such satisfactory substitutes, but when they do, it's nice to avoid the logical gymnastics of such proofs. \section{Discussion} The Wikipedia article where this proof was presented had an objection which the authors kindly left around for contemplation. As you see, the use of the word "supremum" for "lub" easily leads to misunderstandings. To give you some assurance that you understand this proof, here is a useful variant of the problem. You should solve it in this form when you enter the IVT into your Journal. Note that we actually found that $limsup(\{ x | f(x) \lt u \})$ is the last value of $x$ to the right for which $f(x)=u$. Suppose you chose $ glb(\{x \in [a,b] | f(x) > u \}$ for your solution. How would the argument go in this case? To appreciate this approach, consider the example of $f(x)=sin(x)$ on the interval $a=-\pi/4, b=+13\pi/4$ and chose $c=0$. Which zero of the sine function does each of the above approaches actually find? \section{Maxima and Minima Achieved} Another essential property of continuous function on closed intervals, is their achievement of a minimal and a maximal value on the interval. That is, \[f \mbox{ continuous on } [a,b] \Rightarrow (\exists a \le m \le b)( f(m) = max f([a,b]) .\] Recall that for a set $S$, $f(S) = \{f(x) | x\in S \}$. To prove this we first have to agree that the RHS is even a number, namely that the set $Y := f([a,b])$ has a maximum. It might not even be bounded above, until we prove that it is. Even then, it might just have a lub and not a maximum. And even if it has a maximum, it might not be the value of $f$ anywhere on the interval. We review what it means for a set $Y$ to be bounded above, by considering what it means for a set not to be bounded above.
Question 2.
Show (by means of a negation of a quantified predicate) that $Y$ \textbf{ not} having an upper bound means that \[ (\forall b \mbox{ real } )(\exists y \in Y)(b \lt y).\] \subsection{Marching to $\infty$} An immediate consequence of this is the following curious situation. If $Y$ is not bounded above then there is an increasing sequence of elements $ y_n \in Y$ with $ n < y_n $. Put a proof of this lemma into your Journal. You'll have to use an inductive argument that starts like this. Since $1 \notin ub(S)$ there is some $y_1 \gt 1 $ in $Y$. Next, $max(2,y_1)$ is not an upper bound either. So there is some $y_2 \gt 2 \mbox{ and } y_2 \gt y_1.$ Finish the argument yourself.
Question 3.
Apply the "marching to infinity principle" to show that If $Y=f([a,b])$ is not bounded above then there exists an infinite sequence of $x_n \in [a,b]$ with $n \lt f(x_n)$.
Question 4.
Continuing, why can we say that there is an \textbf{infinite} sequence $x_n \in [a,b]$ with $y_n=f(x_n)$. By which theorem does this have a convergent subsequence $m := lim x'_n $? We drop the primes because they get in the way. We have a convergent sequence (formerly that subsequenc), call it $x_n \rightarrow m$. We know that $y_n = f(x_n)$ is still marching to infinity. And we have $f$ continuous at $m$, to that $y_n=f(x_n)\rightarrow f(m)$. So, on the one hand, $y_n - f(m)$ is a null sequence, on the other $ n < y_n$. Here is a contradiction. Eventually \[ n \lt y_n = f(m) + (y_n - f(m)) \lt f(m) + 1 \] as soon as $n > N$ where $N$ is for the $\epsilon = 1$ in the null sequence. $ \subsection {Meanwhile, back at the ranch.} So, now that we know it exists, let's give it a name, $ u:=lub(f[a,b])$. All smaller numbers are not an upper bound. Let's be specific and choose the sequence $q_n := u - \frac{1}{n} $. Since these are not upper bounds. So for all $n\in \mathbb{N}$, there exists an $x_n\in [a,b]$ with $q_n \lt f(x_n) \lt u$. Inductively, we can even make sure all of the $x_n$ are different from each other in the same way as we did above.. By the Bolzano-Weierstrass Theorem, then, a subsequence $x'_n \rightarrow m$ converges. Again we drop the primes. Let's summarize what we now have \begin{itemize} \item $f$ is continuous at $m$. \item $x_n \rightarrow m $ \item $f(x_n) \rightarrow u$ \end{itemize} It remains to observe that by continuity, $f(x_n) \rightarrow f(m)$. Since limits are unique, $f(m)=u$.
Question 5.
Show that if $u - \frac{1}{n} \lt f(x_n) \lt u $ for all $n$ then $f(x_n) \rightarrow u$. \subsection{Equal time for the Minimum} As you prepare to enter the above discussion into your Journal, I suggest you do it with "maximum" replaced by "minimum". If you can do that, you understand the proof. \end{document}