4.4 The Big Search

Searching continuous function is a powerful method that is similar to computer algorithms. Let us start a relatively simple proposition.

Proof:  Suppose that $f$ is NOT bounded. It means that we have a sequence ${\{x_n\}}_{n=1}^{\mathrm{\infty }}\subset [0,1]$ such that $|f(x_n)|\ge n$. By the Bolzano-Weierstrass Theorem, we have a convergent subsequence ${\{x_{n_k}\}}_{n=1}^{\mathrm{\infty }}$ tending to some $x\in [0,1]$ (here we actually use the fact that the interval is closed, the function $f\mathit{}\mathrm{(}x\mathrm{)}\mathrm{=}\mathrm{1}\mathrm{/}x$ is continuous on any point of the interval $\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{)}$ and of course, it is not bounded). Since $f$ is continuous ${\{f(x_{n_k})\}}_{k=1}^{\mathrm{\infty }}$ is convergent. On the other hand, $|f(x_{n_k})|\ge n_k$, so ${\{f(x_{n_k})\}}_{k=1}^{\mathrm{\infty }}$ is unbounded, in contradiction with Proposition 2.1.2. $\mathrm{\square }$

OK, we know that continuous functions on the interval $[0,1]$ have upper bounds. So there is a Least Upper Bound of the set $S=\{f(x),x\in [0,1]$. Remember the story of the least upper bound. It is sometimes a maximum, sometimes not. In the case of the values of a continuous function it is always a maximum.

Proof:  We need to show, that there exists $y\in [0,1]$ such that for any $x\in [0,1]$ $|f(x)|\le |f(y)|$. We know by the Least Upper Bound Principle that the supremum $s=sup(S)$ exists, where $S=\{f(x)\mid x\in [0,1]\}$. We do not know yet, whether this $s$ is “taken”, that is there exists some $x$ for which $f(x)=s$. We need to search for this $x$ by our Bolzano-Weierstrass Machine. We know that there exists a sequence ${\{x_n\}}_{n=1}^{\mathrm{\infty }}\subset [0,1]$ such that ${lim}_{n\to \mathrm{\infty }}f(x_n)=s$, indeed $s$ is the supremal value. We could stop immediately, if ${\{x_n\}}_{n=1}^{\mathrm{\infty }}$ would tend to some $x\in [0,1]$. Unfortunately, it is not guaranteed. Fire up the Bolzano-Weierstrass Machine!! There exists a subsequence ${\{x_{n_k}\}}_{n=1}^{\mathrm{\infty }}$ tending to some $x$!!! Also, ${\{f(x_{n_k})\}}_{n=1}^{\mathrm{\infty }}\}$ still tends to $s$. Hence $f(x)=s$ by continuity. $\mathrm{\square }$

The following theorem is extremely important and you can actually see how the search goes!! Because of the importance of this theorem, we actually give two proofs for it.

On the other hand, if we pick any number $t_2$ such that , then $f(t_2)>c$ since $t_2\notin S$. Also, . This shows that $c-\epsilon \le f(s)$, that is $c\le f(s)+\epsilon$. Hence the inequality $(\mathit{\text{<a href="Ch3.S3.html\#Thmpropo2" title="Proposition 3.3.2 ‣ 3.3 Closed sets ‣ Chapter 3 Limitpoints of sequences and closed sets ‣ MATH 113, The three C’s: convergence, closedness and continuity" class="ltx\_ref ltx\_font\_italic"><span class="ltx\_text ltx\_ref\_tag">3.3.2</span></a>}})$ follows. $\mathrm{\square }$

Proof:  [SECOND PROOF] We proceed similarly to a very simple computer algorithm. Let $x_1=x$, $y_1=y$. Pick $z_1=\frac{x_1+y_1}{2}$, the midpoint of the interval $[x_1,y_1]$. If , then let $x_2=z_1$ and $y_2=y_1$. If $f(z_1)\ge c$, then let $x_2=x_1$ and $y_2=z_1$. So,

$f(x_2)\le c\le f(y_2)$

Now, we want to find $s$ in between $x_2$ and $y_2$, and the interval $[x_2,y_2]$ is half as long as the original interval $[x_1,y_1]$. Now we consider $z_2=\frac{x_2+y_2}{2}$ and play the same game to obtain $x_3\le y_3$ such that $f(x_3)\le c\le f(y_3)$ Continuing the algorithm we obtain the intervals $[x_n,y_n]$ such that $f(x_n)\le c\le f(y_n)$. Clearly, $x_1,y_1,x_2,y_2,x_3,y_3,\mathrm{\dots }$ is a Cauchy-sequence, so it converges to some $s$. Since $x_n\to s$ we know that $f(s)\le c$. Also, $y_n\to s$ so $f(s)\ge c$. Therefore $f(s)=c$. $\mathrm{\square }$