The Bolzano-Weierstrass theorem

verweis=Math for Non-Geeks

This article concerns about a theorem that can be useful for many proofs in real analysis (and also in deeper maths topics): the Bolzano-Weierstrass theorem. It is named after Bernard Bolzano and Karl Weierstraß.

This theorem guarantees that there are accumulation points whenever a sequence is bounded. It is crucial for proving existence of limits (or at least accumulation points) for such sequences. One may also carry through these proofs using nested intervals, but it is often shorter to just use the Bolzano-Weierstrass theorem - which already makes use of nested intervals.

Some textbooks use the Bolzano-Weierstrass theorem to prove validity of the monotonicity criterion for sequences and series. One may also go the other way round and prove the Bolzano-Weierstrass theorem if the monotonicity criterion is known to hold. Another implication of the Bolzano-Weierstrass theorem is that continuous functions on a compact interval $[a, b]$ with $a, b \in ℝ$ are bounded and take a minimum and a maximum value.

A visual explanation for the Bolzano-Weierstrass theorem - video in German. (YouTube-video by Quatematik)

The Bolzano-Weierstrass theorem reads as follows:

Theorem (Bolzano-Weierstrass theorem)

Every bounded sequence $(x_{n})_{n \in ℕ}$ of real numbers has at least one accumulation point. That means, there is a real number $x$ , such that at least one subsequence ${(x_{n_{k}})}_{k \in ℕ}$ of $(x_{n})_{n \in ℕ}$ converges to $x$ .

You can intuitively justify this theorem as follows: A sequence is bounded if and only if all of its infinitely many elements fit inside the finite interval $[s, S]$ . Putting infinitely many points in a finite interval will necessarily make it crowded. So there should be some regions with a lot of points, crowding very closely together. The Bolzano-Weierstrass theorem now states that around one point $x$ , there are infinitely many points in each $ϵ$ -neighbourhood. No matter how small $ϵ$ is. This $x$ is an accumulation point. Note that $x$ does not need to be part of the sequence, and there may be multiple (even uncountably infinitely many) of those $x$ .

Hint

Often, the Bolzano-Weierstrass theorem is formulated in the literature as follows: "Every real and bounded sequence has a convergent subsequence". This formulation is equivalent to the above one.

Why the completeness axiom is necessary

Completeness of the real numbers $ℝ$ means that each Cauchy sequence within $ℝ$ converges to an element in $ℝ$ . Roughly speaking, a Cauchy sequence is a sequence which "looks as if it would converge" and it will be precisely defined elsewhere. For now, you need to know that in $ℝ$ and $ℚ$ , a Cauchy sequence is any sequence with a limit in $ℝ$ . Some of these sequences in $ℚ$ converges to an element in $ℝ ∖ ℚ$ , e.g. $(a_{n})_{n \in ℕ}, a_{n} = {(1 + \frac{1}{n})}^{n} \to e$ . The limit $e$ would be the only possible accumulation point of $(a_{n})_{n \in ℕ}$ . But $e \notin ℚ$ . So $(a_{n})_{n \in ℕ}$ has no limit in $ℚ$ , which means the Bolzano-Weierstrass theorem cannot hold for $ℚ$ .

The above example shows that the domain of the sequence elements is crucial for the Bolzano-Weierstrass theorem to hold. The complete $ℝ$ does work, whereas the incomplete $ℚ$ does not. Mathematicians often go one step further and give a name to any domain of a sequence, where the Bolzano-Weierstrass theorem works (i.e. Cauchy sequences have a convergent subsequence). Those sets are called compact. For instance, any bounded and closed interval $[s, S]$ is compact. Finite unions of these intervals are compact, too. The real numbers $ℝ$ are not compact, since the Bolzano-Weierstrass theorem only guarantees for an accumulation point if the sequence is bounded within some $[s, S]$ . Generally, unbounded sets are not compact.

Proof (by nested intervals)

Proof (Bolzano-Weierstrass theorem)

Let $(x_{n})_{n \in ℕ}$ be a bounded sequence. We know that there is a lower bound $s$ and an upper bound $S$ , such that all sequence elements lie in $[s, S]$ :

