Sequentially Compact Metric Space is Totally Bounded

From ProofWiki
Jump to: navigation, search

Theorem

Let $M = \left({A, d}\right)$ be a metric space.

Let $M$ be sequentially compact.


Then $M$ is totally bounded.


Proof 1

Let $\epsilon \in \R_{>0}$ be a strictly positive real number.

By definition, $M$ is totally bounded only if there exists a finite $\epsilon$-net for $M$.


We use a Proof by Contradiction.

That is, suppose that there exists no finite $\epsilon$-net for $M$.

The aim is to construct an infinite sequence $\left \langle {x_n} \right \rangle_{n \ge 1}$ in $A$ that has no convergent subsequence.


For all natural numbers $n \ge 1$, define the set:

$\mathcal S_n = \left\{{F \subseteq A: \left\vert{F}\right\vert = n: \forall x, y \in F: x \ne y \implies d \left({x, y}\right) \ge \epsilon}\right\}$

where $\left\vert{F}\right\vert$ denotes the cardinality of $F$.

We use the Principle of Mathematical Induction to prove that $\mathcal S_n$ is non-empty.


It is vacuously true that any singleton $\left\{{x}\right\} \subseteq A$ is an element of $\mathcal S_1$.

Since $A$ is non-empty by the definition of a metric space, it follows from Existence of Singleton Set that $\mathcal S_1$ is non-empty.


Let $F \in \mathcal S_n$.

By definition, $F$ is finite.

So $F$ is not an $\epsilon$-net for $M$, by hypothesis.

Hence, there exists an $x \in A$ such that:

$\forall y \in F: d \left({x, y}\right) \ge \epsilon$

Note that, by axiom $\left({M1}\right)$ for a metric:

$x \notin F$

Consider the set:

$F' := F \cup \left\{{x}\right\}$.

Then:

