# Proof of the extreme value theorem without using subsequences

I am preparing a lecture on the Weierstrass theorem (probably best known as the Extreme Value Theorem in english-speaking countries), and I would propose a proof that does not use the extraction of converging subsequences. I did not explain subsequences in my calculus course, and I must choose between skipping the proof of the theorem and finding some proof which works only for functions $\mathbb{R} \to \mathbb{R}$.

I remember I once read a proof based on some bisection technique, but I can't find a reference right now. I would be grateful for any reference to books, papers, web sites about this alternative proof.

Edit: since somebody modified my question, I will write down the precise theorem I want to prove.

Theorem. Let $f \colon [a,b] \to \mathbb{R}$ be a continuous function. Then $f$ has at least a maximum and a minimum point.

-
Soo.. Do you want a prove for the Intermediate Value Thm without (sub-)sequences, or you want to deduce the Extreme Value Thm using the Interm.Value thm, by halfing the interval in infinitely many steps? – Berci Nov 1 '12 at 17:27
Do you mean the Thm. If $f:[a,b]\to\mathbb{R}$ is continuous, then for each $y\in [\min(f(a),f(b)),\max(f(a),f(b))]$ there is $x\in[a,b]$ such that $f(x)=y$? – AD. Nov 1 '12 at 17:29
I can't understand why somebody changed extreme to intermediate. I need a proof for the extreme value theorem! But I think that I wrote intermediate myself somewhere, sorry. – Siminore Nov 1 '12 at 18:17
In the paragraph you say "I am preparing a lecture on the Weierstrass theorem (probably best known as the Intermediate Value Theorem in english-speaking countries)". I assumed you were talking about the intermediate value theorem. Would you like me to change it back? P.S. Brian answered before the title change. – EuYu Nov 1 '12 at 18:21
@EuYu Sorry, in italian we never call it Extreme Value Theorem, and my brain switched to Intermediate Value Theorem just because it rhymes with it! – Siminore Nov 1 '12 at 18:22

Here is a proof of the Extreme Value Theorem that does not need to extract convergent subsequences. First we prove that :

Lemma: Let $f : [a,b] \rightarrow \mathbb{R}$ be a continuous function, then $f$ is bounded.

