Section 9.3 The Bolzano-Weierstrass Theorem
Once we introduced the Nested Interval Property (
Axiom 9.1.1), the Intermediate Value Theorem (
Theorem 9.2.1) followed pretty readily. The proof of Extreme Value Theorem (
Theorem 9.4.8) takes a bit more work. First we need to show that a function that satisfies the conditions of the EVT is bounded.
Theorem 9.3.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]\text{.}\) Then there exists a positive real number \(B\) such that \(|f(x)|\leq B\) for all \(x\in[\,a,b]\text{.}\)
Sketch of Alleged Proof: Let’s assume, for contradiction, that there is no such bound
\(B\text{.}\) This says that for any positive integer
\(n\text{,}\) there must exist
\(x_n\in[a,b]\) such that
\(\abs{f(x_n)}>n\text{.}\) (Otherwise
\(n\) would be a bound for
\(f\text{.}\))
IF the sequence
\(\left(x_n\right)\) converged to something in
\([\,a,b]\text{,}\) say
\(c\text{,}\) then we would have our contradiction. Indeed, we would have
\(\lim_{n\rightarrow\infty}x_n=c\text{.}\) By the continuity of
\(f\) at
\(c\) and
Theorem 8.2.1 of
Chapter 8, we would have
\(\lim_{n\rightarrow\infty}f(x_n)=f(c)\text{.}\) This would say that the sequence
\(\left(f(x_n)\right)\) converges, so by
Lemma 6.2.7 of
Chapter 6, it must be bounded. This would provide our contradiction, as we had
\(|f(x_n)|>n\text{,}\) for all positive integers
\(n\text{.}\) QED?
This would all work well except for one little problem. The way it was constructed, there is no reason to expect the sequence \(\left(x_n\right)\) 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 \(\left(x_n\right)\) may not converge, part of it will. We will need the following definition.
Definition 9.3.2.
Let \(\left(n_k\right)_{k=1}^\infty\) be a strictly increasing sequence of positive integers; that is, \(n_1\lt n_2\lt n_3\lt \cdots\) . If \(\left(x_n\right)_{n=1}^\infty\) is a sequence, then \(\left(x_{n_k}\right)_{k=1}^\infty=\left(x_{n_1},x_{n_2},x_{n_3},\ldots \right)\) is called a subsequence of \(\left(x_n\right)\text{.}\)
The idea is that a subsequence of a sequence is a part of the sequence, \((x_n)\text{,}\) 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\lt n_2\lt n_3\lt \cdots\) comes in. For example, suppose we started our subsequence with the term \(x_{100}\text{.}\) We could not choose our next term to be \(x_{99}\text{.}\) 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 \(\left(n_k\right)\) of the sequence of subscripts \(\left(n\right)\) in \(\left(x_n\right)\text{.}\)
Example 9.3.3.
Given the sequence \(\left(x_n\right)\text{,}\) the following are subsequences.
(a)
\(\left(x_2,\,x_4,\,x_6,\,\ldots\right)=\left(x_{2k}\right)_{k=1}^\infty\)
(b)
\(\left(x_1,\,x_4,\,x_9,\,\ldots\right)=\left(x_{k^2}\right)_{k=1}^ \infty\)
(c)
\(\left(x_n\right)\) itself.
Example 9.3.4.
The following are NOT subsequences.
(a)
\(\left(x_1,\,x_1,\,x_1,\,\ldots\right)\)
(b)
\(\left(x_{99},\,x_{100},\,x_{99},\,\ldots\right)\)
(c)
\(\left(x_1,\,x_2,\,x_3\right)\)
The subscripts in the examples we have seen so far have a discernable pattern, but this need not be the case. For example,
\begin{equation*}
\left(x_2,\,x_5,\,x_{12},\,x_{14},\,x_{23},\,\ldots\right)
\end{equation*}
would be a subsequence as long as the subscripts form an increasing sequence themselves.
Problem 9.3.5.
Suppose \(\lim_{n\rightarrow\infty}x_n=c\text{.}\) Prove that \(\lim_{k\rightarrow\infty}x_{n_k}=c\) for any subsequence \(\left(x_{n_k}\right)\) of \(\left(x_n\right)\text{.}\)
Hint.
First prove that \(n_k\geq k\text{.}\)
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 9.3.6.
The Bolzano-Weierstrass Theorem
Let \(\left(x_n\right)\) be a sequence of real numbers such that \(x_n\in[\,a,b]\text{,}\) \(\forall\) \(n\text{.}\) Then there exists \(c\in[\,a,b]\) and a subsequence \(\left(x_{n_k}\right)\text{,}\) such that \(\lim_{k\rightarrow\infty}x_{n_k}=c\text{.}\)
As an example of this theorem, consider the sequence
\begin{equation*}
\left((-1)^n\right)=\left(-1,1,-1,1,\ldots\right) \text{.}
\end{equation*}
This sequence does not converge, but the subsequence
\begin{equation*}
\left((-1)^{2k}\right)=\left(1,1,1,\ldots\right)
\end{equation*}
converges to \(1\text{.}\) This is not the only convergent subsequence, as \(\left((-1)^{2k+1}\right)=(-1,-1,-1,\,\ldots)\) converges to \(-1\text{.}\) 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(\left((-1)^n+1\right)n\right)\) and \(\left(n\right)\) represent these possibilities as the first has, for example, \(\left(\left((-1)^{2k+1}+1\right)(2k+1)\right)=(0,0,0,\,\ldots)\) and the second one has none.
The Bolzano-Weierstrass Theorem says that no matter how “random” the sequence
\(\left(x_n\right)\) 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 9.3.1.
Sketch of a Proof of the Bolzano-Weierstrass Theorem.
Suppose we have our sequence \(\left(x_n\right)\) such that \(x_n\in[a,b]\text{,}\) \(\forall\) \(n\text{.}\) To find our \(c\) for the subsequence to converge to we will use the NIP. Since we are already using \(\left(x_n\right)\) 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\text{,}\) and notice that \(x_n\in[a_1,b_1]\) for infinitely many \(n\text{.}\) (This is, in fact true for all \(n\text{,}\) 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\in[a_1,m_1]\) for infinitely many \(n\) or \(x_n\in[m_1,b_1]\) for infinitely many \(n\text{.}\) If \(x_n\in[a_1,m_1]\) for infinitely many \(n\text{,}\) then we relabel \(a_2=a_1\) and \(b_2=m_1\text{.}\) If \(x_n\in[m_1,b_1]\) for infinitely many \(n\text{,}\) then relabel \(a_2=m_1\) and \(b_2=b_1\text{.}\) In either case, we get \(a_1\leq a_2\leq b_2\leq b_1\text{,}\) \(b_2-a_2=\frac{1}{2}\left(b_1-a_1\right)\text{,}\) and \(x_n\in[a_2,b_2]\) for infinitely many \(n\text{.}\)
Now we consider the interval \([a_2,b_2]\) and let \(m_2\) be the midpoint of \([a_2,b_2]\text{.}\) Since \(x_n\in[a_2,b_2]\) for infinitely many \(n\text{,}\) then either \(x_n\in[a_2,m_2]\) for infinitely many \(n\) or \(x_n\in[m_2,b_2]\) for infinitely many \(n\text{.}\) If \(x_n\in[a_2,m_2]\) for infinitely many \(n\text{,}\) then we relabel \(a_3=a_2\) and \(b_3=m_2\text{.}\) If \(x_n\in[m_2,b_2]\) for infinitely many \(n\text{,}\) then we relabel \(a_3=m_2\) and \(b_3=b_2\text{.}\) In either case, we get \(a_1\leq a_2\leq a_3\leq b_3\leq b_2\leq b_1\text{,}\) \(b_3-a_3=\frac{1}{2}\left(b_2-a_2\right)=\frac{1}{2^2}\left(b_1-a_1\right)\text{,}\) and \(x_n\in[a_3,b_3]\) for infinitely many \(n\text{.}\)
If we continue in this manner, we will produce two sequences \(\left(a_k\right)\)and \(\left(b_k\right)\) with the following properties:
\(\displaystyle a_1\leq a_2\leq a_3\leq\cdots\)
\(\displaystyle b_1\geq b_2\geq b_3\geq\cdots\)
\(\forall\) \(k,\,a_k\leq b_k\)
\(\displaystyle \displaystyle\lim_{k\rightarrow\infty}\left(b_k-a_k\right)=\,\lim_{k\rightarrow\infty} \frac{1}{2^{k-1}}\left(b_1-a_1\right)=0\)
For each \(k\text{,}\) \(x_n\in[\,a_k,b_k]\) for infinitely many \(n\)
By properties 1-5 and the NIP, there exists a unique \(c\) such that \(c\in[a_k,b_k]\text{,}\) for all \(k\text{.}\) In particular, \(c\in[a_1,b_1]=[a,b]\text{.}\)
We have our \(c\text{.}\) Now we need to construct a subsequence converging to it. Since \(x_n\in[a_1,b_1]\) for infinitely many \(n\text{,}\) choose an integer \(n_1\) such that \(x_{n_1}\in[a_1,b_1]\text{.}\) Since \(x_n\in[a_2,b_2]\) for infinitely many \(n\text{,}\) choose an integer \(n_2>n_1\) such that \(x_{n_2}\in[a_2,b_2]\text{.}\) (Notice that to make a subsequence it is crucial that \(n_2>n_1\text{,}\) and this is why we needed to insist that \(x_n\in[a_2,b_2]\) for infinitely many \(n\text{.}\)) Continuing in this manner, we should be able to build a subsequence \(\left(x_{n_k}\right)\) that will converge to \(c\text{.}\) You can supply the details in the following problem.
Problem 9.3.7.
Turn the ideas of the above outline into a formal proof of the Bolzano-Weierstrass Theorem.
Problem 9.3.8.
Use the Bolzano-Weierstrass Theorem to complete the proof of
Theorem 9.3.1.
