Theorem 20: the Bolzano-Weierstrass theorem

My first-year students were thinking about the BolzanoWeierstrass 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 (x_n) tends to a limit x if the terms of the sequence eventually get really close to x (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 x.  (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 x, then does every convergent subsequence converge to x?  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…

First proof

We have a sequence (x_n) of real numbers, and we know that it’s bounded.  Let’s say that |x_n| \leq K for all n.

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 [-K, K], since we know that every term of the sequence lies in this interval.  But it will be convenient to call this interval [a_0, b_0], to fit with later notation.

Now we split this interval in half.  Define c_0 = \frac{a_0+b_0}{2}.  We’ll think about the intervals [a_0, c_0] and [c_0, b_0].  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 [a_0, c_0] contains infinitely many of the terms, put a_1 = a_0 and b_1 = c_0 (so this becomes our new interval).  If it doesn’t, put a_1 = c_0 and b_1 = b_0 (so [c_0,b_0] becomes our new interval).

Now we repeat the process.  We split [a_1,b_1] 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 [a_i,b_i], each containing infinitely many terms of our sequence.  We know that they’re nested, so we have a_i \leq a_{i+1} \leq b_{i+1} \leq b_i for every i.  So the a_i form an increasing sequence.  Moreover, they’re bounded above (e.g. by b_0).  So, by our fundamental fact from earlier, the a_i converge, say a_i \to a as i\to \infty.  Similarly, we see that the b_i converge; say b_i \to b as i\to \infty.

Can we compare a and b?  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 b_{i+1} - a_{i+1} = \frac{b_i - a_i}{2}.  Taking limits, we find that b-a = 0, i.e., a=b.  So these nested intervals do indeed `zoom in’ on a point a, 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 a).  We can certainly pick a term from the interval [a_0,b_0]; let’s call it x_{n_0}.  Now there are still infinitely many terms that lie in [a_1,b_1]; let’s pick one that comes after x_{n_0} and call it x_{n_1}.  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 x_{n_j}, and we see that x_{n_j} \to a  as j\to\infty because the intervals halve in length each time.  So we’re done — we’ve built a convergent subsequence!

Second proof

Again, we have a sequence (x_n) 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 (x_n) 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 x_n is a summit if it’s at least as high as every later point.  That is, x_n \geq x_m for all m\geq n.  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 x_{n_1}, x_{n_2}, ….  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 x_{n_1}, x_{n_2}, ….  Now x_{n_1} is a summit and n_2 > n_1, so we must have x_{n_1} \geq x_{n_2}.  Similarly, we see that we have x_{n_1} \geq x_{n_2} \geq x_{n_3} \geq ....  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 x_M is the last summit, and put x_{m_1} = x_{M+1}.  (If there’s no summit at all, put x_{m_1} = x_1.)  Now x_{m_1} isn’t a summit, so there must be some later higher point, say x_{m_2} with x_{m_2} \geq x_{m_1}.  Again, x_{m_2} isn’t a summit, so there must be some later higher point, say x_{m_3} with x_{m_3} \geq x_{m_2}.  Continuing in this way, we get an infinite subsequence x_{m_1}, x_{m_2}, x_{m_3}, …, and by construction it’s increasing.  So we’re done in this case too!

Further reading

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!

Advertisements

11 Responses to “Theorem 20: the Bolzano-Weierstrass theorem”

  1. Nartey Evans Says:

    I am really impressed. Please keep on with the good work!

  2. julius Says:

    Nice work!!! I love your posts! Keep up with the good work!

  3. ijeoma Says:

    hmm this theroem has been reduced to its simplest form

  4. Mahamed Abdi Says:

    With such simple and interesting delivery of mathematics lectures makes maths the most flexible language of creative thinking. Thanks.

  5. palash deb Says:

    thats a great explanation it helped me understand the topic otherwise notations can be quite frustrating and it makes it difficult to visualise the result

  6. Analysis I: Lecture 2 « Theorem of the week Says:

    […] 3 (Bolzano-Weierstrass theorem): Let be a bounded sequence of real numbers, say for all .  Then there is a convergent […]

  7. steve Says:

    Excellent straightforward explanation. Very easily understood yet still holds the “heart” of this theorem.

  8. Chloe Says:

    You’re amazing! I always found myself slower at grasping abstract mathematical concepts than everyone else in class. I like your storytelling way of explaining the concept and I will forever picture mountainous landscapes from lord of the rings when I do proofs for sequences haha. Thank you!! =)

  9. Bill MacRitchie Says:

    Thankyou, that is a brilliant explanation.
    Have you authored an Analysis text?

  10. BIJAYA ADHIKARY Says:

    simplest explanation

  11. Arun Mishra Says:

    Nice mehod to prove the theorem

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: