Bolzano-Weierstrass Theorem/General Form

Theorem

Every infinite bounded space in a real Euclidean space has at least one limit point.

Proof

The proof of this theorem will be given as a series of lemmas that culminate in the actual theorem in the end.

Unless otherwise stated, all real spaces occurring in the proofs are equipped with the euclidean metric/topology.

Lemma 0: Suppose $S' \subseteq S \subseteq \R$. Then, any limit point of $S'$ is a limit point of $S$.

Proof: Consider any limit point $l$ of $S'$ and fix an $\epsilon > 0$.

Then, by definition:

$\paren {\map {B_\epsilon} l \setminus \set l} \cap S' \ne \O$

Thus, there is a real $s_\epsilon$ in both $\map {B_\epsilon} l \setminus \set l$ and $S'$.

But since $S' \subseteq S$, $s_\epsilon \in S'$ implies $s_\epsilon \in S$.

So, in other words, $s_\epsilon$ is in both $\map {B_\epsilon} l \setminus \set l$ and $S$.

That is:

$\paren {\map {B_\epsilon} l \setminus \set l} \cap S \ne \O$.

This is exactly what it means for $l$ to be a limit point of $S$.

This trivial lemma is given purely for the sake of argumentative completeness.

It is assumed implicitly in all the proofs below.

$\Box$

Lemma 1: Suppose $S$ is a non-empty subset of the reals such that its supremum, $\map \sup s$, exists.

If $\map \sup s \notin S$, then $\map \sup s$ is a limit point of $S$.

Proof: Aiming for a contradiction, suppose $\map \sup s$ were not a limit point of $S$.

So, by the negation of the definition of a limit point, there is an $\epsilon > 0$ such that:

$\paren {\map {B_\epsilon} {\map \sup s} \setminus \set {\map \sup s} } \cap S = \O$

Since $\map \sup s \notin S$, adding back $\map \sup s$ to $\map {B_\epsilon} {\map \sup s} \setminus \set {\map \sup s}$ still gives an empty intersection with $S$.

That is:

$\map {B_\epsilon} {\map \sup s} \cap S = \openint {\map \sup s - \epsilon} {\map \sup s + \epsilon} \cap S = \O$

So, since $\openint {\map \sup s - \epsilon} {\map \sup s} \subset \openint {\map \sup s - \epsilon} {\map \sup s + \epsilon}$, we also have:

$\openint {\map \sup s - \epsilon} {\map \sup s} \cap S = \O$

Now, because $\epsilon > 0$, $\openint {\map \sup s - \epsilon} {\map \sup s}$ is non-empty.

So, there is a real $r$ such that $\map \sup s - \epsilon < r < \map \sup s$.

This $r$ is an upper bound on $S$.

To see this, note that for any $s \in S$, $s < \map \sup s$.

Indeed, $s \le \map \sup s - \epsilon$ because otherwise, $\map \sup s - \epsilon < s < \map \sup s$ and $s$ would be in $\openint {\map \sup s - \epsilon} {\map \sup s}$ contradicting what we established earlier: that $\openint {\map \sup s - \epsilon} {\map \sup s}$ cannot have an element of $S$.

Hence, we finally have $s \le \map \sup s - \epsilon < r < \map \sup s$, making $r$ a lower upper bound on $S$ than $\map \sup s$. This contradicts the supremum property of $\map \sup s$.

$\Box$

Lemma 2: Suppose $S$ is a non-empty subset of the reals such that its infimum, $\underline{s}$, exists. If $\underline{s} \notin S$, then $\underline{s}$ is a limit point of $S$.

Proof: The proof is entirely analogous to that of the first lemma.

$\Box$

($\tilde s$ is used to mean $\map \sup s$, $\underline s$ is used to mean $\map \inf s$ throughout.)

Lemma 3: (Bolzano-Weierstrass on $\R$) Every bounded, infinite subset $S$ of $\R$ has at least one limit point.

Proof: As $S$ is bounded, it is certainly bounded above. Also, since it is infinite by hypothesis, it is of course non-empty. Hence, by the completeness axiom of the reals, $\tilde{s}_0 = \sup S$ exists as a real. Now, there are two cases:

• Case 1.0: $\tilde{s}_0 \notin S$: Then, by Lemma 1 above, $\tilde{s}_0$ is a limit point of $S$ and we are done.

• Case 2.0: $\tilde{s}_0 \in S$: Then, because $S$ is infinite, $S_1 = S \setminus \{\tilde{s}_0\}$ is non-empty. Of course, as $S_1 \subset S$, it is still bounded above because $S$ is. Hence, $\tilde{s}_1 = \sup S_1$ exists, again, by the completeness axiom of the reals. So, yet again, we have two cases:
  • Case 1.1: either $\tilde{s}_1 \notin S_1$, in which case we stop because we get a limit point of $S_1$ (and hence of $S$ as $S_1 \subset S$),
  • Case 2.1: or $\tilde{s}_1 \in S_1$, in which case we continue our analysis with $\tilde{s}_2 = \sup S_1 \setminus \{\tilde{s}_1\} = \sup S \setminus \{\tilde{s}_0, \tilde{s}_1\}$.

Continuing like this, we note that our analysis stops after a finite number of steps if and only if we ever reach a case of the form Case 1.k for some $k \in \mathbb{N}$. In this case, $\tilde{s}_k = \sup S_k \notin S_k$ and we use Lemma 1 to show that $\tilde{s}_k$ is a limit point of $S_k$ and, therefore, of $S$.

Otherwise, the proof continues indefinitely if we keep getting cases of the form Case 2.k for all $k \in \mathbb{N}$. In that case, $\tilde{s}_k \in S_k$ and we get a sequence $\tilde{S} = \{\tilde{s}_k\}_{k \in \mathbb{N}}$ of reals with the following properties:

• Each $\tilde{s}_k$ is in $S$. This is because, as remarked earlier, the only way we get our sequence is if $\tilde{s}_k \in S_k$. But $S_k$ is either $S$ when $k=0$ or $S \setminus \{\tilde{s}_0, \ldots , \tilde{s}_{k-1}\}$ when $k \geq 1$. In both cases, $S_k$ is a subset of $S$. From this fact, the claim easily follows.

• $\tilde{s}_k > \tilde{s}_{k+1}$. To see this, note that $\tilde{s}_{k+1} \in S_{k+1} = S \setminus \{\tilde{s}_0, \ldots , \tilde{s}_k\} = S_k \setminus \{\tilde{s}_k\}$. So, firstly, $ \tilde{s}_{k+1} \neq \tilde{s}_k$ and, secondly, because $ \tilde{s}_k$ is by construction an upper bound on $S_k$ (and therefore on its subset $S_{k+1}$), we have $ \tilde{s}_k \geq \tilde{s}_{k+1}$. Combining both these facts gives our present claim.

Now, the first property says that the set of all the $ \tilde{s}_k$'s, which is $ \tilde{S}$, is a subset of $S$. So, it is bounded because $S$ is. Then, certainly, it is also bounded below. Also, $\tilde{S}$ is obviously non-empty because it is infinite. Hence, one final application of the completeness axiom of the reals gives that $\underline{s} = \inf\tilde{S}$ exists as a real.

Note that $\underline{s} \notin \tilde{S}$. Otherwise, if $\underline{s} = \tilde{s}_k$ for some $k \in \N$, by the second property of our sequence, we would have $\underline{s} > \tilde{s}_{k+1}$. This would contradict the fact that $\underline{s}$ is a lower bound on $\tilde{S}$.

But then, by Lemma 2 above, $\underline{s}$ is a limit point of the set $\tilde{S}$ and, therefore, of its superset $S$.

$\Box$

Before moving onto the proof of the main theorem, I skim over the elementary concept of projection that will be used in the proof. Fix positive integers $m, n$ where $m \leq n$. Then, for any set $X$,

