# The Bolzano-Weierstrass theorem – Serlo

Zur Navigation springen Zur Suche springen

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 monotony criterion for sequences and series. One may also go the other way round an d prove the Bolzano-Weierstrass theorem if the monotony criterion is known to hold. Another implication of the Bolzano-Weierstrass theorem is that continuous functions on a compact interval ${\displaystyle [a,b]}$ with ${\displaystyle a,b\in \mathbb {R} }$ are bounded and take a minimum and a maximum value.

## The Bolzano-Weierstrass theorem

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

The Bolzano-Weierstrass theorem reads as follows:

Theorem (Bolzano-Weierstrass theorem)

Every bounded sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ of real numbers has at least one accumulation point. That means, there is a real number ${\displaystyle x}$, such that at least one subsequence ${\displaystyle \left(x_{n_{k}}\right)_{k\in \mathbb {N} }}$ of ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ converges to ${\displaystyle 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 ${\displaystyle [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 ${\displaystyle x}$ , there are infinitely many points in each ${\displaystyle \epsilon }$-neighbourhood. No matter how small ${\displaystyle \epsilon }$ is. This ${\displaystyle x}$ is an accumulation point. Note that ${\displaystyle x}$ does not need to be part of the sequence and there may be multiple (even overcountably infinitely many) of those ${\displaystyle x}$.

Hint

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

## Why the completeness axiom is necessary

Completeness of the real numbers ${\displaystyle \mathbb {R} }$ means that each Cauchy sequence within ${\displaystyle \mathbb {R} }$ converges to an element in ${\displaystyle \mathbb {R} }$. 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 ${\displaystyle \mathbb {R} }$ and ${\displaystyle \mathbb {Q} }$, a Cauchy sequence is any sequence with a limit in ${\displaystyle \mathbb {R} }$. Some of these sequences in ${\displaystyle \mathbb {Q} }$ converges to an element in ${\displaystyle \mathbb {R} \setminus \mathbb {Q} }$, e.g. ${\displaystyle (a_{n})_{n\in \mathbb {N} },a_{n}=\left(1+{\tfrac {1}{n}}\right)^{n}\to e}$. The limit ${\displaystyle e}$ would be the only possible accumulation point of ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$. But ${\displaystyle e\notin \mathbb {Q} }$. So ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ has no limit in ${\displaystyle \mathbb {Q} }$, which means the Bolzano-Weierstrass theorem cannot hold for ${\displaystyle \mathbb {Q} }$.

The above example shows that the domain of the sequence elements is crucial for the Bolzano-Weierstrass theorem to hold. The complete ${\displaystyle \mathbb {R} }$ does work, whereas the incomplete ${\displaystyle \mathbb {Q} }$ 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 ${\displaystyle [s,S]}$ is compact. Finite unions of these intervals are compact, too. The real numbers ${\displaystyle \mathbb {R} }$ are not compact, since the Bolzano-Weierstrass theorem only guarantees for an accumulation point if the sequence is bounded within some ${\displaystyle [s,S]}$. Generally, unbounded sets are not compact.

## Proof (by nested intervals)

Proof (Bolzano-Weierstrass theorem)

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

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

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

So if we can construct a sequence of nested intervals which are all including infinitely many points of the sequence ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ , then there must be a point ${\displaystyle x}$ included in all intervals ${\displaystyle [a_{n},b_{n}]}$. This ${\displaystyle x}$ is a good candidate for an accumulation point of ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$, 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 ${\displaystyle I_{1}:=[s,S]}$ certainly contains infinitely many sequence elements ${\displaystyle x_{n}}$ (namely, all of them).

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

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

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

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

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

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

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

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

{\displaystyle {\begin{aligned}|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|\\&\vdots \\|I_{k}|&={\frac {1}{2}}|I_{k-1}|={\frac {1}{2^{k-1}}}|S-s|\end{aligned}}}

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

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

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

Let us finish the proof by verifying that ${\displaystyle x}$ is indeed an accumulation point. For any ${\displaystyle \epsilon >0}$ , we consider the ${\displaystyle \epsilon }$-neighbourhood ${\displaystyle (x-\epsilon ,x+\epsilon )}$ of ${\displaystyle x}$. Since ${\displaystyle \lim _{n\to \infty }|I_{n}|=0}$ , there must be an ${\displaystyle N\in \mathbb {N} }$ with ${\displaystyle |I_{N}|<\epsilon }$. And since ${\displaystyle x\in I_{N}}$ there is ${\displaystyle I_{N}\subseteq (x-\epsilon ,x+\epsilon )}$ (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 ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ . So also ${\displaystyle I_{N}}$ and ${\displaystyle (x-\epsilon ,x+\epsilon )\supseteq I_{N}}$ contain infinitely many elements.

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

## Proof (alternatively via monotony criterion)

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

Boundedness is one of the assumptions of the Bolzano Weierstrass. So if we can establish that there is a monotonous 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 monotonously decreasing subsequence, first. It is good to select an element ${\displaystyle a_{m}}$ with as many of the following elements smaller than it, i.e. ${\displaystyle a_{n} for ${\displaystyle n>m}$, as possible. If there is no such elements, we can definitely not proceed in selecting more elements for a monotonously 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 ${\displaystyle a_{n} for all ${\displaystyle n>m}$. We will call ${\displaystyle a_{m}}$ a "peak element" in that case.

As an example, we may consider the sequence ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ with ${\displaystyle a_{n}={\begin{cases}{\tfrac {1}{n}}&{\text{for }}n{\text{ odd,}}\\0&{\text{for }}n{\text{ even,}}\end{cases}}}$, i.e. the sequence ${\displaystyle (1,0,{\tfrac {1}{3}},0,{\tfrac {1}{5}},0,{\tfrac {1}{7}},0,{\tfrac {1}{9}},\ldots )}$.

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

${\displaystyle (a_{2k-1})_{k\in \mathbb {N} }=(1,{\tfrac {1}{3}},{\tfrac {1}{5}},{\tfrac {1}{7}},{\tfrac {1}{9}},\ldots )}$

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

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

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

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

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

The argument even runs through, if there are finitely many peak points: If ${\displaystyle m_{1},m_{2},\ldots m_{r}}$ are peak element indices, then ${\displaystyle 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 monotonously increasing subsequence. If there are infinitely many peak points, we just choose them as a monotonously decreasing subsequence. In any case, there is a monotonous subsequence.

Proof (Bolzano Weierstrass selection criterion)

Case 1: ${\displaystyle (a_{n})}$ has infinitely many peak points ${\displaystyle m_{1}. Then, the subsequence ${\displaystyle (a_{m_{k}})_{k\in \mathbb {N} }}$ is by definition (strictly) monotonously decreasing.

Case 2: ${\displaystyle (a_{n})}$ has finitely many peak points ${\displaystyle m_{1}. Set ${\displaystyle n_{1}=m_{r}+1}$. Then choose ${\displaystyle n_{2}>n_{1}}$ with ${\displaystyle a_{n_{2}}\geq a_{n_{1}}}$, and iteratively for all ${\displaystyle k\geq 2}$: ${\displaystyle n_{k+1}>n_{k}}$ with ${\displaystyle a_{n_{k+1}}\geq a_{n_{k}}}$. This is possible, since ${\displaystyle n>m_{r}}$ is not a peak point. The subsequence ${\displaystyle (a_{n_{k}})_{k\in \mathbb {N} }}$ is then monotonously 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 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ be a bounded real subsequence. The Bolzano-Weierstrass selection principle shows that there is a monotonous subsequence ${\displaystyle (a_{n_{k}})_{k\in \mathbb {N} }}$. Since ${\displaystyle (a_{n})}$ is bounded, so is ${\displaystyle (a_{n_{k}})}$ . The monotony criterion then implies convergence of ${\displaystyle (a_{n_{k}})}$. Therefore, ${\displaystyle (a_{n})}$ has a convergent subsequence and hence an accumulation point.