Now, we need to find an accumulation point of the sequence. Certainly, the completeness of $ℝ$ will be necessary, which we introduced via nested intervals. Recall: Nested intervals $I_{n} = [a_{n}, b_{n}]$ are a way to approximate any real number $x$ . Here, $a_{n}$ is a lower bound and $b_{n}$ an upper bound for $x$ . So $x$ is included in each of the nested interval $[a_{n}, b_{n}]$ . Nested means that $[a_{n + 1}, b_{n + 1}] \subseteq [a_{n}, b_{n}]$ for all $n \in ℕ$ , so the intervals are included in each other and get narrower and narrower.

If the width of the intervals converges to $0$ , then $x$ is indeed the only elements included in all intervals $x \in [a_{n}, b_{n}]$ for all $n \in ℕ$ .

So if we can construct a sequence of nested intervals which are all including infinitely many points of the sequence $(x_{n})_{n \in ℕ}$ , then there must be a point $x$ included in all intervals $[a_{n}, b_{n}]$ . This $x$ is a good candidate for an accumulation point of $(x_{n})_{n \in ℕ}$ , as there are infinitely many sequence elements around it.

How do find we find such a sequence of nested intervals containing infinitely many sequence elements? The interval $I_{1} := [s, S]$ certainly contains infinitely many sequence elements $x_{n}$ (namely, all of them).

Now, we need to make $I_{1}$ smaller. So let us divide $I_{1}$ into two equally large sub-intervals:

Since the sequence $(x_{n})_{n \in ℕ}$ contains infinitely many elements, at least one of the two sub-intervals also has to contain infinitely many elements of $(x_{n})_{n \in ℕ}$ . Otherwise, there would be only finitely many sequence elements, which is not the case. We define this interval with infinitely many elements as $I_{2}$ .

We can repeat the step and split $I_{2}$ into two equal parts:

The next interval $I_{3}$ is chosen as exactly that part of $I_{2}$ , which in turn contains infinitely many sequence elements. One of the two parts of $I_{2}$ has to contain infinitely many elements, since there are infinitely many elements in $I_{2}$ and otherwise, we would only have finitely many elements available. So we can indeed find a suitable $I_{3}$ with half the width of $I_{2}$ :

We iterate this procedure arbitrarily many times and get a sequence of nested intervals $(I_{n})_{n \in ℕ}$ , where each $I_{n + 1}$ has half the width of $I_{n}$ .

Mathematically, we can describe this inductive procedure as follows: We set $I_{1} := [s, S]$ . In each step, for $I_{k} = [a_{k}, b_{k}]$ we define the middle of the interval as $M = \frac{1}{2} (a_{k} + b_{k})$ and choose

