For $x, y ∈ \{0, 1\}^\mathbb{N}$, define $d(x, y) = 2^{-n}$ where $n$ is the first position where the sequences $x$ and $y$ are different.
- Show that ($\{0,1\}^\mathbb{N}, d$) is compact.
- Show that the set P of periodic elements (sequences where there exist $m>0$ such that $x_i = x_{m+i}$ for all $i$) is countable and dense.
What I tried
For part 1, I have been trying to use the fact that a set is compact if every sequence has a convergent subsequence. But I keep confusing myself with the fact that the elements are sequences and then if I’m supposed to take sequences of those sequences.
For part 2, I’m really not sure where to start. With regards to countability, my initial thought is that if an element is periodic then there is a finite number of elements that get repeated. And since there are only 2 possible options for any given entry, we are arranging a finite number of elements in finite ways? But I am not sure about density.
It's clear that the metric defined on the set is really so. For showing compactness take any arbitrary sequence of sequences say $\lbrace a_n\rbrace$. Clearly there are infinitely many sequences of $\lbrace a_n\rbrace$ with 1st bit being either $0$ or $1$. If there are finitely such sequences that results the whole $\lbrace a_n\rbrace$ to have finite terms which is a contradiction. Take one of such sequences say $a_{n_1}$. Now among those subsequences with 1st bit $1$ or $0$ choose those of 2nd bit being $1$ or $0$ (whose there are infinitely many of them there). There are such infinite sequences with the same argument. So far we have found infinitely many sequence with 1st 2 bits being at least either $00,01,10,11$. Take one of those sequences and name it $a_{n_2}$. Keep on this procedure and make $\lbrace a_{n_k}\rbrace$ as a sunsequence of $\lbrace a_n\rbrace$. This subsequence clearly converges to the same sequence we were fixing each bit every time. So the metric space is compact.
For showing countability of $P$, the set of periodic sequences, let's count them manually. Please note that there are finitely many periodic sequences corresponding to each $m$. Embarking on this, 1st count sequences with $m=1$. When finished, count those of $m=2$ and go on. So you have counted them all. For showing density, we must show that either any member of mother metric set say $X$ is a member of $P$ or is arbitrarily close to one such. In the latter case, take some non-periodic sequence $x \in X$. For any arbitrary $m$, there is a periodic sequence $p \in P$ with period $m$ whose its first $m$ bits are exactly the same as those of $x$. So by definition we conclude that $d(x,p)\le \frac{1}{m}$. Since $m$ is arbitrary this leads us to density.
2nd proof:
Revision
After $\sim 5$ years, I came back to check the answer and spotted some typos and ambiguities in the proof of compactness. Although the OP may so far have received well enough responses from the community, I will add up an update to my current answer, hopefully clarifying it to future readers.
1- We wish to prove that the space with the embedded metric is compact. In other words, we want to prove that any sequence of sequences $\left\{\left\{a_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$ contains a subsequence $\left\{\left\{a_n^{(b_m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$, where $b_m:\Bbb N\to \Bbb N$ denotes the index of the subsequences. The proof continues by step-by-step construction of such a subsequence.
For any sequence $\left\{\left\{a_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$, there are infinitely many $\left\{a_n^{(m)}\right\}_{n=1}^\infty$ either starting with $1$ or starting with $0$. We then refine $\left\{\left\{a_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$ to keep only those sequences for which there are infinitely many sequences sharing the same value with $a_1^{(m)}$. To clarify the matter, if there were infinitely many $\left\{a_n^{(m)}\right\}_{n=1}^\infty$ starting with $1$, then remove the sequences starting with $0$ and vice versa. Name the new refined subsequences as $\left\{\left\{c_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$. It is then clear that the maximal metric value over $\left\{\left\{c_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$ is $\frac{1}{2}$.
Let us move on. This time, among the sequences of $\left\{\left\{c_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$, we look for those sequences $\left\{c_n^{(m)}\right\}_{n=1}^\infty$ with either $c_2^{(m)}=1$ or $c_2^{(m)}=0$ and for which there are infinitely many such sequences there. We refine this set into $\left\{\left\{d_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$ through removing the other sequences. The maximal metric value in $\left\{\left\{d_n^{(m)}\right\}_{n=1}^\infty\right\}_{m=1}^\infty$ would then be $\frac{1}{4}$. Continuing this process, we have finally built a subsequence of sequences converging to a fixed sequence.