$\left\vert{F'}\right\vert = n + 1$

and by axiom $\left({M3}\right)$ for a metric:

$F' \in \mathcal S_{n+1}$


Thus, we have proven that $\mathcal S_n$ is non-empty for all natural numbers $n \ge 1$.


Therefore, using the axiom of countable choice, we can obtain an infinite sequence $\left\langle{F_n}\right\rangle_{n \ge 1}$ such that:

$\forall n \in \N_{\ge 1}: F_n \in \mathcal S_n$

From Countable Union of Countable Sets is Countable, there exists an injection:

$\displaystyle \phi: \bigcup_{n \mathop \ge 1} F_n \to \N$


We now construct an infinite sequence $\left\langle{x_n}\right\rangle_{n \ge 1}$ in $A$.


To do this, we use the Principle of Recursive Definition to define the sequence $\left\langle{\left({x_1, x_2, \ldots, x_n}\right)}\right\rangle_{n \ge 1}$ of ordered $n$-tuples.

Let $x_1 \in F_1$.

Suppose that $x_1, x_2, \ldots, x_n$ have been defined, and let:

$T_n = \left\{{x_1, x_2, \ldots, x_n}\right\}$

Define:

$D_n = \left\{{x \in F_{n+1}: \forall y \in T_n: d \left({x, y}\right) \ge \dfrac \epsilon 2}\right\}$


Using a Proof by Contradiction, we show that $D_n$ is non-empty.

For all $x \in F_{n+1}$, define:

$C_n \left({x}\right) = \left\{{y \in T_n: d \left({x, y}\right) < \dfrac \epsilon 2}\right\}$

Let $x, x' \in F_{n+1}$ be distinct.

Let $y \in C_n \left({x}\right)$.

Then it follows from:

the definition of $F_{n+1}$
axioms $\left({M2}\right)$ and $\left({M3}\right)$ for a metric

that:

$d \left({x', y}\right) \ge d \left({x, x'}\right) - d \left({x, y}\right) > \dfrac \epsilon 2$

Hence, $y \notin C_n \left({x'}\right)$.

That is, the indexed family of sets:

$\left\langle{C_n \left({x}\right)}\right\rangle_{x \in F_{n + 1}}$

is pairwise disjoint.

Suppose that $D_n$ is empty.

That is:

$\forall x \in F_{n+1}: C_n \left({x}\right)$ is non-empty

Then, from Cardinality is Additive Function, Finite Union of Sets in Additive Function, and Cardinality of Subset of Finite Set, we have:

$\displaystyle \left\vert{F_{n+1}}\right\vert \le \sum_{x \mathop \in F_{n+1}} \left\vert{C_n \left({x}\right)}\right\vert \le \left\vert{T_n}\right\vert < \left\vert{F_{n+1}}\right\vert$

which is a contradiction.



From the well-ordering principle, we have that $\left({\N, \le}\right)$ is a well-ordered set.

Let $\le_{\phi}$ be the ordering induced by $\phi$.

Then $\le_{\phi}$ is a well-ordering.

We define $x_{n+1}$ as the (unique) $\le_{\phi}$-smallest element of $D_n$.


By construction:

$\forall m, n \in \N_{>0}: m \le n \implies d \left({x_{n+1}, x_m}\right) \ge \dfrac \epsilon 2$

Hence, by induction, it follows from axiom $\left({M3}\right)$ for a metric that:

$\forall m, n \in \N_{>0}: m \ne n \implies d \left({x_m, x_n}\right) \ge \dfrac \epsilon 2$

Therefore, the sequence $\left\langle{x_n}\right\rangle$ has no Cauchy subsequence.

From Convergent Sequence is Cauchy Sequence, $\left\langle{x_n}\right\rangle$ has no convergent subsequence either.

Thus, by definition, $M$ is not sequentially compact.

But this contradicts the original assumption that $M$ is sequentially compact.

Thus the assumption that there exists no finite $\epsilon$-net for $M$ was false.

Therefore, by definition, $M$ is totally bounded.

Hence the result.

$\blacksquare$


Proof 2

Let $\epsilon \in \R_{>0}$ be a strictly positive real number.

By definition, $M$ is totally bounded only if there exists a finite $\epsilon$-net for $M$.


We use a Proof by Contraposition.

To that end, suppose that there exists no finite $\epsilon$-net for $M$.

The aim is to construct an infinite sequence $\left \langle {x_n} \right \rangle_{n \in \N}$ in $A$ that has no convergent subsequence.


Suppose that $x_0, x_1, \ldots, x_r \in A$ have been defined such that:

$\forall m, n \in \left\{{0, 1, \ldots, r}\right\}: m \ne n \implies d \left({x_m, x_n}\right) \ge \epsilon$

That is, any two distinct elements of $\left\{{x_0, x_1, \ldots, x_r}\right\}$ are at least $\epsilon$ apart.

By hypothesis, there exists no finite $\epsilon$-net for $M$.

Specifically, $\left\{{x_0, x_1, \ldots, x_r}\right\}$ is therefore not an $\epsilon$-net for $M$.

So, by definition of a $\epsilon$-net:

$\displaystyle A \nsubseteq \bigcup_{i \mathop = 0}^r B_\epsilon \left({x_i}\right)$

where $B_\epsilon \left({x_i}\right)$ denotes the open $\epsilon$-ball of $x_i$ in $M$.


Thus there must exist $x_{r+1} \in A$ such that:

$\displaystyle x_{r+1} \notin \bigcup_{i \mathop = 0}^r B_\epsilon \left({x_i}\right)$

That is:

$\exists x_{r+1} \in A: \forall m, n \in \left\{{0, 1, \ldots, r, r + 1}\right\}: m \ne n \implies d \left({x_m, x_n}\right) \ge \epsilon$


Thus, by induction, the infinite sequence $\left \langle {x_n} \right \rangle$ in $A$ has been constructed such that:

$\forall m, n \in \N: m \ne n \implies d \left({x_m, x_n}\right) \ge \epsilon$

Thus $\left \langle {x_n} \right \rangle$ has no Cauchy subsequence.

Since a convergent sequence is Cauchy, it has no convergent subsequence either.

Thus, by definition, $M$ is not sequentially compact.

From Rule of Transposition, if $M$ is sequentially compact, then there exists no finite $\epsilon$-net for $M$.

So if $M$ is sequentially compact, it is certainly not totally bounded.

$\blacksquare$


Axiom of Countable Choice

This theorem depends on the Axiom of Countable Choice.

Although not as strong as the Axiom of Choice, the Axiom of Countable Choice is similarly independent of the Zermelo-Fraenkel axioms.

As such, mathematicians are generally convinced of its truth and believe that it should be generally accepted.


Also see