Editing Bolzano–Weierstrass theorem

{{short description|Bounded sequence in finite-dimensional Euclidean space has a convergent subsequence}}
In [[mathematics]], specifically in [[real analysis]], the '''Bolzano–Weierstrass theorem''', named after [[Bernard Bolzano]] and [[Karl Weierstrass]], is a fundamental [[convergence proof techniques|result about convergence]] in a finite-dimensional [[Euclidean space]] <math>\R^n</math>. The theorem states that each infinite [[bounded sequence]] in <math>\R^n</math> has a [[limit of a sequence|convergent]] [[subsequence]].<ref>Bartle and Sherbert 2000, p. 78 (for '''R''').</ref> An equivalent formulation is that a [[subset]] of <math>\R^n</math> is [[Sequentially compact space|sequentially compact]] if and only if it is [[closed set|closed]] and [[bounded set|bounded]].<ref>Fitzpatrick 2006, p. 52 (for '''R'''), p. 300 (for '''R'''<sup>''n''</sup>).</ref> The theorem is sometimes called the '''sequential compactness theorem'''.<ref>Fitzpatrick 2006, p. xiv.</ref>

== History and significance==

The Bolzano–Weierstrass theorem is named after mathematicians [[Bernard Bolzano]] and [[Karl Weierstrass]].  It was actually first proved by Bolzano in 1817 as a [[Lemma (mathematics)|lemma]] in the proof of the [[intermediate value theorem]].  Some fifty years later the result was identified as significant in its own right, and proven again by Weierstrass. It has since become an essential theorem of [[Real analysis|analysis]].

== Proof ==

First we prove the theorem for <math>\mathbb{R}</math> (set of all [[real number]]s), in which case the ordering on <math>\mathbb{R}</math> can be put to good use. Indeed, we have the following result:

'''Lemma''': Every infinite sequence <math>(x_n)</math> in <math>\mathbb{R}</math> has an infinite [[monotone sequence|monotone]] [[subsequence]] (a subsequence that is either [[non-decreasing]] or [[non-increasing]]).

'''Proof<ref>Bartle and Sherbert 2000, pp. 78-79.</ref>''': Let us call a positive integer-valued index <math>n</math> of a sequence a "peak" of the sequence when <math>x_m \leq x_n</math> for every <math>m > n</math>. Suppose first that the sequence has infinitely many peaks, which means there is a subsequence with the following indices <math>n_1<n_2<n_3<\dots<n_j<\dots</math> and the following terms <math>x_{n_1} \geq x_{n_2} \geq x_{n_3} \geq \dots \geq x_{n_j} \geq \dots</math>. So, the infinite sequence <math>(x_n)</math> in <math>\mathbb{R}</math> has a monotone (non-increasing) subsequence, which is <math>(x_{n_j})</math>. But suppose now that there are only finitely many peaks, let <math>N</math> be the final peak if one exists (let <math>N=0</math> otherwise) and let the first index of a new subsequence <math>(x_{n_j})</math> be set to <math>n_1=N+1</math>.  Then <math>n_1</math> is not a peak, since <math>n_1</math> comes after the final peak, which implies the existence of <math>n_2</math> with <math>n_1<n_2</math> and <math>x_{n_1} < x_{n_2}</math>. Again, <math>n_2</math> comes after the final peak, hence there is an <math>n_3</math> where <math>n_2<n_3</math> with <math>x_{n_2} \leq x_{n_3}</math>. Repeating this process leads to an infinite non-decreasing subsequence&nbsp; <math>x_{n_1} \leq x_{n_2} \leq x_{n_3} \leq \ldots</math>, thereby proving that every infinite sequence <math>(x_n)</math> in <math>\mathbb{R}</math> has a monotone subsequence.

Now suppose one has a [[bounded sequence]] in <math>\mathbb{R}^1</math>; by the lemma proven above [[there exists]] a monotone subsequence, likewise also bounded. It follows from the [[monotone convergence theorem]] that this subsequence converges.

