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 of limit point:
- $\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$ is 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 the proof is complete.
- 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:
\(\ds \bigcup_{y \mathop \in \map f S} \paren {\map {f^{-1} } y \cap S}\) | \(=\) | \(\ds \paren {\bigcup_{y \mathop \in \map f S} \map {f^{-1} } y} \cap S\) | Intersection Distributes over Union | |||||||||||
\(\ds \) | \(=\) | \(\ds \map {f^{-1} } {\map f S} \cap S\) | Preimage of Union under Mapping/Family of Sets | |||||||||||
\(\ds \) | \(=\) | \(\ds 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 of limit point, 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