Difference between revisions of "Theorem:Bolzano-Weierstrass"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Created page with "===Theorem (Bolzano—Weierstrass)=== <blockquote style="background: white; border: 1px solid black; padding: 1em;">Every bounded sequence of real numbers contains a conve...")
 
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
===Theorem (Bolzano&mdash;Weierstrass)===
+
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
<blockquote style="background: white; border: 1px solid black; padding: 1em;">Every bounded sequence of real numbers contains a convergent subsequence.</blockquote>
+
<td><strong>Theorem 1 (Bolzano-Weierstrass):</strong> Let <span class="math-inline"><math>(a_n)</math></span> be a bounded sequence. Then there exists a subsequence of <span class="math-inline"><math>(a_n)</math></span>, call it <span class="math-inline"><math>(a_{n_k})</math></span> that is convergent.</td>
 +
</blockquote>
 +
<ul>
 +
<li><strong>Proof 1:</strong> Let <span class="math-inline"><math>(a_n)</math></span> be a bounded sequence, that is the set <span class="math-inline"><math>\{ a_n : n \in \mathbb{N} \}</math></span> is bounded. Suppose that <span class="math-inline"><math>a</math></span> is a lower bound for this set, and <span class="math-inline"><math>b</math></span> is an upper bound for this set, and so <span class="math-inline"><math>a \leq a_n \leq b_n</math></span> for all <span class="math-inline"><math>n \in \mathbb{N}</math></span>. Therefore the set <span class="math-inline"><math>\{ a_n : n \in \mathbb{N} \}</math></span> is contained in the interval <span class="math-inline"><math>I_1 = [a, b]</math></span>.</li>
 +
</ul>
  
Let (''x''<sub>''n''</sub>) be a sequence of real numbers bounded by a real number ''M'', that is  |''x''<sub>''n''</sub>|&nbsp;&lt;&nbsp;''M'' for all ''n''. We define the set ''A'' by ''A''&nbsp;=&nbsp;{''r''&nbsp;|&nbsp;|''r''|&nbsp;&le;&nbsp;''M'' and ''r''&nbsp;&lt;&nbsp;''x''<sub>''n''</sub> for infinitely many ''n''}.  We note that ''A'' is non-empty since it contains &minus;''M'' and ''A'' is bounded above by ''M''.  Let ''x''&nbsp;=&nbsp;sup&nbsp;''A''. 
+
[[File:Bolzano-Weierstrass 1.png|center|Bolzano-Weierstrass 1]]
  
We claim that, for any ε&nbsp;&gt;&nbsp;0, there must be infinitely many points of ''x''<sub>''n''</sub> in the interval (''x''&nbsp;&minus;&nbsp;ε,&nbsp;''x''&nbsp;+&nbsp;ε).  Suppose not and fix an ε&nbsp;&gt;&nbsp;0 so that there are only finitely many values of ''x''<sub>''n''</sub> in the interval (''x''&nbsp;&minus;&nbsp;ε,&nbsp;''x''&nbsp;+&nbsp;ε). Either ''x''&nbsp;&le;&nbsp;''x''<sub>''n''</sub> for infinitely many ''n'' or ''x''&nbsp;&le;&nbsp;''x''<sub>''n''</sub> for at most only finitely many ''n'' (possibly no ''n'' at all). Suppose ''x''&lt;&nbsp;''x''<sub>''n''</sub> for infinitely many ''n''. Clearly in this case ''x''&nbsp;&ne;&nbsp;''M''. If necessary restrict ε so that ''x''&nbsp;+&nbsp;ε&nbsp;&le;&nbsp;''M''.  Set ''r''&nbsp;=&nbsp;''x''&nbsp;+&nbsp;ε/2 we have that ''r''&nbsp;&lt;&nbsp;''x''<sub>''n''</sub> for infinitely many ''n'' because there are only finitely many ''x''<sub>''n''</sub> in the set [''x'',''r''] and ''x'' must be less than infinitely many ''x''<sub>''n''</sub>, furthermore |''r''|&nbsp;&lt;&nbsp;''M''. Thus ''r'' is in ''A'', which contradicts that ''x'' is an upper bound for ''A''. Now suppose ''x''&lt;&nbsp;''x''<sub>''n''</sub> for at most finitely many ''n''. Set ''y''&nbsp;=&nbsp;''x''&nbsp;&minus;&nbsp;ε/2.  Then there are at most only finitely man ''n'' so that ''x''<sub>''n''</sub>&nbsp;&ge;&nbsp;''y''.  Thus, if ''r''&nbsp;&lt;&nbsp;x<sub>''n''</sub> for infinitely many ''n'', we have that ''r''&nbsp;&le;&nbsp;''y''. This means that ''y'' is an upper bound for ''A'' that is less than ''x'', contradicting that ''x'' wast the ''least'' upper bound of ''A''.  In either case we arrive at a contradiction, thus we must have that for any ε&nbsp;&gt;&nbsp;0, there must be infinitely many points of ''x''<sub>''n''</sub> in the interval (''x''&nbsp;&minus;&nbsp;ε,&nbsp;''x''&nbsp;+&nbsp;ε).
+
<ul>
   
