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

Question 1.

So where in this proof did we use the mystery hypothesis that $b \notin S$?

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}