Proof: We prove it by contradiction. Suppose for example that $f$ does not have an upper bound, then $\forall n\in\mathbb{N}$, the set $\{x \in [a,b] , \, f(x) \geqslant n\}$ is not empty. Consider the following quantity: $$a_n = \inf\{x \in [a,b] , \, f(x) \geqslant n\}.$$ For all $n\in \mathbb{N}$, $a_n \in [a,b]$ exists. By the continuity of $f$, $f(a_n) \geqslant n$. And since $\{x \in [a,b] , \, f(x) \geqslant n+1\} \subset \{x \in [a,b] , \, f(x) \geqslant n\}$, we have $a_{n+1} \geqslant a_n$. Since $(a_n)_{n\in\mathbb{N}}$ is a monotonic bounded sequence, it has a limit: $$a_{\infty} = \lim_{n\to\infty} a_n$$ and $a_{\infty} \in [a,b]$. Let $M = \lceil f(a_{\infty}) \rceil$, then $\forall n \geqslant M+2$, $f(a_n) > f(a_{\infty})+1$. Hence by the continuity of $f$, $$f(a_{\infty}) = \lim_{n\to\infty}f(a_n) \geqslant f(a_{\infty})+1,$$ which yields a contradiction. Therefor $f$ must have an upper bound on $[a,b]$. For the same reason, $f$ must have an lower bound on $[a,b]$. In conclusion, $f$ is bounded on $[a,b$

With this lemma we can prove the Extreme Value Theorem.

Theorem: Let $f : [a,b] \rightarrow \mathbb{R}$ be a continuous function, then $f$ has at least a maximum and a minimum point.

Proof: We proved in the lemma that $f$ is bounded, hence, by the Dedekind-completeness of the real numbers, the least upper bound (supremum) $M$ of $f$ exists. By the definition of $M$, $$\forall n \in \mathbb{N}, \, S_n = \{x \in [a,b] , \, f(x) \geqslant M - \frac1n\} \neq \emptyset .$$ Let $s_n = \inf S_n$ be the infimum of $S_n$. We know that $a \leqslant s_n \leqslant s_{n+1} \leqslant b$ and $f(s_n) \geqslant M - \frac1n$. Since $(s_n)_{n\in\mathbb{N}}$ is a monotonic bounded sequence, the limit $s = \lim_{n\to\infty} s_n \in [a,b]$ exists. $\forall N\in\mathbb{N}$, $\forall n > N$, $f(s_n) > M - \frac1N$, so $M \geqslant f(s) = \lim_{n\to\infty} f(s_n) \geqslant M - \frac1N$. Hence $f(s) = M$ and $f$ has at least a maximum point. Similarly we can prove that $f$ has at least a minimum point. Q.E.D

-
It looks correct. Did you devise it? Do you have any reference? – Siminore Nov 2 '12 at 8:52
@Siminore: yes, I came up with this proof by myself. but the general idea of taking the sup of the inf or taking the inf of the sup must be very common, although I cannot think of any reference now. – corindo Nov 2 '12 at 17:09

Note: This answers the question as it was originally asked, which unfortunately wasn’t what was intended. I’ve added a sketch of an answer to the intended question below it.

I don’t have a reference at hand, but the proof is straightforward. Suppose that $f$ is continuous on $[a_0,b_0]$ with $f(a_0)<0<f(b_0)$. Recursively construct a sequence of intervals $[a_k,b_k]$ as follows.

• If $f\left(\frac{a_k+b_k}2\right)=0$, stop: you’ve found the desired point.

• If $f\left(\frac{a_k+b_k}2\right)<0$, let $a_{k+1}=\dfrac{a_k+b_k}2$ and $b_{k+1}=b_k$.

• If $f\left(\frac{a_k+b_k}2\right)>0$, let $a_{k+1}=a_k$ and $b_{k+1}=\dfrac{a_k+b_k}2$.

Then $\langle a_k:k\in\Bbb N\rangle$ is non-decreasing, $\langle b_k:k\in\Bbb N\rangle$ is non-increasing, $a_k<b_m$ for all $k,m\in\Bbb N$, and $b_k-a_k=(b-a)2^{-k}$ for all $k\in\Bbb N$, so $\sup_ka_k=\inf_kb_k$, and by continuity the function must be $0$ at this point.

Obviously you’d want to fill in a lot of detail and show how it generalizes to the full intermediate value theorem, but that’s it in a nutshell.

To use bisection to prove the extreme value theorem, let $f$ be a continuous real-valued function on $[a,b]$. First use bisection to show that $f$ is bounded above: if not, at stage $k$ choose the left half if it contains a point $x_k$ such that $f(x_k)\ge k$, and otherwise choose the right half and a point $x_k$ in it such that $f(x_k)\ge k$. Then $a_k\le x_k\le b_k$ for all $k\in\Bbb N$, so $\langle x_k:k\in\Bbb N\rangle\to\sup_ka_k$, and $f$ cannot be defined at $\sup_ka_k$.

Now let $y=\sup_{x\in[a,b]}f(x)$, and repeat the bisection process, but this time at stage $k$ choose the left half if it contains a point $x_k$ such that $f(x_k)>y-2^{-k}$; if not, the right half contains such a point $x_k$, and we choose the right half. Then $\langle x_k:k\in\Bbb N\rangle\to\sup_ka_k$, and $f(\sup_ka_k)=y$.

-
Thanks, but my question was about another theorem. Somebody changed the title. – Siminore Nov 1 '12 at 18:19
@Siminore: See if what I’ve added is enough for you. – Brian M. Scott Nov 1 '12 at 19:10
A downvote without an explanatory comment is less than helpful; if there’s an actual error, I’d like to be informed. – Brian M. Scott Nov 1 '12 at 23:25

Here's an outline of a "bisection" proof.

Suppose $\sup_{x \in [a,b]} f = \alpha$. Define a sequence of intervals $I_k = [a_k,b_k]$ recursively as follows: $I_0 = [a,b]$ and for $k > 0$

$I_k = \begin{cases} [a_{k-1}, \frac{a_{k-1} + b_{k-1}}{2}] \quad \text{if } \sup_{x \in [a_{k-1},\frac{a_{k-1} + b_{k-1}}{2}]} = \alpha \\ [\frac{a_{k-1} + b_{k-1}}{2},b_{k-1}] \quad \text{otherwise}. \end{cases}$

Then there exists $x \in \cap_{k} I_k$ (though this requires some care to show, and is a theorem by itself), and you can show $f(x) = \alpha$.

-
The problem with this is that it assumes the boundedness theorem. It is not difficult to prove the extreme value theorem without any appeal to sub-sequences given that you assume a continuous function is bounded. – EuYu Nov 1 '12 at 18:48
Good point. An almost identical argument can be used to prove the boundedness theorem, though. Assume that $\alpha = \infty$, create the same sequence of intervals, and arrive at a contradiction. – littleO Nov 1 '12 at 19:07