Prove that the space of sequences under this metric is complete and compact.

Question

I'm currently studying for the prelim exams, and I would love a hint on how to complete this problem.

If $X$ is the space of sequences of $0$'s and $1$'s (i.e., $x \in X$ if $x = (x_{1}, x_{2}, x_{3}, \dots )$ with $x_{i} = 0$ or $1$), and $d(x,y) = \sum \limits_{n = 1}^{\infty} \dfrac{|x_{n} - y_{n}|}{2^{n}}$, then prove that $d$ is complete and $(X, d)$ is compact.

I'm not even sure how to start this. All that I came up with is the seemingly obvious fact that $d(x,y) \leq 1$ for any $x, y \in X$.

I know to show the metric is complete, I need to show that any Cauchy sequence converges (or has a convergent subsequence...).

So, let $\{x_{n}\}_{n = 1}^{\infty} \subseteq X$ be a Cauchy sequence. Then for every $\epsilon > 0$, $\exists N \in \mathbb{N}$ such that $m, n \geq N$ implies $d(x_{n}, x_{m}) < \epsilon$. Thus, $\sum \limits_{k = 1}^{\infty} \dfrac{|x_{m_{k}} - x_{n_{k}}|}{2^{k}} < \epsilon$.

Now what? I have some sort of idea that as $m$ and $n$ get bigger, the starting terms of each sequence must be equal...I think that must be true. For example, if $\epsilon < \frac{1}{2}$, then certainly we would need $x_{n_{1}} = x_{m_{1}}$. Similarly, if $\epsilon < \frac{1}{4}$, then we would need $x_{n_{2}} = x_{m_{2}}$ as well....

Answer 1

By the Tychonov theorem, this space is compact. It is also metrizable via the metric $$\rho(x,y) = \sum_{n=1}^\infty {|x_n - y_n|\over 2^n}.$$ A compact metrizable space is complete.

Answer 2

For completeness: We know since for any $\epsilon > 0$, there is some $N$ such that $m, n \geq N$ implies $d(x_{n}, x_{m}) < \epsilon$.

But by the definition of the distance formula, this gives:

$\sum \limits_{k = 1}^{\infty} \dfrac{|x_{n_{k}} - x_{m_{k}}|}{2^{k}} < \epsilon$

In particular, if $\epsilon < \dfrac{1}{2}$, then we must have $x_{n_{1}} = x_{m_{1}}$ for all $m, n \geq N$ (because otherwise $d(x_{n},x_{m}) \geq \dfrac{1}{2}$).

Similarly, if $\epsilon < \dfrac{1}{4}$, then we must have $x_{n_{1}} = x_{m_{1}}$, and $x_{n_{2}} = x_{m_{2}}$ for all $n, m \geq N$ in order to ensure $d(x_{n},x_{m}) < \epsilon$.

If $\epsilon$ is chosen such that $\epsilon < \dfrac{1}{2^{k}}$, then we can find $N$ such that $m, n \geq N$ implies $d(x_{n},x_{m}) < \epsilon < \dfrac{1}{2^{k}}$. By the above reasoning, this implies that for $1 \leq i \leq k$, we have $x_{n_{i}} = x_{m_{i}}$, i.e., for all $m, n \geq N$, $x_{m}$ and $x_{n}$ agree on the first $k$ terms.

This shows that as we make $\epsilon$ smaller, (specifically, smaller than $\dfrac{1}{2^{k}}$ for each $k$), the first $k$ terms converge, as sequences of their own. More specifically, consider the sequence $\{ x_{n_{1}}\}_{n = 1}^{\infty}$ of first terms in each of the sequences in $\{x_{n}\}$. Clearly, if $\epsilon < \frac{1}{2}$, then eventually this sequence becomes constantly $0$ or $1$, so $\lim \limits_{n \to \infty} x_{n_{1}}$ exists and is either $0$ or $1$.

Similarly, for each $k$, choosing $\epsilon < \dfrac{1}{2^{k}}$ means $\lim \limits_{n \to \infty} x_{n_{k}}$ becomes constant after some $N$, which means it is either $0$ or $1$. But this is true for each $i \in \mathbb{N}$, which means for each $i$, $\{x_{n_{i}} \}_{n = 1}^{\infty}$ converges. But convergence of each $i$-th term sequence to $0$'s or $1$'s implies convergence of the entire sequence to some sequence of $0$'s and $1$'s, which implies this limit is in $X$. Thus, $d$ is complete, as desired.

For compactness: To show $(X, d)$ is compact, we will prove that $(X, d)$ is sequentially compact. Suppose $\{x_{n}\}$ is a sequence in $(X,d)$. Clearly, for each $n$, $x_{n}$ is itself a sequence, and $x_{n_{i}} = 0$ or $1$ for each $i \in \mathbb{N}$. If we consider the sequence created by looking at the first term of each sequence $x_{n}$, we can denote this sequence $\{x_{n_{1}} \}_{n = 1}^{\infty}$. This sequence will have either infinitely many $0$'s or $1$'s. Assume without loss of generality that it has infinitely many $0$'s. Then denote $y_{1} = x_{n^{*}_{1}}$ where $n^{*}$ is the first term in the sequence $\{x_{n_{i}}\}$ that takes the value $0$. Now we will consider the subset of $M \subseteq \{x_{n} \}$ in which each element of $M$ is a sequence that only contains $0$ as the first term. We will also omit the element $x_{n^{*}}$ from $M$.

Now, $M$ is an infinite subset of $\{x_{n} \}$ by construction. From this infinite subset, we know that there are either infinitely many $0$'s or infinitely many $1$'s as the second terms of the sequences. Assume without loss of generality that there are infinitely many $0$'s. If we let $y_{2}$ be the first element of $M$ such that the second term is $0$, then $y_{2}$ has $0$ in both its first and second coordinates. Now we will define $M'$ to be the infinite subset of $M$ where every element has $0$ as its second term. We will omit $y_{2}$ from $M'$. We will then examine the third entry of every sequence in $M'$. There will be infinitely many $0$'s or $1$'s. We can assume without loss of generality that there are infinitely many $0$'s. Then we can define $y_{3}$ to be the first sequence with $0$ as its third term. We can then define the infinite subset $M''$ of $M'$ containing only the sequences with $0$ as the third entry, and we will omit $y_{3}$ from $M''$.

It's not hard to see that we are able to iteratively construct a sequence $y_{n}$ that converges to $(0,0,0,\dots)$. Thus, every sequence has a convergent subsequence, which means this metric space is sequentially compact, and thus compact, as desired.