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 Continuum 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 \set {\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 \set {\tilde s_1} = \sup S \setminus \set {\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 \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 \N$. In that case, $\tilde s_k \in S_k$ and we get a sequence $\tilde S = \sequence {\tilde s_k}_{k \mathop \in \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 \set {\tilde s_0, \ldots , \tilde s_{k - 1} }$ when $k \ge 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 \set {\tilde s_0, \ldots , \tilde s_k} = S_k \setminus \set {\tilde s_k}$. So, firstly, $\tilde s_{k + 1} \ne \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 \ge \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 \le n$. Then, for any set $X$,

There is a function $\pi_{1, \ldots, m}: X^n \to X^m$ such that $\map {\pi_{1, \ldots, m} } {x_1, \ldots, x_m, \ldots, x_n} = \tuple {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 $\map {\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$th element of that coordinate.

In general, for positive integers $i \le j < n$, there is a function $\pi_{i, \ldots, j}: X^n \to X^{j - i + 1}$ such that $\map {\pi_{i, \ldots, j} } {x_1, \ldots, x_i, \ldots, x_j, \ldots, x_n} = \tuple{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 \map {\pi_{1, \ldots, m} } S \times \map {\pi_{m + 1, \ldots , n} } S$.

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

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

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

$\Box$

Lemma 5: For positive integers $i \le j \le n$ and $S \subseteq \R^n$, if $S$ is a bounded space in $\R^n$, then so is $\map {\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 = \tuple {x_i, \ldots, x_j}$ and $y = \tuple {y_i, \ldots, y_j}$ in $\map {\pi_{i, \ldots, j} } S$ such that $\map d {x, y} = \size {x - y} = \sqrt {\displaystyle \sum_{s \mathop = i}^j \paren {x_s - y_s}^2} > K$ where we get the formula $\size {x - y} = \sqrt {\displaystyle \sum_{s \mathop = i}^j \paren {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 $\map {\pi_{i, \ldots, j} } S$, there are points $x' = \tuple {x_1, \ldots, x_i, \ldots, x_j, \ldots, x_n}$ and $y' = \tuple {y_1, \ldots, y_i, \ldots, y_j, \ldots, y_n}$ in $S$ from which $x$ and $y$ originated as coordinate components. Therefore, $\map d {x', y'} = \size {x' - y} = \sqrt {\displaystyle \sum_{s \mathop = 1}^n \paren {x_s - y_s}^2} \ge \sqrt {\displaystyle \sum_{s \mathop = i}^j \paren {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 $\map f S$ is finite, then there exists some $y \in \map f S$ such that $\map {f^{-1} } y \cap S$ is infinite. Here, $\map {f^{-1} } y$ is the preimage of the element $y$.

Proof: If there weren't such an element in $\map f S$, then for all $y \in \map f S$, $\map {f^{-1} } y \cap S$ would be finite. Also, since $\map 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:

$\displaystyle \bigcup_{y \mathop \in \map f S} \paren {\map {f^{-1} } y \cap S} = \paren {\map {f^{-1} } {y_1} \cap S} \cup \cdots \cup \paren {\map {f^{-1} } {y_n} \cap S}$

must be finite.

But notice that:

\(\displaystyle \bigcup_{y \mathop \in \map f S} \paren {\map {f^{-1} } y \cap S}\)

\(=\)

\(\displaystyle \paren {\bigcup_{y \mathop \in \map f S} \map {f^{-1} } y} \cap S\)

Intersection Distributes over Union

\(\displaystyle \)

\(=\)

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

Preimage of Union under Mapping/Family of Sets

\(\displaystyle \)

\(=\)

\(\displaystyle S\)

Subset of Domain is Subset of Preimage of Image

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} = \map {\pi_{1, \ldots, n} } S$ and $S_{n + 1} = \map {\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} = \tuple {l_1, \ldots, l_n}$.

By definition, for every $\epsilon > 0$, there is an $s_\epsilon \in \paren {\map {B_\epsilon} l \setminus \set l} \cap S_{1, \ldots, n}$. To this $s_\epsilon$, which is in $S_{1, \ldots, n}$, there corresponds the set of all $\paren {n + 1}$th coordinates of $S$-elements that have $s_\epsilon = \tuple {s_{\epsilon, 1}, \ldots, s_{\epsilon, n} }$ as their first $n$ coordinates: $\tilde S_{\epsilon, n + 1} = \map {\pi_{n + 1} } {\map {\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} = \displaystyle \bigcup_{\epsilon \mathop > 0} \tilde S_{\epsilon, n + 1} = \map {\pi_{n + 1} } {\paren {\bigcup_{\epsilon \mathop > 0} \map {\pi_{1, \ldots, n}^{-1} } {s_\epsilon} } \cap S} \subseteq S_{n + 1}$.

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

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