• There is a function $\pi_{1, \ldots ,m}:X^n \to X^m$ such that $\pi_{1, \ldots ,m}(x_1, \ldots , x_m , \ldots , x_n) = (x_1, \ldots , x_m)$. Essentially, $\pi_{1, \ldots ,m}$ takes in a coordinate of $n$ elements of $X$ and simply outputs the first $m$ elements of that coordinate.
• There is a function $\pi_m:X^n \to X$ such that $\pi_m(x_1, \ldots , x_m , \ldots , x_n) = x_m$. Essentially, $\pi_m$ takes in a coordinate of $n$ elements of $X$ and outputs just the $m^\text{th}$ element of that coordinate.
• In general, for positive integers $i \leq j < n$, there is a function $\pi_{i, \ldots , j}:X^n \to X^{j - i + 1}$ such that $\pi_{i, \ldots ,j}(x_1, \ldots , x_i , \ldots , x_j , \ldots , x_n) = (x_i, \ldots , x_j)$.

We begin with an easy lemma:

Lemma 4: For positive integers $m < n$ and $S \subseteq X^n$, $S \subseteq \pi_{1, \ldots ,m}(S) \times \pi_{m+1, \ldots , n}(S)$.

Proof: Fix any $(x_1, \ldots , x_m , x_{m+1} , \ldots , x_n) \in S$. Then, by the Definition:Image of Subset under Mapping, $(x_1, \ldots , x_m) \in \pi_{1, \ldots ,m}(S)$ because $\pi_{1, \ldots ,m}(x_1, \ldots , x_m , x_{m+1} , \ldots , x_n) = (x_1, \ldots , x_m)$. Similarly, $(x_{m+1} , \ldots , x_n) \in \pi_{m+1, \ldots , n}(S)$.

So, by Definition:Cartesian Product, $(x_1, \ldots , x_m , x_{m+1} , \ldots , x_n) \in \pi_{1, \ldots ,m}(S) \times \pi_{m+1, \ldots , n}(S)$.

Since $(x_1, \ldots , x_m , x_{m+1} , \ldots , x_n)$ was an arbitrary element of $S$, this means that $S \subseteq \pi_{1, \ldots ,m}(S) \times \pi_{m+1, \ldots , n}(S)$.

$\Box$

Lemma 5: For positive integers $i \leq j \leq n$ and $S \subseteq \R^n$, if $S$ is a bounded space in $\R^n$, then so is $\pi_{i, \ldots ,j}(S)$ in $\R^{j - i + 1}$.

Proof: For a contradiction, assume otherwise. So, by the negation of the definition of a bounded space, for every $K \in \R$, there are $x=(x_i, \ldots , x_j)$ and $y=(y_i, \ldots , y_j) $ in $\pi_{i, \ldots ,j}(S)$ such that $d(x,y) = |x - y| = \sqrt{\sum\limits_{s=i}^{j}(x_s -y_s)^2} > K$ where we get the formula $|x - y| = \sqrt{\sum\limits_{s=i}^{j}(x_s -y_s)^2}$ because we are working with the euclidean metric on all real spaces (after a suitable change of variables in the summation). Now, by definition of the image set $\pi_{i, \ldots ,j}(S)$, there are points $x' = (x_1, \ldots , x_i, \ldots , x_j , \ldots , x_n)$ and $y' = (y_1, \ldots , y_i, \ldots , y_j , \ldots , y_n)$ in $S$ from which $x$ and $y$ originated as coordinate components. Therefore, $d(x',y') = |x'-y'| = \sqrt{\sum\limits_{s=1}^{n}(x_s -y_s)^2} \geq \sqrt{\sum\limits_{s=i}^{j}(x_s -y_s)^2} > K$ contradicting the fact that $S$ is a bounded space.

$\Box$

Lemma 6: For any function $f: X \to Y$ and subset $S \subseteq X$, if $S$ is infinite and $f(S)$ is finite, then there exists some $y \in f(S)$ such that $f^{-1}(y) \cap S$ is infinite. Here, $f^{-1}(y)$ is the preimage of the element $y$.

Proof: If there weren't such an element in $f(S)$, then for all $y \in f(S)$, $f^{-1}(y) \cap S$ would be finite. Also, since $f(S)$ is finite, we may list its elements: $y_1, \ldots , y_n$ (there must be at least one image element as $S$ is non-empty).

