Completeness and compactness · Selected prerequisite proofs

L7.4.2: A convergent metric sequence is Cauchy

Proposition 7.4.2.

A convergent sequence in a metric space is Cauchy.

Proof.

Suppose

\{ x_n \}_{n=1}^\infty

converges to

p\text{.}

Given

\epsilon > 0\text{,}

there is an

M

such that for all

n \geq M\text{,}

we have

d(p,x_n) < \nicefrac{\epsilon}{2}\text{.}

Hence, for all

n,k \geq M\text{,}

we have

d(x_n,x_k) \leq d(x_n,p) + d(p,x_k) < \nicefrac{\epsilon}{2} + \nicefrac{\epsilon}{2} = \epsilon\text{.}

L7.4.4: Euclidean completeness by coordinatewise real completeness

Proposition 7.4.4.

The space

\R^n

with the standard metric is a complete metric space.

Proof.

Let

\{ x_m \}_{m=1}^\infty

be a Cauchy sequence in

\R^n\text{,}

where

x_m = \bigl(x_{m,1},x_{m,2},\ldots,x_{m,n}\bigr) \in \R^n\text{.}

As the sequence is Cauchy, given

\epsilon > 0\text{,}

there exists an

M

such that for all

i,j \geq M\text{,}

\begin{equation*} d(x_i,x_j) < \epsilon. \end{equation*}

Fix some

k=1,2,\ldots,n\text{.}

For

i,j \geq M\text{,}

\begin{equation*} \bigl\lvert x_{i,k} - x_{j,k} \bigr\rvert = \sqrt{{\bigl(x_{i,k} - x_{j,k}\bigr)}^2} \leq \sqrt{\sum_{\ell=1}^n {\bigl(x_{i,\ell}-x_{j,\ell}\bigr)}^2} = d(x_i,x_j) < \epsilon . \end{equation*}

Hence, the sequence

\{ x_{m,k} \}_{m=1}^\infty

is Cauchy. As

\R

is complete, the sequence converges; there exists a

y_k \in \R

such that

y_k = \lim_{m\to\infty} x_{m,k}\text{.}

Write

y = (y_1,y_2,\ldots,y_n) \in \R^n\text{.}

By Proposition 7.3.9,

\{ x_m \}_{m=1}^\infty

converges to

y \in \R^n\text{,}

and hence

\R^n

is complete.

L7.4.9: Compact sets are closed and bounded, with the empty-set case explicit locally

Proposition 7.4.9.

Let

(X,d)

be a metric space. If

K \subset X

is compact, then

K

is closed and bounded.

Proof.

First, we prove that a compact set is bounded. Fix

p \in X\text{.}

We have the open cover

\begin{equation*} K \subset \bigcup_{n=1}^\infty B(p,n) = X . \end{equation*}

If

K

is compact, then there exists some set of indices

n_1 < n_2 < \ldots < n_m

such that

\begin{equation*} K \subset \bigcup_{j=1}^m B(p,n_j) = B(p,n_m) . \end{equation*}

As

K

is contained in a ball,

K

is bounded. See the left-hand side of Figure 7.11.

Next, we show that a set that is not closed is not compact. Suppose

\widebar{K} \neq K\text{,}

that is, there is a point

x \in \widebar{K} \setminus K\text{.}

If

y \neq x\text{,}

then

y \notin C(x,\nicefrac{1}{n})

for

n \in \N

such that

\nicefrac{1}{n} < d(x,y)\text{.}

Furthermore,

x \notin K\text{,}

so

\begin{equation*} K \subset \bigcup_{n=1}^\infty {C(x,\nicefrac{1}{n})}^c . \end{equation*}

A closed ball is closed, so its complement

{C(x,\nicefrac{1}{n})}^c

is open, and we have an open cover. If we take any finite collection of indices

n_1 < n_2 < \ldots < n_m\text{,}

then

\begin{equation*} \bigcup_{j=1}^m {C(x,\nicefrac{1}{n_j})}^c = {C(x,\nicefrac{1}{n_m})}^c \end{equation*}

As

x

is in the closure of

K\text{,}

then

C(x,\nicefrac{1}{n_m}) \cap K \neq \emptyset\text{.}

So there is no finite subcover and

K

