Karl's Calculus Tutor - Box 3.0c Proof of the Extreme Value Theorem

Box 3.0c: Proof of the Extreme Value Theorem

You are to be commended for your pluck and curiosity, coming here. This proof is hard, and if you get stuck, try working on something else for a while, then coming back here in a few hours or even on another day. You never know when something has clicked in your mind while you were asleep. And do keep in mind that this is optional material. Don't lose the time you need to understand the required material by struggling with this.

We shall be relying heavily on the method of trapping a real number inside a sequence of nested intervals -- the method used in the proof of the intermediate value theorem. We shall use this method several times.

In addition, we shall have to rely upon two other theorems, which I have named The Camel and the Tent Theorem and Stepping Stone Theorem. The latter is given as an exercise in section 3.0. Although at first it may not seem clear where I'm going with these two, in the end, you will see that they form the foundation of the proof of the main theorem -- that is, every function that is continuous over a closed interval has a maximum and a minimum on that interval.

Everthing rests ultimately on the Cauchy sequence definition of real numbers. Remember that a Cauchy sequence is an infinite sequence of numbers that confines itself to as small an interval as you like provided you go far enough into the sequence. Recall that every Cauchy sequence of real numbers converges to some real number in the limit.

If you get through this whole development and understand it, go and treat yourself to something yummie. You deserve it. You will understand more about the real numbers than the average student does after passing two semesters of calculus. So stand tall and march boldly on...

Definition of Upper and Lower Bounds

If A is any nonempty set or collection of real numbers, then a real number, x, is said to be an upper bound of A if and only if x is greater than or equal to every real number that is a member of A. So, for example, if A is the set of all real numbers between 1 and 2, then 3 is an upper bound of A, and so is 1000.

A lower bound is defined the same way, except that x is a lower bound of A if and only if it is less than or equal to every real number that is a member of A. Using the same example of A being all the real numbers between 1 and 2, 0 would be a lower bound of A, and so would -1000.

We say that a set is bounded if it has both an upper bound and a lower bound.

If f(x) is a function and A is some nonempty set of real numbers, then the image of A under f(x) is the set of all real numbers that can be produced by applying f(x) to a member of A. So if a is a member of A, then f(a) is a member of the image if A under f(x). The function, f(x), is said to be bounded over A if the image of A under f(x) is bounded. In this proof we will consider A to be a closed interval (that is, it includes its endpoints) and f(x) to be a function that is continuous over that interval. For example, if f(x) = x² and A is the interval, 2 £ x £ 3, then the image of A under f(x) is the interval 4 £ y £ 9.

If A again is a nonempty set of real numbers, then we say that a real number, x, is the least upper bound of A if and only if it is an upper bound of A and it is less than or equal to all other upper bounds of A. If A is the set of real numbers between 1 and 2, then 2 is the least upper bound of A.

Likewise, a real number, x, is the greatest lower bound of A if and only if it is greater than or equal to all other lower bounds of A. In our example of the numbers between 1 and 2, 1 is the greatest lower bound of A.

The Camel and the Tent Theorem

If riding around the desert on a camel and sleeping in a tent at night were your life, you probably wouldn't want the camel to sleep in the tent with you. The proverbial camel, though, always tries to get his nose into the tent, hoping that he can gradually scooch the rest of himself in unnoticed.

So you lay down the law to the camel. The camel's nose can go this far toward the door of the tent, and no farther. When his nose reaches that point, the camel is still ok. But if he moves his nose even the tiniest fraction farther into the tent, you're going to slap it.

The point here is that of all the places the camel can put his nose, which is to say anywhere outside the tent, there is a spot that he can put it that is as close to being inside the tent as it can go without being slapped.

Imagine that all the places inside the tent are represented by the set, A. And imagine that all the places the camel can put his nose are upper bounds of A. Then that spot he can put his nose that is closest to being inside the tent is the least upper bound of A. This theorem guarantees that that spot always exists.

Theorem

If A is a nonempty set of real numbers that has an upper bound, then A also has a least upper bound.

Outline of Proof

Between any point inside the tent (where the camel's nose is not allowed) to any point outside the tent (where the camel's nose is allowed) you can draw a straight line to connect them. The midpoint of that line must either be inside or outside the tent. So by proper choice from the two fragments you can make a line of half the length that still goes from inside the tent to outside the tent. And you can keep doing that indefinitely, getting shorter and shorter lines that always go from inside the tent to outside the tent. We shall show that those shorter and shorter lines collapse onto a single point, and that it is the point where the camel's nose is allowed no farther.

Proof

We know that there are real numbers in A because it is nonempty. If you pick any real number that is a member of A, and then pick a to be less than that member, then a is guaranteed not to be an upper bound of A. So let that a be the lower endpoint of a closed interval. We have presupposed that A has an upper bound. So let b be some upper bound of A, and let it also be the upper endpoint of a closed interval. So we have an interval that goes from not-an-upper-bound to is-an-upper-bound.

Divide that interval precisely in half and make both fragments closed intervals. One of two situations exist:

The midpoint is an upper bound of A.
The midpoint is not an upper bound of A.

