571: Ch 3 Completeness
===

# Complete metric spaces

Throughout this section all spaces are metric with the default metric on $X$ denoted by $d_X$.

**Notation:** the following notation will be used in this note.
- $(x_i)_{i\in\mathbb{N}}$, $(x_i)_{i=0}^\infty$, $(x_i)_i$, or $(x_i)$ are all shorthand for the sequence $i\mapsto x_i$.
- $(x_{i_j})$ is a subsequence of $(x_i)$ implies $i_0<i_1<\cdots$.

**Definition:**
1. $(x_i)$ is a ***Cauchy-sequence*** (C-seq) provided:
$$
(\forall \epsilon>0)\,(\exists N>0)\,(\forall i,j>N)\,(d_X(x_i,x_j)<\epsilon)
$$
2. A metric space $X$ is ***complete*** if all C-seqs converge.

**Non Example** A typical example of a metric space that fails to be complete is $\mathbb Q$. Let $\alpha$ be irrational and choose any $r_i\to \alpha$ where $r_i\in\mathbb Q$, then $(r_i)$ is a C-seq and there is no limit in $\mathbb Q$. We will see later that one way of constructing $\mathbb R$ is to *add* limits to all C-seqs in $\mathbb Q$.

**Lemma** If $(x_{i_k})$ a subsequence of a C-seq $(x_i)$, then $(x_{i_k})$ is also a C-seq. Moreover, $x_{i_k}\to x\iff x_i\to x$.

**Note** This says that a C-seq converges iff any / all of its subsequences converge and these all converge to the same element of $X$.

**Proof:** Let $\epsilon > 0$ and let $N>0$ and $M>0$ be so that $d_X(x_{i_k},x)<\epsilon/2$ for $i_k>M$ and $d_X(x_i,x_j)<\epsilon/2$ for $i,j>N$. Let K > M,N so that for $i_k,j\geq K$, then $d_X(x_j,x)\leq d_X(x_{i_k},x)+d_X(x_{i_k},j)<\epsilon$. This implies $x_j\to x$ as desired.
❏

**Definition** We say that two C-seqs $(x_i)$ and $(y_i)$ are **equivalent** and write $(x_i)\sim(y_i)$ if there is a third C-seq $(z_j)$ so that $x_i=z_{j_i}$ and $y_i=z_{k_i}$ so that $(x_i)$ and $(y_i)$ both sit as subsequences inside $(z_j)$.

<a id="ex1"></a>
**Exercise** Show that if $(x_i)$ is a C-seq, then the following are equivalent
* $(y_i)$ is a C-seq and $(x_i)\sim (y_i)$.
* $\lim_i d_X(x_i,y_i)=0$.

**Exercise** Show that $\sim$ is an equivalence relation on $\text{C-seq}(X)$.

Due to the exercise, the choice of $(z_j)$ does not matter, so we could take $z_{2j}=x_j$ and $z_{2j+1}=y_j$.

We will use the simpler notation $[x_i]$ for the equivalence class of a C-seq $(x_i)$, that is,
$$
[x_i]=(x_i)/\sim=\{(x_i')\mid (x_i)\sim(x_i')\}
$$

## In metric spaces: compact = complete + totally bounded

**Definition** A metric space $(X,d_X)$ is *totally bounded* iff for all $\delta>0$, there is $x_1,\ldots,x_k\in X$ so that $\{B_\delta(x_i)\mid i=1,\ldots,n\}$ is an open cover of $X$.

The the set $x_1,\ldots,x_n$ in the definition is called a *$\delta$-net*.

**Theorem:** If $(X,d_X)$ is compact, then for every $\delta>0$, there is a $\delta$-net.

**Proof:** $\mathscr{O}_\delta = \{B_\delta(x)\mid x\in X\}$ is clearly an open cover of $X$. Since $X$ is compact there is a finite subcover determined by the centers $x_1,\ldots,x_n$ and this is the $\delta$-net.

**Definition:** A metric space is called *totally bounded* if for every $\delta>0$, there is a $\delta$-net.

**Theorem:** A metric space is compact iff it is complete and totally bounded.

**Proof: (The "only if" direction.)** Assume $X$ is compact. The preceding theorem shows that $X$ is totally bounded so we must verify completeness. Since $X$ is compact it is sequentially compact and thus every C-seq has a limit, thus it is complete.

**(The "if" direction.)** Assume $X$ is complete and totally bounded. We have already argued that for metric spaces: compact = squentially compact. So let $(x_i)$ be a sequence from $X$. We must show that there is a convergent subsequence as this would show that $X$ is sequentially compact. By assumption there is a 1-net for $X$. For some $y_1$ in the net, $N_{1}(y_1)$ must contain an infinite subsequence $(x_{i^1_k})_k$. Repeating this we get a subsequence $(x_{i^2_k})_k$ of $(x_{i^1_k})_k$ contained in some $N_{1/2}(y_2)$ using a 1/2-net. We continue this getting $(x_{i^{n+1}_k})_k\subset (x_{i^n_k})_k$ so that $(x_{i^n_k})_k$ is contained in $N_{1/n}(y_n)$ for all $n$. Diagonalizing and taking $z_j=x_{i^j_1}$ gives a subsequece of $(x_i)$ so that $(z_j)_{j>n}\subset N_{1/n}(y_n)$ for all $n$ and thus $z_j$ is a C-seq and has a limit $x$ by completeness. This is what we had to verify!
❏