Then, by repeated applications of Union of Finite Sets is Finite, we get that:

$\bigcup\limits_{y \in f(S)}(f^{-1}(y) \cap S) = (f^{-1}(y_1) \cap S) \cup \cdots \cup (f^{-1}(y_n) \cap S)$

must be finite.

But notice that:

\(\displaystyle \bigcup\limits_{y \in f(S)}(f^{-1}(y) \cap S)\)

\(=\)

\(\displaystyle \left[\bigcup\limits_{y \in f(S)}f^{-1}(y)\right] \cap S\)

$\quad$ Intersection Distributes over Union

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle f^{-1}(f(S)) \cap S\)

$\quad$ Preimage of Union under Mapping/Family of Sets

$\quad$

\(\displaystyle \)

\(=\)

\(\displaystyle S\)

$\quad$ Subset of Domain is Subset of Preimage of Image

$\quad$

This contradicts the fact that $S$ is infinite.

$\Box$

Main Theorem: (Bolzano-Weierstrass in $\R^n$) Every infinite, bounded subspace $S$ of $\R^n$ has at least one limit point.

Proof: We proceed by induction on the positive integer $n$:

(Base Case) When $n = 1$, the theorem is just Lemma 3 above which has been adequately proven.

(Inductive Step) Suppose that the theorem is true for some positive integer $n$. We must show that it is also true for the positive integer $n+1$. So, fix any infinite, bounded subset $S$ of $\R^{n + 1}$.

Consider the image of $S$ under the projection functions $\pi_{1, \ldots , n}$ and $\pi_{n+1}$: $S_{1, \ldots , n} = \pi_{1, \ldots , n}(S)$ and $S_{n+1} = \pi_{n+1}(S)$. Then,

• Because $S$ is a bounded space of $\R^{n + 1}$, $S_{1, \ldots , n}$ and $S_{n+1}$ must be bounded spaces of $\R^n$ and $\R$ respectively by Lemma 5.
• Also, $S \subseteq S_{1, \ldots , n} \times S_{n+1}$ by Lemma 4. So, by the fact that $S$ is infinite and Subset of Finite Set is Finite, $S_{1, \ldots , n} \times S_{n+1}$ is infinite. But then, by Product of Finite Sets is Finite, either $S_{1, \ldots , n}$ or $S_{n+1}$ must be infinite.

Let us analyze the case that $S_{1, \ldots , n}$ is infinite first. Then, $S_{1, \ldots , n}$ is an infinite bounded space of $\R^n$. So, by the induction hypothesis, it has a limit point $l_{1, \ldots , n}=(l_1, \ldots , l_n)$.

By definition, for every $\epsilon > 0$, there is an $s_\epsilon \in (B_\epsilon(l) \setminus \{l\}) \cap S_{1, \ldots , n}$. To this $s_\epsilon$, which is in $S_{1, \ldots , n}$, there corresponds the set of all $(n+1)^\text{th}$ coordinates of $S$-elements that have $s_\epsilon=(s_{\epsilon,1}, \ldots , s_{\epsilon, n})$ as their first $n$ coordinates: $\tilde{S}_{\epsilon, n+1} = \pi_{n+1}(\pi_{1, \ldots , n}^{-1}(s_\epsilon) \cap S) \subseteq S_{n+1}$ and collect every element of such sets in one set: $\tilde{S}_{n+1} = \bigcup\limits_{\epsilon > 0}\tilde{S}_{\epsilon, n+1} = \pi_{n+1}(\left[\bigcup\limits_{\epsilon > 0}\pi_{1, \ldots , n}^{-1}(s_\epsilon)\right] \cap S) \subseteq S_{n+1}$.

Now, if $\tilde{S}_{n+1}$ is

$\blacksquare$

Also known as

Some sources refer to this result as the Weierstrass-Bolzano theorem.

Source of Name

This entry was named for Bernhard Bolzano and Karl Weierstrass.

Sources

• 1981: Murray R. Spiegel: Theory and Problems of Complex Variables (SI ed.) ... (previous) ... (next): $1$: Complex Numbers: Point Sets: $1$. Weierstrass-Bolzano Theorem