# Formal proof for completion of metric space

In this pdf, a method for constructing a completion for a given metric space $$(X, d)$$. It is very similar (and infact equivalent) to the one in this question.

You start by defining $$S$$ as the set of Cauchy sequences from $$X.$$ Then define the equivalence relation $$\sim$$ on $$X$$ as $$(x_n) \sim (y_n) \iff \forall \epsilon > 0, \, \exists N\, d(x_n, y_m) < \epsilon \,\, \forall n,m \geq N.$$

(Or equivalently as in the other question, $$(x_n) \sim (y_n) \iff \lim_{n\to\infty} d(x_n, y_n) = 0$$)

Denote $$S/\!\!\sim$$ by $$X^*$$. Since the notation in the pdf gets messy if we try to continue with the proof I'm asking for in a moment, I will use some other notation: For every equivalence class $$\overline x = [(x_n)]$$, take $$(x_n)$$ a representative.

Define the following metric in $$X^*$$: $$\delta(\overline x, \overline y) = \lim_{n\to\infty} d(x_n, y_n)$$. It can be proved that this metric is well-defined (it doesn't depend on the choice of representatives) using the Squeeze Theorem.

Now $$(X^*, \delta)$$ can be thought of as being equivalent to a completion of $$X$$, where each point $$p \in X$$ is mapped to the equivalence class of the constant sequence $$[(p, p, p, \dots)]$$.

What I don't know how to prove is that $$(X^*, \delta)$$ is indeed a complete metric space, although I understand it totaly: informally, $$(x_n) \sim (y_n)$$ if they have the same limit in the completion of $$X$$ and and the "holes" or "open ends" are covered by the equivalence classes of sequences that "approach the holes". Everything falls into place, but providing a rigurous proof beats me at this point. Even the notation seems unfixable (you need notation for sequences of classes of sequences. I propose the usage of $$(\overline x^{(n)})_n$$ and then the mth element of a representative of the $$n$$th term is $$x^{(n)}_m$$)

Sometimes you just have to deal with more complicated notation. Here, I shall use a capital letter like $$A$$ to denote an element of $$X^*$$; and since $$A$$ is an equivalence class of sequences in $$X$$, I shall use something like $$(a_n)$$ to denote an element of $$A$$.

Here are some preliminary observations which will help to simplify the proof of completeness:

• If $$(a_n)_{n=1}^{\infty}$$ is a Cauchy sequence in $$X$$ then every subsequence $$(a_{n_k})_{k=1}^{\infty}$$ is related via $$\sim$$ to the main sequence (I leave it to you to verify).

• For any $$\eta>0$$, there is an $$N\in \Bbb{N}$$ such that for all $$m,n\geq N$$, we have $$d(a_n,a_m) \leq \eta$$. In other words, the subsequence $$\{a_N, a_{N+1}, \dots\}$$ has the property that each pair of terms is at most $$\eta$$ away from each other. To summarize: for every $$\eta>0$$, there is a subsequence $$(a_{n_k})_{k=1}^{\infty}$$ such that for all $$k,l\in \Bbb{N}$$, we have $$d(a_{n_k}, a_{n_l})< \eta$$.

Fix a sequence $$(\zeta_n)$$ of positive numbers which decrease to zero (such as $$\zeta_n = \frac{1}{n}$$). Now, to show completeness of $$X^*$$, we have to show every Cauchy sequence converges. So, let $$(A_n)_{n=1}^{\infty}$$ be a Cauchy sequence in $$X^*$$. For each $$n\in \Bbb{N}$$, choose a representative $$(a_{n,k})_{k=1}^{\infty} \in A_n$$ such that for all $$k,l\in \Bbb{N}$$, we have \begin{align} d(a_{n,k}, a_{n,l})< \zeta_n \tag{i} \end{align}

Note that such a representative always exists by our remarks above.

Since $$(A_n)$$ is Cauchy, for every $$j\in \Bbb{N}$$, there is an $$N_j\in \Bbb{N}$$ such that for all $$n,m,k \geq N_j$$, we have \begin{align} d(a_{n,k}, a_{m,k}) < \zeta_j \tag{ii} \end{align} (just unwind the definition of $$(A_n)$$ being Cauchy and the definition of $$\delta$$ to see why this follows). Also observe that by doing this recursively, then you can arrange for this such that $$j and $$N_1< N_2< N_3\dots$$

Now, put $$\beta_j:= a_{N_j, N_j}$$. We claim that $$(\beta_j)_{j=1}^{\infty}$$ is Cauchy in $$X$$. This is because for every $$l\in \Bbb{N}$$, if $$i,j\geq l$$ then (since $$N_i,N_j \geq N_l$$) \begin{align} d(\beta_i, \beta_j) &:= d(a_{N_i, N_i}, a_{N_j, N_j}) \\ &\leq d(a_{N_i, N_i}, a_{N_i, N_j}) + d(a_{N_i, N_j}, a_{N_j, N_j}) \\ &\leq \zeta_i + \zeta_l \tag{by i and ii} \\ &\leq 2\zeta_l, \end{align} where the last line is because we chose the $$\zeta$$ sequence to be decreasing. As $$l\to \infty$$, the RHS tends to $$0$$, which proves the sequence is Cauchy in $$X$$.

Finally, let $$B:= [(\beta_j)_{j=1}^{\infty}]$$ be the equivalence class; I leave it to you to show $$A_n \to B$$.

Note that the idea of the proof is pretty simple. We have a Cauchy sequence $$(A_n)$$. We then choose representatives $$(a_{n,k})_{k=1}^{\infty}$$. So if we write this out as a square array of numbers: \begin{align} \begin{matrix} A_1: & a_{1,1} & a_{1,2} & a_{1,3} & \cdots \\ A_2: & a_{2,1} & a_{2,2} & a_{2,3} & \cdots \\ A_3: & a_{3,1} & a_{3,2} & a_{3,3} & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix} \end{align} ($$n$$ is going down, $$k$$ is going to the right). Very informally, (i) says that if you go vertically down far enough, then all the elements in that row will be close to each other. (ii) says that if you go to the far enough to the "bottom right" then all the elements in the same column will be close enough.

So, the idea is to take the diagonal elements $$\beta_j := a_{N_j,N_j}$$, and show that this has the desired properties. To really understand the proof, I would highly recommend you to write your own arguments for why $$(\beta_j)$$ is Cauchy and why $$A_n \to B$$; use the square array above as your guiding principle to see which elements are close to which ones.

• This answer is perfect! Exactly what I needed. That visual argument helps me so much, I also had my way of looking at the sequences, but I couldn't find a way to describe a sequence that approaches a "hole" so that I could show that its equivalence class is the limit of the classes for which the "limits"* of the representatives approach that hole. That sequence is $(\beta_j)$. The idea of going diagonally is just genius. Thank you so much! (* with quotes, because they need not exist, they may be other holes) Sep 5, 2020 at 19:08
• Thanks! I just asked similar question to this, because the notation in the book I use is instead of using a notation like yours, it chooses to use a notation like $a_n^k$ and I think $k$ is the power of $a_n$! Spent the whole night just to make sense of it -- what a notation! Mar 27, 2022 at 14:52