$I_{k + 1} = [a_{k + 1}, b_{k + 1}] = {\begin{matrix} [a_{k}, M] & in [a_{k}, M] contains infinitely many x_{n} \\ [M, b_{k}] & else \end{matrix}$

Indeed, the width of $I_{k}$ is cut into half in each step:

$\begin{matrix} | I_{1} | & = | S - s | \\ | I_{2} | & = \frac{1}{2} | I_{1} | = \frac{1}{2} | S - s | \\ | I_{3} | & = \frac{1}{2} | I_{2} | = \frac{1}{2^{2}} | S - s | \\ | I_{4} | & = \frac{1}{2} | I_{3} | = \frac{1}{2^{3}} | S - s | \\ ⋮ \\ | I_{k} | & = \frac{1}{2} | I_{k - 1} | = \frac{1}{2^{k - 1}} | S - s | \end{matrix}$

Here, $| I_{k} |$ is the width of interval number $k$ . Hence,

$| I_{k} | = \frac{1}{2^{k - 1}} | S - s | \overset{n \to \infty}{\to} 0$

The interval width tends to $0$ . So there must be a unique point $x$ , which is included in all intervals $I_{k}$ . This $x$ is the desired accumulation point candidate.

Let us finish the proof by verifying that $x$ is indeed an accumulation point. For any $ϵ > 0$ , we consider the $ϵ$ -neighbourhood $(x - ϵ, x + ϵ)$ of $x$ . Since $lim_{n \to \infty} | I_{n} | = 0$ , there must be an $N \in ℕ$ with $| I_{N} | < ϵ$ . And since $x \in I_{N}$ there is $I_{N} \subseteq (x - ϵ, x + ϵ)$ (visualize this on a piece of paper or in your head). But now, we constructed the intervals such that they all contain infinitely many elements $(x_{n})_{n \in ℕ}$ . So also $I_{N}$ and $(x - ϵ, x + ϵ) \supseteq I_{N}$ contain infinitely many elements.

Since this works for any $ϵ > 0$ , we verified that $x$ is an accumulation point of $(x_{n})_{n \in ℕ}$ , which was to be shown.

Proof (alternatively via monotonicity criterion)

A further way to prove the Bolzano-Weierstrass theorem goes by the monotonicity criterion. This criterion says that every monotone and bounded sequence of real numbers converges.

Boundedness is one of the assumptions of the Bolzano-Weierstrass theorem. So if we can establish that there is a monotone subsequence, we know that it must converge, which is what we want to show. Can we select such a subsequence? The answer is yes, as the following theorem will prove:

Theorem (Bolzano Weierstrass selection criterion)

Every real sequence has a monotone subsequence.

How to get to the proof? (Bolzano Weierstrass selection criterion)

How can we select a monotone subsequence? Let's try to find a monotonically decreasing subsequence, first. It is good to select an element $a_{m}$ with as many of the following elements smaller than it, i.e. $a_{n} < a_{m}$ for $n > m$ , as possible. If there are no such elements, we can definitely not proceed in selecting more elements for a monotonically decreasing sequence. If there are only finitely many elements like this, we will sooner or later run out of elements to select, so this should also be avoided. By contrast, the best case is if $a_{n} < a_{m}$ for all $n > m$ . We will call $a_{m}$ a "peak element" in that case.

As an example, we may consider the sequence $(a_{n})_{n \in ℕ}$ with $a_{n} = {\begin{matrix} \frac{1}{n} & for n odd, \\ 0 & for n even, \end{matrix}$ , i.e. the sequence $(1, 0, \frac{1}{3}, 0, \frac{1}{5}, 0, \frac{1}{7}, 0, \frac{1}{9}, \dots)$ .

All odd numbers $1, 3, 5, 7, 9 \dots$ are "peak elements", since $a_{1} = 1 > a_{n}$ for all $n > 1$ , $a_{3} = \frac{1}{3} > a_{n}$ for all $n > 3$ and so on. So there are infinitely many peak elements $2 k - 1$ for $k \in ℕ$ . If we proceed selecting one peak element after the other, we will certainly end up with a monotonically decreasing sequence:

$(a_{2 k - 1})_{k \in ℕ} = (1, \frac{1}{3}, \frac{1}{5}, \frac{1}{7}, \frac{1}{9}, \dots)$

If $m_{k}$ denotes the index of the (peak) element $a_{m_{k}}$ , then this element must be smaller than all the previous elements $a_{m_{1}}, a_{m_{2}}, \dots, a_{m_{k - 1}}$ , since they were peak elements, too. So $a_{m_{1}} > a_{m_{2}} > \dots > a_{m_{k - 1}} > a_{m_{k}}$ . That means, whenever the sequence $(a_{n})$ has infinitely many "peak elements", we can select a monotonically decreasing subsequence $(a_{m_{k}})_{k \in ℕ}$ .

And what if we cannot find infinitely many "peak points"? Consider the following example:

Let $(a_{n})_{n \in ℕ}$ be the sequence with $a_{n} = (- 1)^{n} \frac{n}{n + 1}$ , i.e. $(- \frac{1}{2}, \frac{2}{3}, - \frac{3}{4}, \frac{4}{5}, - \frac{5}{6}, \frac{6}{7}, - \frac{7}{8}, \frac{8}{9}, - \frac{9}{10}, \dots)$ .

This sequence has no peak points at all: The off indices $2 k - 1$ have negative elements, which are situated below the even elements $2 k$ , i.e. $a_{2 k - 1} < 0 < a_{2 k}$ . However, the even indices $2 k$ can also not contain peak points, since the subsequence of even-indexed elements is monotonically increasing: $(a_{2 k})_{k \in ℕ} = (\frac{2}{3}, \frac{4}{5}, \frac{6}{7}, \frac{8}{9}, \dots))$ . So there is always an $n > 2 k$ with $a_{2 k} < a_{n}$ . But the even-indexed subsequence $(a_{2 k})_{k \in ℕ}$ is already a monotone subsequence! It is only monotonically increasing, instead of decreasing.

Is there always such a monotonically increasing subsequence, if we cannot find any peak elements? The answer is yes: If we selected $a_{m}$ , which is not a peak point and there is also no peak point after it, then there is some $a_{n}$ with $n > m$ , with $a_{n} \geq a_{m}$ . Otherwise, $a_{m}$ would be a peak point. So we can select $a_{n}$ as the next element of the subsequence, which is again not a peak point. Now the same assumptions hold for $a_{n}$ , as for $a_{m}$ (not a peak point and no peak points after it) and we can choose a further subsequence element bigger than $a_{n}$ . This step is repeated literately and renders an infinite subsequence $(a_{n_{k}})_{k \in ℕ}$ of $(a_{n})$ .

The argument even runs through, if there are finitely many peak points: If $m_{1}, m_{2}, \dots m_{r}$ are peak element indices, then $n_{1} = m_{r} + 1$ is not a peak point and has no peak points after it. So it can be used as a starting point for a construction.

We recap: if there are finitely many peak points, we are able to construct a monotonically increasing subsequence. If there are infinitely many peak points, we just choose them as a monotonically decreasing subsequence. In any case, there is a monotone subsequence.

Proof (Bolzano Weierstrass selection criterion)

Case 1: $(a_{n})$ has infinitely many peak points $m_{1} < m_{2} < \dots < m_{k} < m_{k + 1} < \dots$ . Then, the subsequence $(a_{m_{k}})_{k \in ℕ}$ is by definition (strictly) monotonically decreasing.

Case 2: $(a_{n})$ has finitely many peak points $m_{1} < m_{2} < \dots < m_{r}$ . Set $n_{1} = m_{r} + 1$ . Then choose $n_{2} > n_{1}$ with $a_{n_{2}} \geq a_{n_{1}}$ , and iteratively for all $k \geq 2$ : $n_{k + 1} > n_{k}$ with $a_{n_{k + 1}} \geq a_{n_{k}}$ . This is possible, since $n > m_{r}$ is not a peak point. The subsequence $(a_{n_{k}})_{k \in ℕ}$ is then monotonically increasing.

The above Bolzano-Weierstrass selection principle makes it very easy to prove the Bolzano-Weierstrass theorem:

Proof (alternative proof for the Bolzano-Weierstrass theorem)

Let $(a_{n})_{n \in ℕ}$ be a bounded real subsequence. The Bolzano-Weierstrass selection principle shows that there is a monotone subsequence $(a_{n_{k}})_{k \in ℕ}$ . Since $(a_{n})$ is bounded, so is $(a_{n_{k}})$ . The monotonicity criterion then implies convergence of $(a_{n_{k}})$ . Therefore, $(a_{n})$ has a convergent subsequence and hence an accumulation point.

Divergence to infinity →

Feedback? Do you want to join?

If you have questions concerning the content, or didn't understand something, the feel free to contact us! We would love to answer your questions! Also we are thankful for critics and/or comments! If you share our vision to explain university math in an comprehensible way, then contact us under:

E-Mail: en@serlo.org

E-Mail: hochschulmathematik@serlo.org

This article is licensed under the free license CC-BY-SA 3.0. With that you can use it, modify it or share it freely, as long as you name „Serlo“ as source and put you changes under the same CC-BY-SA 3.0 oder an compatible license. On the page „Kopier uns!“ we explain you what you have to pay attention to, when using our texts, picture or videos.