Completion of metric space (Terence Tao Analysis II Exercise 1.4.8 part (c))

Question

$\def\LIM{\operatorname{LIM}}$ Let $(X,d)$ be a metric space and given any cauchy sequence $(x_n)_{n=1}^{\infty}$ in $X$ we introduce the formal limit $\LIM_{n\to \infty}x_n$. We say that two formal limits $\LIM_{n\to \infty}x_n$ and $\LIM_{n\to \infty}y_n$ are equal iff $\lim_{n \to \infty}d(x_n,y_n)=0$. We then define $\bar{X}$ to be set of all the formal limits of Cauchy sequences in $X$. We define the metric $d_{\bar{X}}$ as follows: $$d_{\bar{X}}(\LIM_{n\to \infty}x_n,\LIM_{n\to \infty}y_n)= \lim_{n \to \infty} d(x_n,y_n)$$ I have proved that $(\bar{X},d_{\bar{X}})$ is indeed a metric space that that the definition of metric is well defined. But I am stuck to prove that $(\bar{X},d_{\bar{X}})$ is a complete metric space. This problem could be resolved without taking into account topological spaces as that concept in later in the book. Any suggestion on how to go about this problem without using machinery of topology would be highly invaluable. Thanks in advance.

Answer 1

Let $(LIM_{n\to\infty} x_{in})_{i=1}^\infty$ be a Cauchy sequence in $(\overline{X},d_{\overline{X}})$, where $(x_{in})_{n=1}^\infty$ is a Cauchy sequence in (X, d) for each i. Define the sequence $n(i)_{i=1}^\infty$ recursively as follows:$ n(1) := min\{N \geq 1: d(x_{1i},x_{1j}) \leq 1, \forall i,j \geq N\}. $ $ \forall k > 1, n(k) := min\{N > n(k-1): d(x_{ki}, x_{kj}) \leq 1/k, $ $\forall i, j \geq N\}.$ (That is, we take the smallest term in the first sequence after which the distance of any pair is less than 1, then we take the smallest term from that term on in the second sequence after which the distance of any pair is less than 1/2 ,..., etc.) $n(i)_{i=1}^\infty$ is an increasing sequence. Let $(x_{k})_{k=1}^\infty := (x_{kn(k)})_{k=1}^\infty$.

Step 1: $(x_{k})_{k=1}^\infty$ is Cauchy: Let $N \geq 1$. By construction, $\forall i , j \geq N$, $d(x_{in(i)}, x_{jn(j)}) \leq d(x_{in(i)}, x_{in(j)}) $ $+$ $d(x_{in(j)}, x_{jn(j)}) \leq 1/N$ $+$ $o$(N), which can be bounded as small as desired by taking N sufficiently large.

Step 2: $LIM_{k\to\infty} (x_{k})_{k=1}^\infty$ is the limit: For any i, j, note that: $d_(x_{ij}, x_{jn(j)}) \leq d(x_{ij}, x_{in(j)})$ $+$ $d(x_{in(j)}, x_{in(i)})$ $+$ $d(x_{in(i)}, x_{jn(i)})$ $+$ $d(x_{jn(i)}, x_{jn(j)})$. Each of the four terms on the RHS can be bounded arbitrarily small by taking taking i, j sufficiently large. Hence we have: $lim_{i\to\infty} d_{\overline{X}}(LIM_{j\to\infty} x_{ij}, LIM_{j\to\infty} x_{j}) = lim_{i\to\infty} lim_{j\to\infty} d(x_{ij}, x_{jn(j)}) = 0$, as desired.

Answer 2

Generally, if you have a sequence of sequences, one thing to consider is the diagonal sequence:

\begin{array}{ccccc} \color{purple}{x_{1,1}} & x_{1,2} & x_{1,3} & x_{1,4} & \dots \\ x_{2,1} & \color{purple}{x_{2,2}} & x_{2,3} & x_{2,4} & \dots \\ x_{3,1} & x_{3,2} & \color{purple}{x_{3,3}} & x_{3,4} & \dots \\ x_{4,1} & x_{4,2} & x_{4,3} & \color{purple}{x_{4,4}} & \dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array}

You should be able to show that if $(\operatorname{LIM}_n x_{i,n})_{i = 1}^\infty$ is Cauchy then the limit is $\operatorname{LIM}_n x_{n,n}$.

Answer 3

$\def\LIM{\operatorname{LIM}}$EDIT: I'm currently reviewing analysis so I decided to prove Trevor Gunn's claim and after wasting like TWO hours of my time, I realized that it's wrong! Here is a counterexample:

\begin{matrix} \color{red}{1} &0 &0 &0 &\cdots \\ 2 &\color{red}{2}&0 &0 &\cdots \\ 3 &3 &\color{red}{3} &0 &\cdots \\ 4 &4 &4 &\color{red}{4} &\cdots \\ \vdots &\vdots &\vdots &\vdots &\ddots \end{matrix} I apologize for posting this here, but I don't have enough credit to write comments.

---

For future self-studiers (like me), here is my proof:

Let $(x^{(n)})_{n=m}^\infty$ be a Cauchy sequence in $\overline X$. Then for each $n\ge m$ we can choose a Cauchy sequence $(x^{(n)}_i)_{i=1}^\infty$ in $X$ such that $x^{(n)} = \LIM_{i\to\infty}x^{(n)}_i$ (this requires the axiom of choice).

Now we want to construct a Cauchy sequence in $X$ and show that $(x^{(n)})_{n=m}^\infty$ converges to its formal limit. There is the obvious choice of $(x_{i}^{(m+i-1)})_{i=1}^\infty$ but I couldn't show that this sequence is a Cauchy sequence. Therefore, we will instead construct a Cauchy sequence by choosing elements $x^{(n)}_i$ such that each term is close to previous term and the distance between a term and the next shrinks fast enough to make all the terms close to each other. More precisely, we want to find sequences $m\le N_1 < N_2 < \dots$ and $1 \le n_1 < n_2 < \dots$ such that $$d\left(x_{n_i}^{(N_i)}, x_{n_{i+1}}^{(N_{i+1})}\right) \le \frac{1}{2^{i}} \quad \text{for all} \quad i \ge 1$$

So let's start with the $N_i$ first. We are assuming that $(x^{(n)})_{n=m}^\infty$ is a Cauchy sequence, this means that $$(\forall\varepsilon>0)(\exists N\ge m)(\forall j,k\ge N)\left(\lim_{\ell\to\infty} d\left(x_{\ell}^{(j)},x_{\ell}^{(k)}\right) \le \varepsilon\right)$$

Thus by the well-ordering principle, we can define $N_i$ recursively as follows $$N_1 := \min\left\{N \in \mathbb{Z} : N\ge m \quad\text{and}\quad (\forall j,k\ge N)\left(\lim_{\ell\to\infty} d\left(x_{\ell}^{(j)},x_{\ell}^{(k)}\right) \le \frac{1}{2}\right)\right\}$$

$$N_{i+1} := \min\left\{N \in \mathbb{Z} : N>N_i \quad\text{and}\quad (\forall j,k\ge N)\left(\lim_{\ell\to\infty} d\left(x_{\ell}^{(j)},x_{\ell}^{(k)}\right) \le \frac{1}{2^{i+1}}\right)\right\}$$

Notice that $\lim_{\ell\to\infty} d\left(x_{\ell}^{(N_i)},x_{\ell}^{(N_{i+1})}\right) \le \frac{1}{2^{i}}$ for all $i\ge 1$. This, together with the fact that these are Cauchy sequences, suggests that one can find a useful bound on $d\left(x_{j}^{(N_i)},x_{k}^{(N_{i+1})}\right)$ for sufficiently large $j$ and $k$.

To prove this, let's fix an $i\ge 1$ and let $L := \lim_{\ell\to\infty} d\left(x_{\ell}^{(N_i)},x_{\ell}^{(N_{i+1})}\right)$. Then there exists an $l\ge1$ such that $d\left(x_{\ell}^{(N_i)},x_{\ell}^{(N_{i+1})}\right) \le L + \frac{1}{2^{i}} \le \frac{1}{2^{i-1}}$ for all $\ell \ge l$. Now, both sequences are Cauchy sequences so we can find a common $l'\ge1$ such that $$d\left(x_{j}^{(N_i)},x_{k}^{(N_{i})}\right) \le \frac{1}{2^{i-1}} \quad\text{and}\quad d\left(x_{j}^{(N_{i+1})},x_{k}^{(N_{i+1})}\right) \le \frac{1}{2^{i-1}}$$

