The Bolzano-Weierstrass theorem – Serlo

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 and 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 $[a,b]$ with $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)

The Bolzano-Weierstrass theorem reads as follows:

Theorem (Bolzano-Weierstrass theorem)

Every bounded sequence $(x_{n})_{n\in \mathbb {N} }$ of real numbers has at least one accumulation point. That means, there is a real number $x$, such that at least one subsequence $\left(x_{n_{k}}\right)_{k\in \mathbb {N} }$ of $(x_{n})_{n\in \mathbb {N} }$ 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 $\epsilon$-neighbourhood. No matter how small $\epsilon$ 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 overcountably 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 $\mathbb {R}$ means that each Cauchy sequence within $\mathbb {R}$ converges to an element in $\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 $\mathbb {R}$ and $\mathbb {Q}$, a Cauchy sequence is any sequence with a limit in $\mathbb {R}$. Some of these sequences in $\mathbb {Q}$ converges to an element in $\mathbb {R} \setminus \mathbb {Q}$, e.g. $(a_{n})_{n\in \mathbb {N} },a_{n}=\left(1+{\tfrac {1}{n}}\right)^{n}\to e$. The limit $e$ would be the only possible accumulation point of $(a_{n})_{n\in \mathbb {N} }$. But $e\notin \mathbb {Q}$. So $(a_{n})_{n\in \mathbb {N} }$ has no limit in $\mathbb {Q}$, which means the Bolzano-Weierstrass theorem cannot hold for $\mathbb {Q}$.

The above example shows that the domain of the sequence elements is crucial for the Bolzano-Weierstrass theorem to hold. The complete $\mathbb {R}$ does work, whereas the incomplete $\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 $[s,S]$ is compact. Finite unions of these intervals are compact, too. The real numbers $\mathbb {R}$ 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 \mathbb {N} }$ 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]$ :

A bounded sequence and its lower and upper bounds

Now, we need to find an accumulation point of the sequence. Certainly, the completeness of $\mathbb {R}$ 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 \mathbb {N}$, 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 \mathbb {N}$.

So if we can construct a sequence of nested intervals which are all including infinitely many points of the sequence $(x_{n})_{n\in \mathbb {N} }$ , 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 \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 $I_{1}:=[s,S]$ certainly contains infinitely many sequence elements $x_{n}$ (namely, all of them).

The first interval

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

Splitting the interval in two equal parts

Since the sequence $(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 $(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 $I_{2}$.

The second interval

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

Splitting the second interval

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}$:

The third interval

We iterate this procedure arbitrarily many times and get a sequence of nested intervals $(I_{n})_{n\in \mathbb {N} }$ , 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={\tfrac {1}{2}}(a_{k}+b_{k})$ and choose

$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 $I_{k}$ is cut into half in each step:

${\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, $|I_{k}|$ is the width of interval number $k$. Hence,

$|I_{k}|={\frac {1}{2^{k-1}}}|S-s|\xrightarrow {n\to \infty } 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 $\epsilon >0$ , we consider the $\epsilon$-neighbourhood $(x-\epsilon ,x+\epsilon )$ of $x$. Since $\lim _{n\to \infty }|I_{n}|=0$ , there must be an $N\in \mathbb {N}$ with $|I_{N}|<\epsilon$. And since $x\in I_{N}$ there is $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 $(x_{n})_{n\in \mathbb {N} }$ . So also $I_{N}$ and $(x-\epsilon ,x+\epsilon )\supseteq I_{N}$ contain infinitely many elements.

Since this works for any $\epsilon >0$ , we verified that $x$ is an accumulation point of $(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 $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 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 $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 \mathbb {N} }$ with $a_{n}={\begin{cases}{\tfrac {1}{n}}&{\text{for }}n{\text{ odd,}}\\0&{\text{for }}n{\text{ even,}}\end{cases}}$, i.e. the sequence $(1,0,{\tfrac {1}{3}},0,{\tfrac {1}{5}},0,{\tfrac {1}{7}},0,{\tfrac {1}{9}},\ldots )$.

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

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

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

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

Let $(a_{n})_{n\in \mathbb {N} }$ be the sequence with $a_{n}=(-1)^{n}{\tfrac {n}{n+1}}$, i.e. $(-{\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 )$.

The sequence a_n=(-1)^n*n/(n+1)

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

The argument even runs through, if there are finitely many peak points: If $m_{1},m_{2},\ldots 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 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: $(a_{n})$ has infinitely many peak points $m_{1}<m_{2}<\ldots <m_{k}<m_{k+1}<\ldots$. Then, the subsequence $(a_{m_{k}})_{k\in \mathbb {N} }$ is by definition (strictly) monotonously decreasing.

Case 2: $(a_{n})$ has finitely many peak points $m_{1}<m_{2}<\ldots <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 \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 $(a_{n})_{n\in \mathbb {N} }$ be a bounded real subsequence. The Bolzano-Weierstrass selection principle shows that there is a monotonous subsequence $(a_{n_{k}})_{k\in \mathbb {N} }$. Since $(a_{n})$ is bounded, so is $(a_{n_{k}})$ . The monotony criterion then implies convergence of $(a_{n_{k}})$. Therefore, $(a_{n})$ has a convergent subsequence and hence an accumulation point.