7.3: The Bolzano-Weierstrass Theorem

Learning Objectives

• Explain the Bolzano-Weierstrass Theorem

Once we introduced the Nested Interval Property, the Intermediate Value Theorem followed pretty readily. The proof of Extreme Value (which says that any continuous function \(f\) defined on a closed interval \([a,b]\) must have a maximum and a minimum) takes a bit more work. First we need to show that such a function is bounded.

Theorem \(\PageIndex{1}\)

A continuous function defined on a closed, bounded interval must be bounded. That is, let \(f\) be a continuous function defined on \([a,b]\). Then there exists a positive real number \(B\) such that \(|f(x)|≤ B\) for all \(x ∈ [a,b]\).

Sketch of Alleged Proof

Let’s assume, for contradiction, that there is no such bound \(B\). This says that for any positive integer \(n\), there must exist \(x_n ∈ [a,b]\) such that \(|f(x_n)| > n\). (Otherwise \(n\) would be a bound for \(f\).) IF the sequence (\(x_n\)) converged to something in \([a,b]\), say \(c\), then we would have our contradiction. Indeed, we would have \(\lim_{n \to \infty } x_n = c\). By the continuity of \(f\) at \(c\) and Theorem 6.2.1 of Chapter 6, we would have \(\lim_{n \to \infty } f(x_n) = f(c)\). This would say that the sequence (\(f(x_n)\)) converges, so by Lemma 4.2.2 of Chapter 4, it must be bounded. This would provide our contradiction, as we had \(|f(x_n)| > n\), for all positive integers \(n\).

This would all work well except for one little problem. The way it was constructed, there is no reason to expect the sequence (\(x_n\)) to converge to anything and we can’t make such an assumption. That is why we emphasized the IF above. Fortunately, this idea can be salvaged. While it is true that the sequence (\(x_n\)) may not converge, part of it will. We will need the following definition.

Definition

Let \(\left ( n_k \right )_{k=1}^{\infty }\) be a strictly increasing sequence of positive integers; that is, \(n_1 < n_2 < n_3 < ···\). If \(\left ( x_n \right )_{k=1}^{\infty }\) is a sequence, then \(\left ( x_{n_k} \right )_{k=1}^{\infty } = (x_{n_1}, x_{n_2}, x_{n_3}, \cdots )\) is called a subsequence of (\(x_n\)).

The idea is that a subsequence of a sequence is a part of the sequence, (\(x_n\)), which is itself a sequence. However, it is a little more restrictive. We can choose any term in our sequence to be part of the subsequence, but once we choose that term, we can’t go backwards. This is where the condition \(n_1 < n_2 < n_3 < ···\) comes in. For example, suppose we started our subsequence with the term \(x_{100}\). We could not choose our next term to be \(x_{99}\). The subscript of the next term would have to be greater than \(100\). In fact, the thing about a subsequence is that it is all in the subscripts; we are really choosing a subsequence (\(n_k\)) of the sequence of subscripts (\(n\)) in (\(x_n\)).

Example \(\PageIndex{1}\):

Given the sequence (\(x_n\)), the following are subsequences.

1. \((x_2, x_4, x_6, ...) = (x_{2k})_{k=1}^\infty\)
2. \((x_1, x_4, x_9, ...) = (x_{k^2})_{k=1}^\infty\)
3. \((x_n)\) itself.

Example \(\PageIndex{2}\):

1. \((x_1, x_1, x_1, ...)\)
2. \((x_{99}, x_{100}, x_{99}, ...)\)
3. \((x_1, x_2, x_3, ...)\)

The subscripts in the examples we have seen so far have a discernable pattern, but this need not be the case. For example,

\[(x_2, x_5, x_{12}, x_{14}, x_{23} ...)\]

would be a subsequence as long as the subscripts form an increasing sequence themselves.

Exercise \(\PageIndex{1}\)

Suppose \(\lim_{n \to \infty } x_n = c\). Prove that \(\lim_{k \to \infty } x_{n_k} = c\) for any subsequence (\(x_{n_k}\)) of (\(x_n\)).

Hint

\(n_k \geq k\)

A very important theorem about subsequences was introduced by Bernhard Bolzano and, later, independently proven by Karl Weierstrass. Basically, this theorem says that any bounded sequence of real numbers has a convergent subsequence.

Theorem \(\PageIndex{2}\): The Bolzano-Weierstrass Theorem

Let (\(x_n\)) be a sequence of real numbers such that \(x_n ∈ [a,b]\), \(∀ n\). Then there exists \(c ∈ [a,b]\) and a subsequence (\(x_{n_k}\)), such that \(\lim_{k \to \infty } x_{n_k} = c\).

Sketch of Proof