We now pick a new closed interval. If the midpoint is an upper bound of A, then pick the lower fragment as the new interval. If the midpoint is not an upper bound of A pick the upper fragment as the newer interval. This way we are guaranteed that:

The new interval is half the length of the old.
The new interval (like the old) goes from not-an-upper-bound to is-an-upper-bound.

Because of that second property, we can apply the same operation on the new interval, and then on the interval that results, and so on. Each time we will get an interval that goes from not-an-upper-bound to is-an-upper-bound. And just as in the proof for the intermediate value theorem we end up with a sequence of nested intervals, I₀, I₁, I₂, ... , whose length goes to zero. This means that the sequence of lower endpoints forms a Cauchy sequence and the sequence of upper endpoints forms a Cauchy sequence. Not only must each sequence converge to a real number, but they both must converge to the same real number (because the difference between the upper endpoint and the lower endpoint goes to zero in the limit). Call that real number, c.

Here is the crux of this proof. c must be the least upper bound of A. Why? First we show that c is indeed an upper bound. If it weren't, then there would have to be some real number, a, that was a member of A such that a > c, or equivalently a - c > 0. Let b₀, b₁, b₂, ... be the sequence of upper endpoints of the intervals. All are upper bounds of A. They are all greater than or equal to c. And the sequence of them converges to c, so you can always pick an n large enough to make b_n - c as close to zero as you like. That means that you can pick one so that b_n - c < a - c. But that means b_n < a. If a is a member of A, how can b_n, which is an upper bound of A be less than it? It can't. Hence c is an upper bound of A.

You can use a similar argument to show that no upper bound of A can be less than c. If there were such an upper bound, b, then we have c - b > 0. Let a₀, a₁, a₂, ... be the sequence of lower endpoints to the intervals. None of them can be upper bounds of A. They also converge to c, and so there is an a_n that makes c - a _n as close to zero as you'd like. In particular, there is one that makes c - a_n < c - b or equivalently, a_n > b. But how can something that is not an upper bound of A be greater than something that is? It can't. Hence c is the least upper bound of A.

So the camel always has a most favorable spot where he is allowed to rest his nose. The corollary to this is that every set that has a lower bound also has a greatest lower bound. The proof is identical, except you turn all the inequalities around.

If x is chosen from an interval, a £ x £ b (or from any other set), and f(x) is a function, then the set of all f(x)'s that can be formed from x's inside the interval (that is, the image of the interval under f(x)) is a set of real numbers. If that set has an upper bound or a lower bound, then this theorem applies to it.

Main Theorem

There are two parts to the theorem: If f(x) is continuous for all x on a closed interval, a £ x £ b, then

f(x) is bounded for all x on that interval. That means that there is some upper bound value, y_ub, that f(x) is never greater than and that there is also some lower bound value, y_lb, that f(x) is never less than, for all x on the closed interval.
There is at least one x = c, where c is on the closed interval, that makes f(c) greater than or equal to f(x) for all x on the interval, and there is at least one x = d, where d is also on the closed interval, that makes f(d) less than or equal to f(x) for all x on the interval. In other words, f(x) has both a maximum and a minimum on the interval, and you can find x's that give you the maximum and minimum values.

Outline of Proof

Since the theorem is in two parts, we shall prove them separately. To prove the first part, we shall observe that if f(x) is unbounded over the closed interval, then it must be unbounded over at least one half of that closed interval, and that half can be made to be a closed interval as well. So we can apply the operation again to get an even smaller interval. And we can continue to do so indefinitely, trapping a region in which f(x) is unbounded inside a smaller and smaller closed interval. We can demonstrate that both sequences of endpoints converge to the same real number, c. We then show that for every d you can name, f(x) must be unbounded in the interval c - d £ x £ c + d. This would make the delta-epsilon contract for continuity impossible to keep. Since f(x) being continuous was a premise, we must infer that f(x) is bounded over the original interval.

To prove the second part, again we divide the interval in half repeatedly to trap an x where f(x) has its least upper bound. We then use the camel and the tent theorem and the stepping stone theorem to show that continuity forces the existence of an x where f(x) is maximum and another x where it is minimum.

Proof of the First Part: A Continuous Function is Bounded over a Closed Interval

Suppose that f(x) is continuous over some closed interval but is not bounded. Divide that interval precisely in half, making each fragment a closed interval. One of the following two situations must be the case:

f(x) is unbounded over the lower fragment.
f(x) is bounded over the lower fragment but unbounded over the upper fragment.

If it is the first case, choose the next closed interval to be the lower fragment. Otherwise choose the next closed interval to be the upper fragment. This guarantees that:

The next interval is half the length of the last interval.
f(x) is unbounded over the next interval.

Once again there is no limit on how many times we can apply this operation. That means that we end up with a sequence of nested closed intervals, I₀, I₁, I₂, ... , in which I₀ is the original closed interval. Again you can find an interval in this sequence as short as you like by choosing the subscript high enough. f(x) must be unbounded over each and every one of them. And once again the two sequences of endpoints each form Cauchy sequences that converge to the same real number, which we call, c. Note that c is contained in every interval, I_n in the sequence of closed intervals described above.

