My first-year students were thinking about the Bolzano–Weierstrass theorem earlier, so it seemed like a natural choice for this week’s theorem. I’ll try to describe what it says, and then two proofs (since they’re both nice).
The theorem is all about sequences of real numbers. Here are some examples of sequences:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, …
1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10, …
1, -1, 1, -1, 1, -1, 1, -1, 1, -1, …
Let’s think about these sequences for a bit. In particular, let’s think about whether they have limits, and if so what those limits are.
Well, the first one just gets bigger and bigger. It doesn’t feel like it tends to some fixed limit. We might say that it tends to infinity.
The second one is not exciting, but is a perfectly legitimate sequence. Does it have a limit? The limit must be 1 — how could it possibly be anything else?
The third one feels as though it must tend to a limit — it must tend to 0, right?
The fourth one is interesting. It seems very predictable, it never gets out of hand (it doesn’t tend to infinity), yet it doesn’t seem to tend to a limit: it just keeps oscillating between those two values.
I’m going to gloss over the formal definition of a limit here. There’s a time and a place for it (and it’s jolly important), but that’s not here. We’ll hope that our intuition of what it means for a sequence to tend to a limit will suffice. Just so we can try to agree, I’ll tell you what my version of that intuition is. I think that a sequence tends to a limit if the terms of the sequence eventually get really close to (and stay that close). In fact, we can decide how close we want to be “close” to be (within 0.01, or within 0.0000000001, or whatever), and we can be sure that the terms will eventually be that close to . (That’s pretty close to the formal definition, actually, but I’ll skip the Greek letters.)
Before we go on, there’s one really key fact about convergent sequences that I’d like to share with you. It’s sometimes called the fundamental axiom of analysis.
An increasing sequence, bounded above, tends to a limit.
What does this mean? Imagine we go for an infinite walk in a hilly landscape (so not Cambridgeshire!). At each step, we make a note of the height of your foot above sea level. This gives an infinite sequence of real numbers. (For the purposes of this post, you can take very tall steps if necessary!)
What does it mean for the sequence to be increasing? Simply that we never go downhill: at every step, we are at least as high above sea level as you were at the last step. If we walk on perfectly flat ground, that counts as increasing for our purposes. (We might say the sequence was strictly increasing if we wanted to insist that we always go uphill.)
What does it mean to say that the sequence is bounded above? It means there’s an upper bound on how high we get. There’s some height we never exceed. (It might be that we meet that height, it might be that we never get there.)
So let’s imagine going for this walk. We never go downhill, and there’s some height we never exceed. What can we say about our walk? If you think about it for a bit, I think it seems pretty natural to think that there’s some limit height: some height that our altitudes tend to. That’s what the fundamental axiom of analysis tells us.
Important note: the fundamental axiom doesn’t tell us anything about what the limit is, simply that it exists! By flipping things upside down, it also tells us that any decreasing sequence, bounded below, tends to a limit. The fancy word for a sequence that is either increasing or decreasing is monotone.
The two convergent sequences we had earlier (1, 1, 1, 1, … and 1, 1/2, 1/3, 1/4, …) are both monotone: the former is both increasing and decreasing, and the latter is decreasing. They are also both bounded below, by 0, say. (Of course, 1, 1, 1, 1, 1, … is also bounded below by 1, and by 1/10, and by -17, but that doesn’t matter — there’s just some lower bound.)
OK, so to the Bolzano-Weierstrass theorem. We had that intriguing fourth sequence (1, -1, 1, -1, 1, -1, …), which seemed to be quite interesting and well behaved, but not convergent. The theorem will tell us something interesting about it. Let’s see what it says.
Theorem (Bolzano-Weierstrass) A bounded sequence of real numbers has a convergent subsequence.
Let’s see what this means for our interesting example. We see that by taking the odd-numbered terms, we get the subsequence 1, 1, 1, 1, 1, …, and we’ve already seen that this converges to 1. One crucial point to note is that it might be that we get two (or more) convergent subsequences with different limits. We could take the even-numbered terms in our example, which would give the subsequence -1, -1, -1, -1, -1, …, which has the limit -1. Something for you to think about: if the original sequence is itself convergent, say to , then does every convergent subsequence converge to ? Indeed, is every subsequence convergent?
I said I’d describe two proofs of the Bolzano-Weierstrass theorem. I don’t quite know which order to put them in, so I’ve chosen pretty arbitrarily! Here goes with the first one…
We have a sequence of real numbers, and we know that it’s bounded. Let’s say that for all .
Our plan is to `zoom in’ on a subsequence that tends to a limit. This technique is sometimes known as lion hunting. We’re going to define a bunch of nested intervals. Crucially, the lengths of these intervals will tend to 0, so the intervals will `zoom in’ to a point. Also, at each stage we’ll make sure that our chosen nested interval still contains infinitely many terms of our sequence. We’ll then go through and pick one term from each interval. These will form the convergent subsequence. Let’s go!
Our first interval will be , since we know that every term of the sequence lies in this interval. But it will be convenient to call this interval , to fit with later notation.
Now we split this interval in half. Define . We’ll think about the intervals and . Now (at least) one of these subintervals must contain infinitely many of the terms of our sequence. Why? Well, otherwise we’d have two subintervals, each containing only finitely many terms, and that would give a finite number of terms in total, which would be absurd. (This is rather like the argument used in the pigeonhole principle.) If contains infinitely many of the terms, put and (so this becomes our new interval). If it doesn’t, put and (so becomes our new interval).
Now we repeat the process. We split into two equal subintervals, one of which must contain infinitely many terms of our sequence. And so on. Clear how the intervals are defined?
To recap. We have a bunch of intervals , each containing infinitely many terms of our sequence. We know that they’re nested, so we have for every i. So the form an increasing sequence. Moreover, they’re bounded above (e.g. by ). So, by our fundamental fact from earlier, the converge, say as . Similarly, we see that the converge; say as .
Can we compare and ? There’s a piece of information we haven’t used yet: we know that the length of each interval is half of that of the previous interval. That is, we have . Taking limits, we find that , i.e., . So these nested intervals do indeed `zoom in’ on a point , as promised.
OK, but what about our sequence? We want to pick a term of our sequence in each interval. This will give a subsequence that converges (to ). We can certainly pick a term from the interval ; let’s call it . Now there are still infinitely many terms that lie in ; let’s pick one that comes after and call it . And we keep doing this: we pick a later term that lies in the next interval, and we’re sure we can do this because we know we have infinitely many terms left at each stage. This gives a subsequence , and we see that as because the intervals halve in length each time. So we’re done — we’ve built a convergent subsequence!
Again, we have a sequence of real numbers, and we know that it’s bounded. Our aim is to show that it has a convergent subsequence.
We’re still going to use the fundamental fact from above, but this time in a different way. We’re going to show that the sequence must contain a monotone subsequence (an increasing subsequence or a decreasing subsequence). Since we know that the whole sequence is bounded above and below, the same certainly applies to any subsequence, and so if we have a monotone subsequence then we must have a convergent subsequence, using the fundamental fact. So we’ve now rephrased the problem: our aim is now to show that our sequence must contain a monotone subsequence. (As we’ll see, our proof works for any sequence of real numbers, not just bounded sequences. We need the boundedness to get convergence once we’ve got a monotone subsequence, but not to get that subsequence in the first place.)
I’d like to go back to thinking of our sequence as the sequence of heights at each step on our infinite walk in a hilly landscape. How might we hope to find a nice subsequence in those heights? I think it would be quite natural to think about what happens at the tops of the various hills. That leads on to the following definition.
Let’s say that a value is a summit if it’s at least as high as every later point. That is, for all . So if we stand on this summit, there is no later point that’s higher. There might be lots of dips and smaller hills; there might be a plateau; there might be lots of other hills at the same height as our summit. But none higher (except possibly ones we’ve already been past, but we’ve forgotten about them — we’re looking forwards now!).
Let’s make a list of all of the summits. Let’s say they’re , , …. This is slightly misleading notation, because we don’t know whether there are infinitely many summits. Let’s try the two possibilities separately.
Case 1: there are infinitely many summits. Then we have an infinite sequence , , …. Now is a summit and , so we must have . Similarly, we see that we have . We have a decreasing subsequence — so we’re done!
Case 2: there are finitely many summits (including the possibility that there’s no summit at all). Say that is the last summit, and put . (If there’s no summit at all, put .) Now isn’t a summit, so there must be some later higher point, say with . Again, isn’t a summit, so there must be some later higher point, say with . Continuing in this way, we get an infinite subsequence , , , …, and by construction it’s increasing. So we’re done in this case too!
Any introductory analysis textbook should discuss the theorem. The Wikipedia page discusses some generalisations. The Bolzano-Weierstrass theorem has many applications to other results in real analysis, such as the theorem that says that a continuous function on a closed, bounded interval is bounded and attains its bounds. There’s a really nice Tricki page about how to use Bolzano-Weierstrass to prove this and several other things — I strongly recommend it!