for all $j,k \ge l'$. It follows that $$d\left(x_{j}^{(N_i)},x_{k}^{(N_{i+1})}\right) \le d\left(x_{j}^{(N_i)},x_{k}^{(N_{i})}\right) + d\left(x_{k}^{(N_i)},x_{k}^{(N_{i+1})}\right) \le \frac{1}{2^{i-1}} + \frac{1}{2^{i-1}} = \frac{1}{2^{i-2}}$$ for all $i,k \ge \max(l,l')$. To summarize, for any $i\ge 1$ we can find an integer $l\ge1$ such that for all $j,k \ge l$ the following inequality is true $$d\left(x_{j}^{(N_i)},x_{k}^{(N_{i+1})}\right) \le \frac{1}{2^{i-2}}$$

Therefore we can define (using the well-ordering principle again) the $n_i$ sequence recursively as follows $$n_1 := \min\left\{l \in \mathbb{Z} : l\ge 1 \quad\text{and}\quad (\forall j,k \ge l) \left(d\left(x_{j}^{(N_1)},x_{k}^{(N_{2})}\right) \le \frac{1}{2^{-1}}\right)\right\}$$ $$n_{i+1} := \min\left\{l \in \mathbb{Z} : l > n_i \quad\text{and}\quad (\forall j,k \ge l) \left(d\left(x_{j}^{(N_{i+1})},x_{k}^{(N_{i+2})}\right) \le \frac{1}{2^{i-1}}\right)\right\}$$

It's clear that $d\left(x_{n_i}^{(N_{i})},x_{n_{i+1}}^{(N_{i+1})}\right) \le \frac{1}{2^{i-2}}$ for all $i\ge 1$ (this is not what we aimed for above, but it will work). By induction and the triangle inequality we have $$d\left(x_{n_i}^{(N_{i})},x_{n_{j}}^{(N_{j})}\right) \le \sum_{k=i}^{j-1} \frac{1}{2^{k-2}} \tag{1}$$

for all $1 \le i \le j$. Since $\sum_{k=0}^{\infty}\frac{1}{2^{k-2}}$ is convergent, the above sum can be made arbitrarily small by choosing $i$ and $j$ big enough (cf. Proposition 7.2.5 in Analysis I). Therefore, the sequence $(x_{n_i}^{(N_i)})_{i=1}^\infty$ is a Cauchy sequence in $X$.

Finally, we have to show that $\lim_{n\to\infty}x^{(n)} = \LIM_{i\to\infty}x_{n_i}^{(N_i)}$. We can simplify this job by proving instead that $\lim_{k\to\infty}x^{(N_k)} = \LIM_{i\to\infty}x_{n_i}^{(N_i)}$ and then applying Lemma 1.4.9 (note that $m\le N_1 < N_2 < \dots$ as we planned). So we want to prove that $$\lim_{k\to\infty}\lim_{i\to\infty} d\left(x_{i}^{(N_k)}, x_{n_i}^{(N_i)}\right) = \lim_{k\to\infty} d_{\overline X}\left(x^{(N_k)},\mathop{\LIM}\limits_{i\to\infty}x_{n_i}^{(N_i)}\right) = 0$$ Ok so let us fix $k \ge 1$. Then for all $i \ge n_{k+1}$, we have $i \ge n_k$ so by our choice of $n_k$ we get

$$d\left(x_i^{(N_k)},x_{n_{k+1}}^{(N_{k+1})}\right) \le \frac{1}{2^{k-2}}$$

Also, $i \ge k+1$ since $1\le n_1 < n_2 \dots$. So using inequality (1) above we obtain

\begin{align*} d\left(x_i^{(N_k)},x_{n_{i}}^{(N_{i})}\right) &\le d\left(x_i^{(N_k)},x_{n_{k+1}}^{(N_{k+1})}\right) + d\left(x_{n_{k+1}}^{(N_{k+1})},x_{n_{i}}^{(N_{i})}\right) \le \frac{1}{2^{k-2}} + \sum_{\ell=k+1}^{i-1} \frac{1}{2^{\ell-2}}\\ &= \frac{1}{2^{k-2}} + 4\frac{\frac{1}{2^{i}} - \frac{1}{2^{k+1}}}{\frac{1}{2}-1} = \frac{1}{2^{k-3}} - 8\frac{1}{2^{i}} \end{align*}

for all $i \ge n_{k+1}$. By the comparison principle we obtain $$\lim_{i\to\infty} d\left(x_{i}^{(N_k)}, x_{n_i}^{(N_i)}\right) \le \frac{1}{2^{k-3}}$$ for all $k\ge 1$ (note that this limit exists by part (b) of this exercise). One last application of the comparison principle, and we get the desired result.