Let d > 0 be as small as you like. The interval, c - d £ x £ c + d, must contain some of the I_n's described above. Why? Because we know that I_n can be made as short as you like by picking n large enough, and I_n always contains c. That means that I_n can be chosen short enough so it won't reach from c to c ± d. And since f(x) is unbounded over I_n, it must also be unbounded over the interval, c - d £ x £ c + d, which contains I_n.

But that means that no matter what e > 0 I choose, you will never be able to find any d > 0 that guarantees

   |f(x) - f(c)|  £  e

whenever |x - c| £ d.

Why? Because f(x) is unbounded for every interval, c - d £ x £ c + d, and the above inequality is attempting to place bounds of f(c) ± e on f(x) in such an interval. What all this means is that f(x) cannot be continuous at x = c. If f(x) is unbounded, it always fails the delta-epsilon contract required for continuity at x = c. We must conclude that f(x) cannot be simultaneously continuous on a closed interval and unbounded on that interval.

Proof of the Second Part: A Continuous Function has a Max and a Min on a Closed Interval

We have already shown that if f(x) is continuous over a closed interval, then it is bounded over that interval as well. That means that the image of the interval under f(x) has an upper bound and a lower bound. According to the camel and the tent theorem, it must also have a least upper bound and a greatest lower bound. We shall use the properties of the least upper bound to show that f(x) has a maximum on the closed interval. Nearly identical logic on the greatest lower bound proves that f(x) also has a minimum on the interval.

We know from the above that f(x) has a least upper bound over the interval. Call the real number that is f(x)'s least upper bound, y_lub. If you divide the interval precisely in half, making each fragment a closed interval, then y_lub is an upper bound of f(x) over each fragment, and it is the least upper bound of of f(x) over at least one of the fragments. So one of two situations must be the case:

y_lub is the least upper bound of f(x) over the lower fragment.
y_lub is not the least upper bound of f(x) over the lower fragment but it is the least upper bound of f(x) over the upper fragment.

If it is the first situation, choose the lower fragment as the next interval. If it is the second situation, choose the upper fragment as the next interval. This guarantees that:

The next interval is half the length of the last interval.
y_lub is the least upper bound of f(x) over the next interval.

There is no limit on how many times we can apply this operation, so again this leads to a sequence of nested closed intervals, I₀, I₁, I₂, ... , in which I₀ is the original interval. y_lub is the least upper bound of f(x) over every I_n in the sequence. And again you can find an interval in this sequence as short as you like by choosing the subscript high enough. Once again the two sequences of endpoints each form Cauchy sequences that converge to the same real number, which we call, c. Note that c is contained in every interval in the sequence of closed intervals described above.

Since both the lower end points, a₀, a₁, a₂, ... , and the upper endpoints, b₀, b₁, b₂, ... , of the intervals each form sequences, and each converges to a limit of c, and since f(x) is continuous, it means the stepping stone theorem applies. It follows from the stepping stone theorem that f(c) exists and is the limit of both f(a₀), f(a₁), f(a₂), ... and f(b₀), f(b₁), f(b₂), ... .

In addition to that, no matter how close to zero you choose a positive d, there will always be an I_n contained in the interval c - d £ x £ c + d. This is because every I_n contains c and you can always find an I_n short enough so that it won't reach from c to c ± d.

We now show that f(c) = y_lub. For if f(c) > y_lub, then y_lub would not be an upper bound of f(x). If f(c) < y_lub, then pick an e in the interval 0 < e < y_lub - f(c). According to the delta-epsilon continuity contract, there must be some d > 0 that guarantees

   |f(x) - f(c)|  £  e

whenever |x - c| £ d.

So whenever c - d £ x £ c + d, it means that f(x) is guaranteed to be within e of f(c). But y_lub is more than e distant from f(c), and the interval, c - d £ x £ c + d, contains an I_n over which y_lub is the least upper bound of f(x). Yet everything less than y_lub and greater than f(c) + e is also an upper bound of f(x) over I_n. And that means that y_lub is not the least upper bound of f(x) over I_n. It can't both be and not be f(x)'s least upper bound.

Hence you cannot have f(c) < y_lub either. If you can have neither f(c) < y_lub nor f(c) > y_lub, then they must be equal. So c is a point where where f(x) is maximum over the original closed interval, because f(c) exists and is the least upper bound of f(x) over the original closed interval.

Again, the proof for the existence of a minimum for continuous f(x) over a closed interval is nearly identical, except you use the greatest lower bound instead of the least upper bound, and some of the inequalities are turned around the other way.

Corollary

It follows almost directly from this theorem and from the intermediate value theorem that if f(x) is continuous over a closed interval, then the image of that closed interval under f(x) is also a closed interval.

Comments

Well, was getting through this proof a glorious victory or what? Thanks to your perseverence, you have taken your first steps into a field of mathematics with the impressive name of Real Analysis. What's more important, though, is that you have begun to think like a mathematician. And that will take you a long way in your calculus training.

Return to Main Text

email me at hahn@netsrq.com