The general case in <math>\mathbb{R}^n</math> can be proven using this lemma as follows. Firstly, we will acknowledge that any sequence <math>(x_m)_{m \in I}</math> in <math>\mathbb{R}^n</math> (where <math>I</math> denotes its [[index set]]) has a convergent subsequence if and only if there exists a countable set <math>K \subseteq I</math>  such that <math>(x_m)_{m \in K}</math> converges. Let <math>(x_m)_{m \in I}</math> be any bounded sequence in <math>\mathbb{R}^n</math>, then it can be expressed as an n-tuple of sequences in <math>\mathbb{R}</math> by writing <math>x_m = (x_{m1}, x_{m2}, \dots, x_{mn})</math>, where <math>(x_{mj})_{m \in I}</math> is a sequence for <math>j=1,2,\dots,n</math>. Since <math>(x_m)</math> is bounded, <math>(x_{mj})</math> is also bounded for <math>j=1,2,\dots, n</math>. It follows then by the lemma that <math>(x_{m1})</math> has a convergent subsequence and hence there exists a countable set <math>K_1 \subseteq I</math> such that <math>(x_{m1})_{m \in K_1}</math> converges. For the sequence <math>(x_{m2})</math>, by applying the lemma once again there exists a countable set <math>K_2 \subseteq K_1 \subseteq I</math> such that <math>(x_{m2})_{m \in K_2}</math> converges and hence <math>(x_{m2})</math> has a convergent subsequence. This reasoning may be applied until we obtain a countable set <math>K_n</math> for which <math>(x_{mj})_{m \in K_n}</math> converges for <math>j=1,2,\dots,n</math>. Hence, <math>(x_m)_{m \in K_n}</math> converges and therefore, since <math>(x_m)</math> was arbitrary, any bounded sequence in <math>\mathbb{R}^n</math> has a convergent subsequence.

== Alternative proof ==
There is also an alternative proof of the Bolzano–Weierstrass theorem using [[nested intervals]]. We start with a bounded sequence <math>(x_n)</math>:

<gallery widths="300" heights="150">
File:Bolzano–Weierstrass theorem - step 1.svg|Because <math>(x_n)_{n\in\N}</math> is bounded, this sequence has a lower bound <math>s</math> and an upper bound <math>S</math>.
File:Bolzano–Weierstrass theorem - step 2.svg|We take <math>I_1=[s,S]</math> as the first interval for the sequence of nested intervals.
File:Bolzano–Weierstrass theorem - step 3.svg|Then we split <math>I_1</math> at the mid into two equally sized subintervals.
File:Bolzano–Weierstrass theorem - step 4.svg|Because each sequence has infinitely many members, there must be (at least) one of these subintervals that contains infinitely many members of <math>(x_n)_{n\in\N}</math>. We take this subinterval as the second interval <math>I_2</math> of the sequence of nested intervals. 
File:Bolzano–Weierstrass theorem - step 5.svg|Then we split <math>I_2</math> again at the mid into two equally sized subintervals.
File:Bolzano–Weierstrass theorem - step 6.svg|Again, one of these subintervals contains infinitely many members of <math>(x_n)_{n\in\N}</math>. We take this subinterval as the third subinterval <math>I_3</math> of the sequence of nested intervals.
File:Bolzano–Weierstrass theorem - step 7.svg|We continue this process infinitely many times. Thus we get a sequence of nested intervals.
</gallery>

Because we halve the length of an interval at each step, the limit of the interval's length is zero. Also, by the ''[[nested intervals]] theorem'', which states that if each <math>I_n</math> is a closed and bounded interval, say

: <math>I_n = [a_n, \, b_n]</math>

with

: <math>a_n \leq b_n</math>

then under the assumption of nesting, the intersection of the <math>I_n</math> is not empty. Thus there is a number <math>x</math> that is in each interval <math>I_n</math>. Now we show, that <math>x</math> is an [[accumulation point]] of <math>(x_n)</math>.

Take a neighbourhood <math>U</math> of <math>x</math>. Because the length of the intervals converges to zero, there is an interval <math>I_N</math> that is a subset of <math>U</math>. Because <math>I_N</math> contains by construction infinitely many members of <math>(x_n)</math> and <math>I_N \subseteq U</math>, also <math>U</math> contains infinitely many members of <math>(x_n)</math>. This proves that <math>x</math> is an accumulation point of <math>(x_n)</math>. Thus, there is a subsequence of <math>(x_n)</math> that converges to <math>x</math>.

== Sequential compactness in Euclidean spaces ==

'''Definition:''' A set ''<math>A \subseteq \mathbb{R}^n</math>'' is [[sequentially compact]] if every sequence ''<math>\{x_n\}</math>'' in ''<math>A</math>'' has a convergent subsequence converging to an element of ''<math>A</math>''.

