Bolzano-Weierstrass Theorem/General Form

From ProofWiki
Jump to navigation Jump to search


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


The proof of this theorem will be given as a series of lemmata 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 and its related Euclidean topology.

Lemma $0$

Let $S' \subseteq S \subseteq \R$.

Then every limit point of $S'$ is a limit point of $S$.


The above trivial lemma is given purely for the sake of argument completeness.

It is assumed implicitly in all the proofs below.

Lemma $1$

Let $S$ be a non-empty subset of the real numbers such that its supremum $\map \sup S$ exists.

Let $\map \sup S \notin S$.

Then $\map \sup S$ is a limit point of $S$.


Lemma $2$

Let $S$ be a non-empty subset of the real numbers such that its infimum $\map \inf s$ exists.

Let $\map \inf s \notin S$.

Then $\map \inf s$ is a limit point of $S$.


Throughout the rest of the proof:

$\tilde s$ is used to mean $\map \sup S$
$\underline s$ is used to mean $\map \inf S$.

Lemma $3$

Every bounded, infinite subset $S$ of $\R$ has at least one limit point.


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$

Bolzano-Weierstrass Theorem/Lemma 4 $\Box$

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$.


Lemma $5$

Bolzano-Weierstrass Theorem/Lemma 5 $\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 {\ds \sum_{s \mathop = i}^j \paren {x_s - y_s}^2} > K$ where we get the formula $\size {x - y} = \sqrt {\ds \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 {\ds \sum_{s \mathop = 1}^n \paren {x_s - y_s}^2} \ge \sqrt {\ds \sum_{s \mathop = i}^j \paren {x_s - y_s}^2} > K$ contradicting the fact that $S$ is a bounded space.


Lemma $6$

Bolzano-Weierstrass Theorem/Lemma 6 $\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:

$\ds \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.


Recall the statement of the theorem:

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

We proceed by the Principle of Mathematical 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} = \ds \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 the Bolzano-Weierstrass Theorem as the Weierstrass-Bolzano theorem.

Source of Name

This entry was named for Bernhard Bolzano and Karl Weierstrass.