**Note:** In a complete metric space that is not compact we get a *measure* of non-compactness. First note that if there is no $\delta$-net and $\delta'<\delta$, then there is no $\delta'$-net. Define
$$
0\le\delta_X=\sup\{\delta\ge0\mid \text{there is no }\delta\text{-net for }X\}\le\infty
$$
so that $\delta_X=0$ iff $X$ is totally bounded and $\delta_X<\infty$ iff $X$ is bounded. If $\delta_Y>\delta_X$ we can view $Y$ as being further away from compact than $X$. This makes sense at least when $Y\subseteq X$ or $X\subseteq Y$.

**Exercise** Explain why if $X$ is a complete metric space, then $K\subseteq X$ is compact iff $K$ is closed and totally bounded. (A generalization of Heine-Borel.)

## Completion of a metric space

Here we see that to every metric space $X$ there is a "unique" metric space $Y$ that "contains" $X$ as a dense subset. This space is called the *completion of $X$*. As a canonical example, $\mathbb{R}$ is the unique completion of $\mathbb{Q}$.

### Uniqueness of the completion of X

Suppose $Y$ and $Y'$ are complete metric spaces containing $X$ densely, then we will show $Y\underset{\tiny{\text{iso}}}\simeq Y'$ where this means that there is $f:Y\to Y'$ that is an isomorphism of metric spaces, an *isometry*, that is, $f$ is a bijection and the metric is preserved, i.e., $d_{Y'}(f(a),f(b))=d_Y(a,b)$.

**Note** We are assuming here that $d_X=d_Y|_{X\times X}$ and $d_X=d_Y'|_{X\times X}$ so that $X$ is the induced metric space from both $Y$ and $Y'$.

**Proof of uniqueness of the completion:** Let $(x_i)$ be a C-seq of $X$ and let $x_i\to y$ in $Y$ and $x_i\to y'$ in $Y'$. Define $f(y)=y'$.

**Claim 1 ($f$ is well defined):** Suppose $x_i\to y$ and $x'_i\to y$, then set $\hat x_{2i}=x_i$ an $\hat x _{2i+1}=x'_i$, this new sequence $(\hat x_i)$ is a C-seq and so in $Y'$, $(x_i)$ and $(x'_i)$ have the same limit, $y'$, as they are subsequences of a single C-seq. This shows that the map $y\mapsto y'$ is independent of the choice of C-seq converging to $y$.

**Claim 2 ($f$ is 1-1):** If $y_0 \neq y_1$ and $x^0_i\to y_0$ while $x^1_i\to y_1$ for C-seqs $(x^j_i)$ for $j=0,1$, then $(x_i^0)\not\sim (x_i^1)$ and so in $Y'$, $f(y_0)= y_0'\neq y_1'=f(y_1)$.

**Claim 3 ($f$ is onto):** Let $y'\in Y'$, then as $X$ is dense in $Y'$ we get C-seq $(x_i)$ so that $x_i\to y'$. But then in $Y$, $x_i\to y$, by the completeness of $Y$, and $f(y)=y'$ by the definition of $f$.