'''Theorem:'''  ''<math>A \subseteq \mathbb{R}^n</math>'' is [[sequentially compact]] if and only if ''<math>A</math>'' is [[Closed set|closed]] and bounded.

'''Proof:''' ([[sequentially compact|sequential compactness]] implies closed and bounded)

Suppose ''<math>A</math>'' is a subset of <math>\R^n</math> with the property that every sequence in ''<math>A</math>'' has a subsequence converging to an element of ''<math>A</math>''. Then ''<math>A</math>'' must be bounded, since otherwise the following unbounded sequence <math>\{x_n \} \in A</math> can be constructed. For every <math>n \in \mathbb{N}</math>, define <math>x_n</math> to be any arbitrary point such that <math>|| x_n || \geq n</math>. Then, every subsequence of <math>\{x_n\}</math> is unbounded and therefore not convergent. Moreover, ''<math>A</math>'' must be closed, since any [[Accumulation point|limit point]] of ''<math>A</math>'', which has a sequence of points in ''<math>A</math>'' converging to itself, must also lie in ''<math>A</math>.''

'''Proof:''' (closed and bounded implies [[sequentially compact|sequential compactness]])

Since ''<math>A</math>'' is bounded, any sequence ''<math>\{x_n\}\in A</math>'' is also bounded. From the [[Bolzano-Weierstrass theorem]], ''<math>\{x_n\}</math>'' contains a subsequence converging to some point <math>x \in\R^n</math>. Since <math>x</math> is a [[Accumulation point|limit point]] of ''<math>A</math>'' and ''<math>A</math>'' is a [[closed set]], ''<math>x</math>'' must be an element of ''<math>A</math>''.

Thus the subsets ''<math>A</math>'' of <math>\R^n</math> for which every sequence in ''A'' has a subsequence converging to an element of ''<math>A</math>'' &ndash; i.e., the subsets that are [[sequentially compact]] in the [[subspace topology]]&nbsp;&ndash; are precisely the closed and bounded subsets.

This form of the theorem makes especially clear the analogy to the [[Heine–Borel theorem]], which asserts that a subset of <math>\R^n</math> is [[Compact space|compact]] if and only if it is closed and bounded.  In fact, general topology tells us that a [[metrizable space]] is compact if and only if it is sequentially compact, so that the Bolzano–Weierstrass and Heine–Borel theorems are essentially the same.

== Application to economics ==
There are different important [[economic equilibrium|equilibrium]] concepts in economics, the proofs of the existence of which often require variations of the Bolzano–Weierstrass theorem. One example is the existence of a [[Pareto efficiency|Pareto efficient]] allocation. An allocation is a [[Matrix (mathematics)|matrix]] of consumption bundles for agents in an economy, and an allocation is Pareto efficient if no change can be made to it that makes no agent worse off and at least one agent better off (here rows of the allocation matrix must be rankable by a [[preference relation]]). The Bolzano–Weierstrass theorem allows one to prove that if the set of allocations is compact and [[Empty set|non-empty]], then the system has a Pareto-efficient allocation.

==See also==
*[[Sequentially compact space]]
*[[Heine–Borel theorem]]
*[[Completeness of the real numbers]]
*[[Ekeland's variational principle]]

== Notes ==
{{Reflist}}

== References ==
* {{cite book |last1=Bartle |first1=Robert G. |author1link = Robert G. Bartle|last2=Sherbert |first2=Donald R. |date=2000 |title=Introduction to Real Analysis |url=https://archive.org/details/introductiontore00bart_1|url-access=registration |edition=3rd |location=New York |publisher=J. Wiley |isbn=9780471321484 }}
* {{cite book |last=Fitzpatrick |first=Patrick M. |date=2006 |title=Advanced Calculus |edition=2nd |location=Belmont, CA |publisher=Thomson Brooks/Cole |isbn=0-534-37603-7 }}

==External links==
* {{springer|title=Bolzano-Weierstrass theorem|id=p/b016880}}
* [http://ram.rachum.com/bw.htm A proof of the Bolzano–Weierstrass theorem]
* [https://planetmath.org/proofofbolzanoweierstrasstheorem PlanetMath: proof of Bolzano–Weierstrass Theorem]
* [https://www.youtube.com/watch?v=dfO18klwKHg The Bolzano-Weierstrass Rap]

{{DEFAULTSORT:Bolzano-Weierstrass theorem}}
[[Category:Theorems about real number sequences]]
[[Category:Compactness theorems]]