Problem 2 - Cauchy sequences

For a set $T$ defined by

$$T=\{ X \; \vert \; X \subseteq \{0,1\}^*, \forall x,y \in \{0,1\}^*, xy\in X \Rightarrow x \in X\}$$

consider a distance $d$ on $T$ defined by

$$d(X,X)=0\quad (X\in T)$$

$$d(X,Y)=\frac{1}{\min\{\vert x\vert:x\in X, x\notin Y \; \hbox{or} \; x\notin X, x\in Y\}}\quad (X,Y\in T, X\neq Y)$$

where $\vert x\vert$ denotes the length of $x$.

Prove that $(T,d)$ is a complete metric space, i.e., every Cauchy sequence on $T$ converges.

A sequence $(X_n)$ is a Cauchy sequence when

$$(\forall \epsilon \in \mathbb{R}^*_+)(\exists q \in \mathbb{N})(\forall n \geq q)(\forall p \in \mathbb{N})(d(X_{n+p},X_n)\leq \epsilon).$$

Let us assume that $(X_n)$ does not converge, that is

$$(\forall l \in T)(\exists \epsilon \in \mathbb{R}^*_+)(\forall n_... ...{N})(\exists n \in \mathbb{N})(n\geq n_0 \; \hbox{and} \; d(X_n,l) > \epsilon).$$

In particular, if $l=\{0,1\}^*$, we have an $\epsilon$ such that

$$(\forall n_0 \in \mathbb{N})(\exists n \in \mathbb{N})(n\geq n_0 \; \hbox{and} \; d(X_n,l) > \epsilon),$$

$$(\exists q \in \mathbb{N})(\forall n \geq q)(\forall p \in \mathbb{N})(d(X_{n+p},X_n)\leq \epsilon).$$

We selection a $q$ such that

$$(\exists n \in \mathbb{N})(n\geq q \; \hbox{and} \; d(X_n,l) > \epsilon),$$

$$(\forall n \geq q)(\forall p \in \mathbb{N})(d(X_{n+p},X_n)\leq \epsilon).$$

and finally a $n$ such that

$$d(X_n,l) > \epsilon,$$

$$(\forall p \in \mathbb{N})(d(X_{n+p},X_n)\leq \epsilon).$$

We can rewrite those equations as:

$$\frac{1}{\min\{\vert x\vert:x\notin X_n\}} > \epsilon,$$

$$(\forall p \in \mathbb{N})(\frac{1}{\min\{\vert x\vert:x\in X_n, x\notin X_{n+p}\;\hbox{or}\;x\in X_{n+p},x\notin X_n\}} \leq \epsilon).$$

We can simplify the first one because $X_n \subset l, X_n \neq l$ (because when $\epsilon$ was fixed, the fact that $\hbox{card}\; l = \infty$ ensured that $X_n$ couldn't be $l$). We deduce that $\min\{\vert x\vert:x\notin X_n\} = k$ for some $k\in \mathbb{N}$. The second formula says that $\min\{\vert x\vert:x\in X_n, x\notin X_{n+p}\;\hbox{or}\;x\in X_{n+p},x\notin X_n\} > k$. That means that the minimal value is achieved for $x\notin X_n$ (because otherwise that longer word should have been detected before when comparing $X_n$ and $l$). That is:

$$\frac{1}{\min\{\vert x\vert:x\notin X_n\}} > \epsilon,$$

$$(\forall p \in \mathbb{N})(\frac{1}{\min\{\vert x\vert:x\in X_{n+p},x\notin X_n\}} \leq \epsilon).$$

But, anyway, it still means that an element of length $\geq k$ should belong to $X_n$, which yields a contradiction with the fact that $\min\{\vert x\vert:x\notin X_n\} = k$.

Therefore, we have shown ab absurdo than $(X_n)$ converges, thus $(T,d)$ is a complete metric space.