+
<li>Let's take <span class="math-inline"><math>n_1 = 1</math></span>, i.e., let the first term of the subsequence <span class="math-inline"><math>(a_{n_k})</math></span> be equal to the first term of the parent sequence <span class="math-inline"><math>(a_n)</math></span>.</li>
Now we show there is a subsequence that converges to ''x''.  We define the subsequence inductively, choose any ''x''<sub>n<sub>1</sub></sub> from the interval (''x''&nbsp;&minus;&nbsp;1,&nbsp;''x''&nbsp;+&nbsp;1). Assuming we have chosen ''x''<sub>''n''<sub>1</sub></sub>,&nbsp;…,&nbsp;''x''<sub>''n''<sub>''k''&minus;1</sub></sub>, choose ''x''<sub>''n''<sub>''k''</sub></sub> to be an element in the interval (''x''&nbsp;&minus;&nbsp;1/k,&nbsp;''x''&nbsp;+&nbsp;1/k) so that ''n''<sub>''k''</sub>&notin;{''n''<sub>1</sub>,&nbsp;…,&nbsp;''n''<sub>k&minus;1</sub>}, this is possible as there are infinitely many elements of (''x''<sub>''n''</sub>) in the interval. Notice that for this choice of ''x''<sub>''n''<sub>''k''</sub></sub> we have that |''x''&nbsp;&minus;&nbsp;''x''<sub>''n''<sub>''k''</sub></sub>|<1/k.  Hence for any ε>0, if we take any ''k''&nbsp;&gt;&nbsp;1/ε, then  |''x''<sub>''n''<sub>''k''</sub></sub>-x|&nbsp;&lt;&nbsp;ε.  That is the subsequence (''x''<sub>''n''<sub>k</sub></sub>)&nbsp;→&nbsp;''x''. <math>\Box</math>
+
</ul>
 +
<ul>
 +
<li>We will now take the interval <span class="math-inline"><math>I_1</math></span> and divide into two subintervals of equal length. We will call these intervals <span class="math-inline"><math>I_1'</math></span> and <span class="math-inline"><math>I_1''</math></span>. We will also divide the set of indices into two sets. Let <span class="math-inline"><math>A_1 := \{ n \in \mathbb{N} : n > n_1, a_n \in I_1' \}</math></span> and let <span class="math-inline"><math>B_1 = \{ n \in \mathbb{N} : n > n_1, a_N \in I_1'' \}</math></span>. We note that <span class="math-inline"><math>A_1</math></span> is the set of indices <span class="math-inline"><math>n</math></span> greater than the first index in our subsequence, <span class="math-inline"><math>n_1</math></span>, such that <span class="math-inline"><math>a_n</math></span> is in the interval <span class="math-inline"><math>I_1'</math></span>. Similarly, <span class="math-inline"><math>B_1</math></span> is the set of indices <span class="math-inline"><math>n</math></span> greater than the first index in our subsequence, <span class="math-inline"><math>n_1</math></span> such that <span class="math-inline"><math>a_N</math></span> is in the interval <span class="math-inline"><math>I_1''</math></span>.</li>
 +