is not compact. See the right-hand side of Figure 7.11.

L7.4.10: Lebesgue covering lemma proved directly from sequential compactness

Lemma 7.4.10. Lebesgue covering lemma.

Let

(X,d)

be a metric space and

K \subset X\text{.}

Suppose every sequence in

K

has a subsequence convergent in

K\text{.}

Given an open cover

\{ U_\lambda \}_{\lambda \in I}

of

K\text{,}

there exists a

\delta > 0

such that for every

x \in K\text{,}

there exists a

\lambda \in I

with

B(x,\delta) \subset U_\lambda\text{.}

Proof.

We prove the lemma by contrapositive. If the conclusion is not true, then there is an open cover

\{ U_\lambda \}_{\lambda \in I}

of

K

with the following property. For every

n \in \N\text{,}

there exists an

x_n \in K

such that

B(x_n,\nicefrac{1}{n})

is not a subset of any

U_\lambda\text{.}

Take any

x \in K\text{.}

There is a

\lambda \in I

such that

x \in U_\lambda\text{.}

As

U_\lambda

is open, there is an

\epsilon > 0

such that

B(x,\epsilon) \subset U_\lambda\text{.}

Take

M

such that

\nicefrac{1}{M} < \nicefrac{\epsilon}{2}\text{.}

If

y \in B(x,\nicefrac{\epsilon}{2})

and

n \geq M\text{,}

then

\begin{equation*} B(y,\nicefrac{1}{n}) \subset B(y,\nicefrac{1}{M}) \subset B(y,\nicefrac{\epsilon}{2}) \subset B(x,\epsilon) \subset U_\lambda , \end{equation*}

where

B(y,\nicefrac{\epsilon}{2}) \subset B(x,\epsilon)

follows by triangle inequality. See Figure 7.12. Thus

y \neq x_n\text{.}

In other words, for all

n \geq M\text{,}

x_n \notin B(x,\nicefrac{\epsilon}{2})\text{.}

The sequence cannot have a subsequence converging to

x\text{.}

As

x \in K

was arbitrary, we are done.

L7.4.11: Sequential compactness and the finite-subcover definition are equivalent

Theorem 7.4.11.

Let

(X,d)

be a metric space. Then

K \subset X

is compact if and only if every sequence in

K

has a subsequence converging to a point in

K\text{.}

Proof.

Claim: Let $K \subset X$ be a subset of $X$ and $\{ x_n \}_{n=1}^\infty$ a sequence in $K\text{.}$ Suppose that for each $x \in K\text{,}$ there is a ball $B(x,\alpha_x)$ for some $\alpha_x > 0$ such that $x_n \in B(x,\alpha_x)$ for only finitely many $n \in \N\text{.}$ Then $K$ is not compact.

Proof of the claim: Notice

\begin{equation*} K \subset \bigcup_{x \in K} B(x,\alpha_x) . \end{equation*}

Any finite collection of these balls contains at most finitely many elements of

\{ x_n \}_{n=1}^\infty\text{,}

and so there must be an

x_n \in K

not in their union. Hence,

K

is not compact and the claim is proved.

So suppose that

K

is compact and

\{ x_n \}_{n=1}^\infty

is a sequence in

K\text{.}

Then there exists an

x \in K

such that for all

\delta > 0\text{,}

B(x,\delta)

contains

x_n

for infinitely many

n \in \N\text{.}

We define the subsequence inductively. The ball

B(x,1)

contains some

x_k\text{,}

so let

n_1 \coloneqq k\text{.}

Suppose

n_{j-1}

is defined. There must exist a

k > n_{j-1}

such that

x_k \in B(x,\nicefrac{1}{j})\text{.}

Define

n_j \coloneqq k\text{.}

We now possess a subsequence

\{ x_{n_j} \}_{j=1}^\infty\text{.}

Since

d(x,x_{n_j}) < \nicefrac{1}{j}\text{,}

Proposition 7.3.5 says

\lim_{j\to\infty} x_{n_j} = x\text{.}

For the other direction, suppose every sequence in

K

has a subsequence converging in

K\text{.}

Take an open cover

\{ U_\lambda \}_{\lambda \in I}

of

K\text{.}

Using the Lebesgue covering lemma above, find a

\delta > 0

such that for every

x \in K\text{,}

there is a

\lambda \in I

with

B(x,\delta) \subset U_\lambda\text{.}

Pick

x_1 \in K

and find

\lambda_1 \in I

such that

B(x_1,\delta) \subset U_{\lambda_1}\text{.}

If

K \subset U_{\lambda_1}\text{,}

we stop as we have found a finite subcover. Otherwise, there must be a point

x_2 \in K \setminus U_{\lambda_1}\text{.}

Note that

d(x_2,x_1) \geq \delta\text{.}

There must exist some

\lambda_2 \in I

such that

B(x_2,\delta) \subset U_{\lambda_2}\text{.}

We work inductively. Suppose

\lambda_{n-1}

is defined. Either

U_{\lambda_1} \cup U_{\lambda_2} \cup \cdots \cup U_{\lambda_{n-1}}

is a finite cover of

K\text{,}

in which case we stop, or there must be a point

x_n \in K \setminus \bigl( U_{\lambda_1} \cup U_{\lambda_2} \cup \cdots \cup U_{\lambda_{n-1}}\bigr)\text{.}

Note that

d(x_n,x_j) \geq \delta

for all

j = 1,2,\ldots,n-1\text{.}

Next, there must be some

\lambda_n \in I

such that

B(x_n,\delta) \subset U_{\lambda_n}\text{.}

See Figure 7.13.

A shaded region with a solid boundary is marked K. Four points in K are marked x sub 1, x sub 2, x sub 3, and x sub 4. Circles of radius delta are drawn centered at x sub 1, x sub 2, and x sub 3. Around each of these circles there are three regions outlined in dotted line marked U sub lambda sub 1, U sub lambda sub 2, and U sub lambda sub 3. The discs, and therefore the surrounding regions, seem to be slowly covering the set K entirely on the left-hand side of the picture. — Figure 7.13. Covering $K$ by $U_{\lambda}\text{.}$ The points $x_1,x_2,x_3,x_4\text{,}$ the three sets $U_{\lambda_1}\text{,}$ $U_{\lambda_2}\text{,}$ $U_{\lambda_3}\text{,}$ and the first three balls of radius $\delta$ are drawn.

Either at some point we obtain a finite subcover of

K\text{,}

or we obtain an infinite sequence

\{ x_n \}_{n=1}^\infty

as above. For contradiction, suppose that there is no finite subcover and we have the sequence

\{ x_n \}_{n=1}^\infty\text{.}

For all

n

and

k\text{,}

n \neq k\text{,}

we have

d(x_n,x_k) \geq \delta\text{.}

So no subsequence of

\{ x_n \}_{n=1}^\infty

is Cauchy. Hence, no subsequence of

\{ x_n \}_{n=1}^\infty

is convergent, which is a contradiction.

Two diagrams. A set K is given as a shaded region with solid boundary. In the left diagram, a point p is highlighted together with 3 nested open balls (circles in this case) of radius 1, 2, and 3 all centered at p with dotted boundary. The set K lies in the largest one. In the right diagram, the background of the diagram is shaded. A point x that is on the boundary of K is shown, and 4 closed balls are drawn as circles with the inside shaded in lighter and lighter gray, indicating that we are looking at the complements. The outer ball is of radius 1, then there is a ball of radius one half, then a ball of radius one third, then a ball of radius one fourth. We note that as x sits on the boundary, the complements of the balls cover more and more of K. On the other hand we also note that K has nonempty intersection with all the closed balls. — Figure 7.11. Proving compact set is bounded (left) and closed (right).

A diagram of a shaded open set U sub lambda. A point x in U sub lambda is marked and a ball of radius epsilon centered at x is drawn and this ball sits within U sub lambda. A ball of radius epsilon over 2 centered at x is also drawn which sits within the larger ball. A point y in the smaller ball is marked and a ball of radius epsilon over 2 centered at y is shown. We note that this ball centered at y sits entirely within the ball of radius epsilon centered at x, the largest ball, and hence also within U sub lambda. One last small ball of radius 1 over n centered at y is shown that sits within the epsilon over 2 ball centered at y. — Figure 7.12. Proof of Lebesgue covering lemma. Note that $B(y,\nicefrac{\epsilon}{2}) \subset B(x,\epsilon)$ by triangle inequality.