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....

  • $\begingroup$ You need to fix the notation with indices denoting both elements of a sequence and its components. $\endgroup$ – Conifold Sep 7 '14 at 1:05
  • $\begingroup$ @Conifold Thanks for the help, but I have no idea what you just said. Please explain! $\endgroup$ – layman Sep 7 '14 at 1:06
  • $\begingroup$ $x_n$ is used to denote elements of a sequence in $X$ as well as components of a single element in the distance formula, $x_{n_k}$ would be a subsequence of $x_n$, probably something like $x_n^{(k)}$ is intended. $\endgroup$ – Conifold Sep 8 '14 at 17:53

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.


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.

  • $\begingroup$ Wouldn't it have been substantially easier to show that $X$ was totally bounded, given that totally bounded + complete = compact? I mean, totally bounded follows rather trivially from the fact that $d(x,y) = \sum_{n=1}^{\infty} \frac{1}{2^n} \left| x_n - y_n \right| < \frac{1}{2^n} \leq \frac{1}{2}.$. $\endgroup$ – user319128 Jun 13 '16 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.