</ul>
 +
 
 +
[[File:Bolzano-Weierstrass 2.png|center|Bolzano-Weierstrass 2]]
 +
 
 +
<ul>
 +
<li>We note that both of the sets <span class="math-inline"><math>A_1</math></span> and <span class="math-inline"><math>B_1</math></span> cannot be finite since <span class="math-inline"><math>A_1</math></span> and <span class="math-inline"><math>B_1</math></span> contain all of the indices of the sequence <span class="math-inline"><math>(a_n)</math></span> which has infinitely many indices since it is an infinite sequence. If <span class="math-inline"><math>A_1</math></span> is infinite, then we let <span class="math-inline"><math>I_2 = I_1'</math></span>, and we will let <span class="math-inline"><math>n_2</math></span> be the smallest natural number index in the set <span class="math-inline"><math>A_1</math></span>, which we are ensured to have by the Well Ordering Principle. If <span class="math-inline"><math>A_1</math></span> is finite, then <span class="math-inline"><math>B_1</math></span> is infinite and we let <span class="math-inline"><math>I_2 = I_1''</math></span> and we let <span class="math-inline"><math>n_2</math></span> be the smallest natural number index in the set <span class="math-inline"><math>B_1</math></span>, which once again, we are ensured to have by the Well Ordering Principle.</li>
 +
</ul>
 +
<ul>
 +
<li>We will now take the interval <span class="math-inline"><math>I_2</math></span> and subdivide it into two subintervals of equal length, call them <span class="math-inline"><math>I_2'</math></span> and <span class="math-inline"><math>I_2''</math></span>. Once again, we will subdivide the set of indices into two sets. Let <span class="math-inline"><math>A_2 = \{ n \in \mathbb{N} : n > n_2, a_n \in I_2' \}</math></span> and let <span class="math-inline"><math>B_2 = \{ n \in \mathbb{N} : n > n_2, a_n \in I_2'' \}</math></span>.</li>
 +
</ul>
 +
 
 +
[[File:Bolzano-Weierstrass 3.png|center|Bolzano-Weierstrass 3]]
 +
 
 +
<ul>
 +
<li>Once again, if <span class="math-inline"><math>A_2</math></span> is infinite, then we will let <span class="math-inline"><math>I_3 = I_2'</math></span>, and let <span class="math-inline"><math>n_3</math></span> be the smallest natural number index of <span class="math-inline"><math>A_2</math></span>. If <span class="math-inline"><math>A_2</math></span> is finite, then <span class="math-inline"><math>B_2</math></span> is infinite and let <span class="math-inline"><math>n_3</math></span> be the smallest natural number index of <span class="math-inline"><math>B_2</math></span>.</li>
 +
</ul>
 +
<ul>
 +
<li>We will then take the interval <span class="math-inline"><math>I_3</math></span> and subdivide it into two subintervals of equal length, call them <span class="math-inline"><math>I_3'</math></span> and <span class="math-inline"><math>I_3''</math></span>. We will also subdivide the set of indices into two sets. <span class="math-inline"><math>A_3 = \{ n \in \mathbb{N} : n > n_3, a_n \in I_3' \}</math></span> and <span class="math-inline"><math>B_3 = \{ n \in \mathbb{N} : n > n_3, a_n \in I_3'' \}</math></span></li>
 +
</ul>
 +
 
 +
[[File:Bolzano-Weierstrass 4.png|center|Bolzano-Weierstrass 4]]
 +
 
 +
<ul>
 +
<li>We will continue this pattern to obtain a sequence of nested intervals <span class="math-inline"><math>I_1 \supseteq I_2 \supseteq ... \supseteq I_k \supseteq ...</math></span>. Furthermore, we will also have a subsequence <span class="math-inline"><math>(a_{n_k})</math></span> of <span class="math-inline"><math>(a_n)</math></span> where <span class="math-inline"><math>a_{n_k} \in I_k</math></span> for every <span class="math-inline"><math>k \in \mathbb{N}</math></span>.</li>
 +
