Metric space of infinite binary sequences

Question

Let $\Omega = \{0,1\}^{\mathbb{N}}$ be the space of infinite binary sequences. Define a metric on $\Omega$ by setting $d(x,y) = 2^{-n(x,y)}$ where $n(x,y)$ is defined to be the maximum $n$ such that $x_i = y_i$ for all $i\le n$. Show that $(\Omega, d)$ is a compact metric space.

I have tried to show this by taking open covers of $\Omega$ and finding a finite subcover, but that does not seem to be working. How could I approach this problem?

Answer 1

HINT: Give $\{0,1\}$ the discrete topology, and let $\tau$ be the resulting product topology on $\Omega$; $\Omega$ is certainly compact in this topology, since it’s a product of compact spaces. If $\tau_d$ is the topology generated by the metric $d$, show that $\tau_d=\tau$.

Alternatively, let $\sigma=\langle x_n:n\in\Bbb N\rangle$ be a sequence in $\Omega$, where $x_n=\langle x_n(k):k\in\Bbb N\rangle$, and show that $\sigma$ has a convergent subsequence. To do this, note first that there must be a $b_0\in\{0,1\}$ and an infinite $N_0\subseteq\Bbb N$ such that $x_n(0)=b_0$ for each $n\in N_0$. Then there must be a $b_1\in\{0,1\}$ and an infinite $N_1\subseteq N_0$ such that $x_n(1)=b_1$ for each $n\in N_1$. Keep going.

Answer 2

It suffices to prove $\Omega$ is complete and totally bounded. Let $\{x_i\}$ be a Cauchy sequence in $\Omega$. Construct a sequence $x\in \Omega$ as follows. For every $n\in\mathbb{N}$, there is some smallest $K_n$ such that for all $i$, $j\ge K_n$, we have $d(x_i, x_j) < 1/2^n$. This implies that for all $i, j\ge K_n$, the first $n$ bits of $x_i$ and $x_j$ agree. Set the $n$th bit of $x$ to be the $n$th bit of $x_{K_n}$, $x_{K_n +1}$, $x_{K_n+2}$, etc. Now, note that if $i > K_n$, then $n(x_i, x) \ge n$, as $K_{n} \ge K_{n-1} \ge K_{n-2} \ge \cdots \ge K_1$. Thus, for $i > K_n$, we see that $d(x_i, x) < 1/2^n$. Sending $n\to\infty$ shows $x_i \to x$. Thus $\Omega$ is complete.

Now we must show $\Omega$ is totally bounded. Let $\epsilon > 0$, and choose $n$ such that $1/2^{n+1} < \epsilon \le 1/2^n$. Suppose $\{a_1, a_2, \cdots, a_{2^n}\}$ is an enumeration of the $2^n$ finite binary sequences of length $n$. Append an infinitely many 0s to the end of each $a_i$, so that they may be considered elements in $\Omega$. For every $x\in \Omega$, its first $n$ bits must agree with the first $n$ bits of some $a_j$, so $d(x, a_j) < \epsilon$ for some $1\le j \le 2^n$. Hence, $$\Omega \subset N_{\epsilon} (a_1) \cup N_{\epsilon} (a_2) \cup \cdots \cup N_{\epsilon} (a_{2^n}) $$ As $\epsilon$ was arbitrary, it follows $\Omega$ is totally bounded.