Bolzano–Weierstrass theorem

From Wikipedia, the free encyclopedia

In real analysis, the Bolzano–Weierstrass theorem is an important theorem characterizing sequentially compact sets.

1 Formal statement
2 Understanding the theorem
3 Proof
- 3.1 Lemma
- 3.2 Proving the main theorem
4 Generalizations
5 History
6 Application to economics
7 Notes
8 References
9 External links

[edit] Formal statement

A subset A of Rⁿ is sequentially compact if and only if it is both closed and bounded.

[edit] Understanding the theorem

A set is sequentially compact if every sequence of points in the set has a convergent subsequence which converges to a point in that set. Intuitively, a sequence of points converges to a point if it becomes arbitrarily close to that point for elements of the set with large enough index.

A subsequence is a sequence that omits some members, for instance a₂, a₅, a₁₃, ... Keep in mind that although we are taking away some members of the sequence, the number of elements in the subsequence is still infinite.

The sequence a₁, a₂, a₃, ... is bounded if there exists a real number L such that the norm ||a_n|| is less than L for every index n. For the real numbers, the norm is just the absolute value function, and the concept can be illustrated graphically in 2 dimensions. If a_i is plotted on a 2-dimensional graph, with i on the horizontal axis and the value on the vertical, the sequence then travels to the right as it progresses. It is bounded if we can draw a horizontal strip which encloses all of the points.

A set is closed if every convergent sequence of points within the set converges to a point in the set. Note that this is not saying that every sequence within the set converges. While it may seem that every set must be closed by the above definition, this is in fact not the case. Consider the set of all points on the real line less than 1. Then it is easy to define a sequence that approaches 1 arbitrarily closely, but never exceeds or equals 1. This sequence converges to 1. But 1 is not in the set, so this is an example of a set that is not closed. (It is actually open.)

[edit] Proof

In order to proceed with the proof, we first introduce a lemma.

[edit] Lemma

Every bounded sequence in Rⁿ has a convergent subsequence.

Proof

It is easiest to prove the lemma first for the special case of the real numbers, and then generalize it to Rⁿ using the first form of mathematical induction.

Let $(a n)$ be a bounded sequence in the real numbers. Using results from monotonicity, there exists a monotone subsequence $(a_{n_r})$ . Since $(a_{n_r})$ is bounded, the lowest upper bound axiom implies that $(a_{n_r})$ converges.^[1]

Now, we prove the lemma for Rⁿ by induction.

The case for n = 1 was just proved. Now, suppose that for some positive integer n, every bounded sequence in Rⁿ has a convergent subsequence. To do a proof by induction, we must show that this implies that any bounded sequence in Rⁿ⁺¹ also has a convergent subsequence.

Let $a k$ be a bounded sequence in Rⁿ⁺¹. Let x_k be the final component of a_k for every positive integer k. Thus, we can write $a k$ as:

a_k = (b_k, x_k)

Here, b_k is the point in Rⁿ which is just all but the final component of a_k . So, we have two sequences: $x k$ , a sequence of real numbers, and $b k$ , a sequence in Rⁿ. $b k$ is a bounded sequence in Rⁿ, so it has a convergent sequence by the induction assumption, which we will label ${b_{k_j}}$ . Using the same set of indices, we form a subsequence of $x k$ , ${x_{k_j}}$ . We can then find a convergent subsequence of this, ${x_{k_{j_l}}}$ , since $x k$ is a sequence of real numbers.

Since ${b_{k_{j_l}}}$ is a subsequence of the convergent sequence ${x_{k_j}}$ , ${b_{k_{j_l}}}$ also converges. We now have that both ${x_{k_{j_l}}}$ and ${b_{k_{j_l}}}$ are convergent sequences. By componentwise convergence, ${a_{k_{j_l}}}$ converges, and is thus a convergent subsequence of $a k$ . This proves the lemma.

[edit] Proving the main theorem

Using the above lemma, we can now prove the main theorem. Note that since the theorem is an "if and only if" statement, we must prove it in both directions.

Proof

First, we prove that a closed, bounded set is sequentially compact.

Let A be a closed, bounded subset of Rⁿ. Let $a k$ be an arbitrary sequence in A. Since A is bounded, $a k$ must be bounded, so it follows from the lemma above that $a k$ has a convergent subsequence, which we will label ${a_{k_j}}$ . Call the point which ${a_{k_j}}$ converges to a. Since ${a_{k_j}}$ is a sequence in Rⁿ, and since A is a closed set, a must belong to A. This is precisely the statement that A is sequentially compact.

Now, the converse, namely that a sequentially compact set is closed and bounded. Let A be a sequentially compact set in Rⁿ.

First, we will show that A is closed. Let $a k$ be a sequence in A that converges to a in Rⁿ. Every subsequence of $a k$ must also converge to a. By the sequential compactness of A, a must be in A. Thus, A is closed.

Next, we show that A is bounded. We will prove this by contradiction. Suppose A is not bounded. Then, for any positive integer k, the norm of a is greater than k for some a in A. So, for each k, we can select an a_k such that the norm of a_k > k. By the sequential compactness of A, there exists a convergent subsequence of a_k, which we will label ${a_{k_j}}$ . Then, the norm of each element in this sequence is greater than the index, k_j. This means the sequence is unbounded, so it cannot be convergent. This is a contradiction, which proves that A is bounded.

Taking together everything that we have done, we see that the proof of the theorem is now complete.

[edit] Generalizations

The theorem is closely related to the Heine–Borel theorem. A generalization of both theorems to arbitrary topological spaces is as follows:

A space is compact if and only if every net has a convergent subnet.

[edit] History

The Bolzano–Weierstrass theorem is named after mathematicians Bernard Bolzano and Karl Weierstrass. It was actually first proved by Bolzano, but this proof was lost. It was re-proven by Weierstrass and became an important centerpiece of analysis. Later, it was discovered that Bolzano had in fact proved the theorem long before Weierstrass, hence the current name.

[edit] Application to economics

There are different important 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 efficient allocation. An allocation is a matrix of consumption bundles for agents in an economy, and an allocation is pareto efficient if no change can be made to it which 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 non-empty, then the system has a Pareto efficient allocation.

[edit] Notes

^ See for instance Lemma 2 at Proof of Bolzano–Weierstrass Theorem on PlanetMath.

[edit] References

^ Fitzpatrick, Patrick M. (2006) Advanced Calculus (2nd ed.). Belmont, CA: Thompson Brooks/Cole. ISBN 0-534-37603-7.

[edit] External links

Bolzano–Weierstrass theorem

From Wikipedia, the free encyclopedia

Contents

[edit] Formal statement

[edit] Understanding the theorem

[edit] Proof

[edit] Lemma

[edit] Proving the main theorem

[edit] Generalizations

[edit] History

[edit] Application to economics

[edit] Notes

[edit] References

[edit] External links

Views

Navigation

Interaction

Search

Languages