</ul>
 +
 
 +
[[File:Bolzano-Weierstrass 5.png|center|Bolzano-Weierstrass 5]]
 +
 
 +
<ul>
 +
<li>We also note that the length of any interval <span class="math-inline"><math>I_k</math></span> is precisely equal to <span class="math-inline"><math>\frac{b - a}{2^{k-1}}</math></span>. By the nested intervals theorem there exists a common point <span class="math-inline"><math>\xi \in I_k</math></span> for all <span class="math-inline"><math>k \in \mathbb{N}</math></span>, and so we have that:</li>
 +
</ul>
 +
<div style="text-align: center;"><math>\begin{align} \mid a_{n_k} - \xi \mid \leq \frac{b - a}{2^{k-1}} \end{align}</math></div>
 +
<ul>
 +
<li>Therefore the subsequence <span class="math-inline"><math>(a_{n_k})</math></span> converges to <span class="math-inline"><math>\xi</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
<ul>
 +
<li><strong>Proof 2:</strong> Let <span class="math-inline"><math>(a_n)</math></span> be a bounded sequence. By the <a href="/the-monotone-subsequence-theorem">The Monotone Subsequence Theorem</a>, every sequence of real numbers has a monotonic subsequence. Let <span class="math-inline"><math>(a_{n_k})</math></span> be this monotonic subsequence. Since <span class="math-inline"><math>(a_n)</math></span> is bounded, it follows that <span class="math-inline"><math>(a_{n_k})</math></span> is also bounded since the values <span class="math-inline"><math>a_{n_k}</math></span> are contained in the sequence <span class="math-inline"><math>(a_n)</math></span>. Since <span class="math-inline"><math>(a_{n_k})</math></span> is both bounded and monotonic, then by <a href="/the-monotone-convergence-theorem">The Monotone Convergence Theorem</a>, <span class="math-inline"><math>(a_{n_k})</math></span> is a convergent subsequence. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
<blockquote style="background: white; border: 1px solid black; padding: 1em;">
 +
<td><strong>Theorem 2:</strong> If <span class="math-inline"><math>(a_n)</math></span> is a bounded sequence such that every convergent subsequence <span class="math-inline"><math>(a_{n_k})</math></span> of <span class="math-inline"><math>(a_n)</math></span> converges to <span class="math-inline"><math>L</math></span> then <span class="math-inline"><math>(a_n)</math></span> converges to <span class="math-inline"><math>L</math></span>.</td>
 +
</blockquote>
 +
<ul>
 +
<li><strong>Proof:</strong> Suppose that <span class="math-inline"><math>A = (a_n)</math></span> does not converge to <span class="math-inline"><math>L</math></span>. Then there exists a subsequence <span class="math-inline"><math>A' = (a_{n_k})</math></span> and an <span class="math-inline"><math>\epsilon_0 > 0</math></span> such that <span class="math-inline"><math>\mid a_{n_k} - L \mid \geq \epsilon_0</math></span> for all <span class="math-inline"><math>k \in \mathbb{N}</math></span>.</li>
 +
</ul>
 +
<ul>
 +
<li>Since <span class="math-inline"><math>A</math></span> is bounded, any subsequence of <span class="math-inline"><math>A</math></span> is also bounded, and so the subsequence <span class="math-inline"><math>A'</math></span> is bounded. Since <span class="math-inline"><math>A'</math></span> is bounded, then by the Bolzano-Weierstrass theorem there exists a convergent subsequence <span class="math-inline"><math>A''</math></span> of <span class="math-inline"><math>A'</math></span>. Since <span class="math-inline"><math>A''</math></span> is a convergent subsequence of <span class="math-inline"><math>A'</math></span>, then it is also a convergent sequence of <span class="math-inline"><math>A</math></span> by transitivity, and by the hypothesis, <span class="math-inline"><math>A''</math></span> converges to <span class="math-inline"><math>L</math></span>.</li>
 +