Suppose we have our sequence (\(x_n\)) such that \(x_n ∈ [a,b]\), \(∀ n\). To find our \(c\) for the subsequence to converge to we will use the NIP. Since we are already using (\(x_n\)) as our original sequence, we will need to use different letters in setting ourselves up for the NIP. With this in mind, let \(a_1 = a\) and \(b_1 = b\), and notice that \(x_n ∈ [a_1,b_1]\) for infinitely many \(n\). (This is, in fact true for all n, but you’ll see why we said it the way we did.) Let \(m_1\) be the midpoint of \([a_1,b_1]\) and notice that either \(x_n ∈ [a_1,m_1]\) for infinitely many \(n\) or \(x_n ∈ [m_1,b_1]\) for infinitely many \(n\). If \(x_n ∈ [a_1,m_1]\) for infinitely many \(n\), then we relabel \(a_2 = a_1\) and \(b_2 = m_1\). If \(x_n ∈ [m_1,b_1]\) for infinitely many \(n\), then relabel \(a_2 = m_1\) and \(b_2 = b_1\). In either case, we get \(a_1 ≤ a_2 ≤ b_2 ≤ b_1, b_2 - a_2 = \frac{1}{2} (b_1 - a_1)\), and \(x_n ∈ [a_2,b_2]\) for infinitely many \(n\).

Now we consider the interval \([a_2,b_2]\) and let \(m_2\) be the midpoint of \([a_2,b_2]\). Since \(x_n ∈ [a_2,b_2]\) for infinitely many \(n\), then either \(x_n ∈ [a_2,m_2]\) for infinitely many \(n\) or \(x_n ∈ [m_2,b_2]\) for infinitely many \(n\). If \(x_n ∈ [a_2,m_2]\) for infinitely many \(n\), then we relabel \(a_3 = a_2\) and \(b_3 = m_2\). If \(x_n ∈ [m_2,b_2]\) for infinitely many \(n\), then we relabel \(a_3 = m_2\) and \(b_3 = b_2\). In either case, we get \(a_1 ≤ a_2 ≤ a_3 ≤ b_3 ≤ b_2 ≤ b_1, b_3 - a_3 = \frac{1}{2} (b_2 - a_2) = \frac{1}{2^2} (b_1 - a_1)\), and \(x_n ∈ [a_3,b_3]\) for infinitely many \(n\).

If we continue in this manner, we will produce two sequences (\(a_k\)) and (\(b_k\)) with the following properties:

1. \(a_1 ≤ a_2 ≤ a_3 ≤···\)
2. \(b_1 ≥ b_2 ≥ b_3 ≥···\)
3. \(∀ k\), \(a_k ≤ b_k\)
4. \(\lim_{k \to \infty } (b_k - a_k) = \lim_{k \to \infty } \frac{1}{2^{k-1}} (b_1 - a_1) = 0\)
5. For each \(k\), \(x_n ∈ [a_k,b_k]\) for infinitely many \(n\)

By properties 1-5 and the NIP, there exists a unique \(c\) such that \(c ∈ [a_k,b_k]\),for all \(k\). In particular, \(c ∈ [a_1,b_1] = [a,b]\).

We have our \(c\). Now we need to construct a subsequence converging to it. Since \(x_n ∈ [a_1,b_1]\) for infinitely many \(n\), choose an integer \(n_1\) such that \(x_{n_1} ∈ [a_1,b_1]\). Since \(x_n ∈ [a_2,b_2]\) for infinitely many \(n\), choose an integer \(n_2 > n_1\) such that \(x_{n_2} ∈ [a_2,b_2]\). (Notice that to make a subsequence it is crucial that \(n_2 > n_1\), and this is why we needed to insist that \(x_n ∈ [a_2,b_2]\) for infinitely many \(n\).) Continuing in this manner, we should be able to build a subsequence (\(x_{n_k}\)) that will converge to \(c\).

As an example of this theorem, consider the sequence

\[\left ( (-1)^n \right ) = (-1,1,-1,1,...)\]

This sequence does not converge, but the subsequence

\[\left ( (-1)^{2k} \right ) = (1,1,1,...)\]

\((-1,-1,-1, ...)\) converges to \(-1\). Notice that if the sequence is unbounded, then all bets are off; the sequence may have a convergent subsequence or it may not. The sequences \(\left ( ((-1)^n + 1)n \right )\) and (\(n\)) represent these possibilities as the first has, for example, \(\left ( ((-1)^{2k+1} + 1)(2k+1) \right ) = (0, 0, 0, \cdots )\) and the second one has none.

The Bolzano-Weierstrass Theorem says that no matter how “random” the sequence (\(x_n\)) may be, as long as it is bounded then some part of it must converge. This is very useful when one has some process which produces a “random” sequence such as what we had in the idea of the alleged proof in Theorem \(\PageIndex{1}\).

Exercise \(\PageIndex{2}\)

Turn the ideas of the above outline into a formal proof of the Bolzano-Weierstrass Theorem.

Exercise \(\PageIndex{3}\)

Use the Bolzano-Weierstrass Theorem to complete the proof of Theorem \(\PageIndex{1}\).