**Claim 4 ($f$ preserves the metric):** Let $y_0,y_1\in Y$ and let $(x_i^j)$ be a C-seq so that $x_i^j\to y_j$ for $j=0,1$. We show that $d_Y(y_0,y_1)=\lim_{i\to\infty}d_X(x_i^0,x_i^1)$. By assumption for $x,x'\in X$, $d_X(x,x')=d_Y(x,x')$ and as $x_i^j\to y_j$ we have $d_Y(x_i^j,y_j)\to 0$ as $i\to\infty$. Take $\epsilon>0$ and fix $N>0$ so that $d_Y(x_i^j,y_j)<\epsilon/2$ for $i>N$. Now let $i>\max(M,N)$, we have
$$
d_Y(y_0,y_1)\leq d_Y(x^0_i,y_0) + d_Y(x^0_i,x^1_i) + d_Y(x^1_i,y_1)
$$
This gives
$$
d_Y(y_0,y_1)-d_Y(x_i^0,x_i^1)\leq d_Y(x^0_i,y_0) + d_Y(x^1_i,y_1)< \epsilon
$$
Similarly we can get
$$
d_Y(x_i^0,x_i^1)-d_Y(y_0,y_1)\leq d_Y(x^0_i,y_0) + d_Y(x^1_i,y_1)< \epsilon
$$
and so
$$
|d_Y(y_0,y_1)-d_Y(x_i^0,x_i^1)|\leq d_Y(x^0_i,y_0) + d_Y(x^1_i,y_1)<\epsilon
$$
This shows
$$
\lim_{i\to\infty}|d_Y(y_0,y_1)-d_Y(x^0_i,x^1_i)|=0
$$
which in turn shows
$$
d_Y(y_0,y_1)=\lim_{i\to\infty}d_Y(x_i^0,x_i^1)=\lim_{i\to\infty}d_X(x_i^0,x_i^1)
$$

Arguing the same in $Y'$ where $x_i^j\to y_j'$ we get
$$
d_Y(y_0,y_1)=\lim_{i\to\infty}d_X(x_i^0,x_i^1)=d_{Y'}(y_0',y_1')
$$
Finally this provides what we desired
$$
d_Y(y_0,y_1)=d_{Y'}(f(y_0),f(y_1))
$$
❏

### Existence of the completion of X
The preceding indicates how we must proceed. Every $y\in Y$ must come from a C-seq in $X$ and the metric in $Y$ must be defined by $d_Y(y,y')=\lim_{i\to\infty}d_X(x_i,x_i')$. This is what we now carry through.

Let $(X,d_X)$ be a metric space. Let $Y=\text{C-seq}(X)/\sim$, the set of equivalence classes of C-seqs from $X$. We define a metric on $Y$ by
$$
d_Y(y_1,y_2)=\lim_i d_X(x_i^1,x_i^2)
$$
where $y_j=[x_i^j]$. The first issue is to show that this is well defined, that it is a metric on $Y$ extending the metric on $X$ in a natural way, and is complete.

$X$ sits inside of $Y$ is an obvious way, namely, associate to each $x\in X$, the (equivalence class of the) constant (C-seq) $c_x=[x_i]$ where $x_i=x$ for all $i$.

**Claim** $d_Y$ is a well-defined metric on $Y$.

**Proof** Let $[x_i]=[x_i']$ and $[y_i]=[y'_i]$ be elements of $Y$. We need to show
$$
\lim_i d_X(x_i,y_i)=\lim_i d_X(x'_i,y'_i)
$$
Notice that since
$$
d_X(x_i,y_i)\le d_X(x_i,x_i')+d_X(x_i',y_i)
$$
we get
$$
d_X(x_i,y_i)-d_X(x_i',y_i)\le d_X(x_i,x_i').
$$
Similarly, $d_X(x_i',y_i)-d_X(x_i,y_i)\le d_X(x_i,x_i')$ so
$$
|d_X(x_i,y_i)-d_X(x_i',y_i)|\le d_X(x_i,x_i').
$$
Now consider
\begin{align}
|d_X(x_i,y_i)-d_X(x'_i,y'_i)|
&=|d_X(x_i,y_i)-d_X(x'_i,y_i)+d_X(x'_i,y_i)-d_X(x'_i,y'_i)|\\
&\le|d_X(x_i,y_i)-d_X(x'_i,y_i)|+|d_X(x'_i,y_i)-d_X(x'_i,y'_i)|\\
&\le|d_X(x_i,x_i')|+|d_X(y_i,y_i')|\\
\end{align}
This we have $\lim_i|d_X(x_i,y_i)-d_X(x'_i,y'_i)|=0$ and thus $\lim_id_X(x_i,y_i)=\lim_i d_X(x'_i,y'_i)$. So $d_Y$ is well-defined.
❏

**Claim** $d_Y$ is a metric on $Y$.

**Symmetry** It is clear that $d_Y([x_i],[y_i])=d_Y([y_i],[x_i])$ so $d_Y$ is symmetric.

**Identity of Indiscernibles** This follows from [an exercise above](/bpBk_WyzTUi4jVF1YKyWsg#ex1).

**Triangle Inequality** Finally, we need to verify the triangle inequality. $d_Y([x_i],[y_i])\le d_Y([x_i],[z_i])+d_Y([z_i],[y_i])$. This follows from the corresponding inequality for $X$, that is, $d_X(x_i,y_i)\le d_X(x_i,z_i)+d_X(z_i,y_i)$, then taking limits on both sides.

So we have a well defined metric. Let us show next that
❏

**Claim** $X$ is dense in $Y$.

**Proof** What we show is:
$$
d_X(x,x')=d_Y(c_x,c_{x'})\text{ and }\lim_i c_{x_i}=[x_i]\text{ in }Y
$$
The first of these is trivial, for the second, we need $\lim_i d_Y(c_{x_i},[x_i])=0$, that is,
$$
\lim_i \lim_j d_X(x_i,x_j)=0
$$
This is true for any C-seq $(x_i)$ from $X$. This shows that $X$ is dense in $Y$.
❏

**Claim** $Y$ is complete.

**Proof** Let $(y_i)$ be a C-seq from $Y$, since $X$ is dense in $Y$ we can find $c_{x_i}$ with $x_i\in X$ such that $(c_{x_i})\sim(y_i)$ (As C-seqs in $Y$!) But $c_{x_i}\to[x_i]$ from the preceding argument, thus $y_i\to[x_i]$.
❏

**Exercise** Explain how to define the field operations and order in $\mathbb R$ using this *completion* of $\mathbb Q$ definition of $\mathbb R$.

For example, if $x=[x_i]$ and $y=[y_i]$ what CS do you think would be good for $x+y$?

###### tags: `571` `MAT571`