</ul>
 +
<ul>
 +
<li>But then convergence of <span class="math-inline"><math>A''</math></span> to <span class="math-inline"><math>L</math></span> contradicts the assumption that <span class="math-inline"><math>\mid a_{n_k} - L \mid \geq \epsilon_0</math></span>, and so the assumption that <span class="math-inline"><math>A</math></span> did not converge to <span class="math-inline"><math>L</math></span> was false. Therefore <span class="math-inline"><math>(a_n)</math></span> converges to <span class="math-inline"><math>L</math></span>. <span class="math-inline"><math>\blacksquare</math></span></li>
 +
</ul>
 +
 
 +
==Licensing==
 +
Content obtained and/or adapted from:
 +
* [http://mathonline.wikidot.com/the-bolzano-weierstrass-theorem The Bolzano-Weierstrass Theorem] under a CC BY-SA license

Latest revision as of 12:26, 8 November 2021

Theorem 1 (Bolzano-Weierstrass): Let be a bounded sequence. Then there exists a subsequence of , call it that is convergent.

  • Proof 1: Let be a bounded sequence, that is the set is bounded. Suppose that is a lower bound for this set, and is an upper bound for this set, and so for all . Therefore the set is contained in the interval .
Bolzano-Weierstrass 1
  • Let's take , i.e., let the first term of the subsequence be equal to the first term of the parent sequence .
  • We will now take the interval and divide into two subintervals of equal length. We will call these intervals and . We will also divide the set of indices into two sets. Let and let . We note that is the set of indices greater than the first index in our subsequence, , such that is in the interval . Similarly, is the set of indices greater than the first index in our subsequence, such that is in the interval .
Bolzano-Weierstrass 2
  • We note that both of the sets and cannot be finite since and contain all of the indices of the sequence which has infinitely many indices since it is an infinite sequence. If is infinite, then we let , and we will let be the smallest natural number index in the set , which we are ensured to have by the Well Ordering Principle. If is finite, then is infinite and we let and we let be the smallest natural number index in the set , which once again, we are ensured to have by the Well Ordering Principle.
  • We will now take the interval and subdivide it into two subintervals of equal length, call them and . Once again, we will subdivide the set of indices into two sets. Let and let .
Bolzano-Weierstrass 3
  • Once again, if is infinite, then we will let , and let be the smallest natural number index of . If is finite, then is infinite and let be the smallest natural number index of .
  • We will then take the interval and subdivide it into two subintervals of equal length, call them and . We will also subdivide the set of indices into two sets. and
Bolzano-Weierstrass 4
  • We will continue this pattern to obtain a sequence of nested intervals . Furthermore, we will also have a subsequence of where for every .
Bolzano-Weierstrass 5
  • We also note that the length of any interval is precisely equal to . By the nested intervals theorem there exists a common point for all , and so we have that:
  • Therefore the subsequence converges to .
  • Proof 2: Let be a bounded sequence. By the <a href="/the-monotone-subsequence-theorem">The Monotone Subsequence Theorem</a>, every sequence of real numbers has a monotonic subsequence. Let be this monotonic subsequence. Since is bounded, it follows that is also bounded since the values are contained in the sequence . Since is both bounded and monotonic, then by <a href="/the-monotone-convergence-theorem">The Monotone Convergence Theorem</a>, is a convergent subsequence.

Theorem 2: If is a bounded sequence such that every convergent subsequence of converges to then converges to .

  • Proof: Suppose that does not converge to . Then there exists a subsequence and an such that for all .
  • Since is bounded, any subsequence of is also bounded, and so the subsequence is bounded. Since is bounded, then by the Bolzano-Weierstrass theorem there exists a convergent subsequence of . Since is a convergent subsequence of , then it is also a convergent sequence of by transitivity, and by the hypothesis, converges to .
  • But then convergence of to contradicts the assumption that , and so the assumption that did not converge to was false. Therefore converges to .

Licensing

Content obtained and/or adapted from: