Bolzano-Weierstrass Theorem/General Form

From ProofWiki
Jump to navigation Jump to search


This article needs to be tidied.
In particular: $\LaTeX$ now compliant. It remains to style the structure. Loads more to do.
Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Tidy}} from the code.



This article needs to be linked to other articles.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.



This page has been identified as a candidate for refactoring of medium complexity.
In particular: Extract lemmata
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Refactor}} from the code.


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

$\Box$


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

$\Box$


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

$\Box$


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.

$\Box$


Although this article appears correct, it's inelegant. There has to be a better way of doing it.
In particular: cut out the waffle
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Improve}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


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

$\Box$


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.

$\Box$


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.


$\Box$


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


This needs considerable tedious hard slog to complete it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Finish}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.



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.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Bolzano-Weierstrass_Theorem/General_Form&oldid=581050"