# Proving a metric space to be compact

I have the following metric space: The set $X$ of all sequences with members from the set $\{1,2,\ldots, n\}$, together with the metric $$d(x,y)=\frac{1}{\min\{j\in\mathbb{N}:x_j\ne y_j\}}.$$ I wish to prove two things about this space:

1) $X$ is compact.

2) If $T:X\to X$ is defined by $Tx_n=x_{n+1}$ then $T$ is continuous.

Its many years since I studied topology so if someone can help me even a little bit I will be very grateful. Thanks.

-
Maybe we should write $(Tx)_n$? I was confused at first. – Dylan Moreland Jul 8 '12 at 6:16

Hint for 1: Note that a metric space is compact iff every sequence has a convergent sub-sequence. Let $(y_k)$ be a sequence in $X$. Since there are only finitely many choices for the first term of an element of $(y_k)$, there is some sub-sequence $(y_k^1)$ of $(y_k)$ such that all elements have the same first term. Since there are only finitely many choices for the second term, there is some sub-sequence $(y_k^2)$ of $(y_k^1)$ such that all elements have the same first term. Continue in this manner, and show that the sub-sequence $(y_k^k)$ (often called the diagonal sub-sequence) is convergent.

Hint for 2: Let $(x_j),(y_j)\in X$. Note that $\min\{j\in \mathbb N: x_j\neq y_j\}=\min\{j\in \mathbb N: x_{j+1}\neq y_{j+1}\}+1$, so $$\frac{1}{d((x_j),(y_j))}=\frac{1}{d(T(x_j),T(y_j))}+1$$ and do some rearranging.

-
Do you mean +1 in Hint 2? For $(x_j)=1,2,3\cdots$ and $(y_j)=1,2,4\cdots$, the min on the left is 3 while the min on the right is 2. Or am I missing something here? – Shahab Jul 8 '12 at 6:44
@Shahab: Yes, it should be $+1$. – Brian M. Scott Jul 8 '12 at 6:50

To prove that $X$ is compact, it suffice to show that it is totally bounded and complete.

To show that it is totally bounded, let $\epsilon\gt 0$. Let $m\gt 0$ be such that $\frac{1}{m}\lt\epsilon$. Now, there are only $n^m$ possible finite sequences of length $m$ with values in $\{1,2,\ldots,n\}$. For each such sequence $s$, let $\mathcal{O}_s$ consist of all elements of $X$ that agree with $s$ in the first $m$ points. The set is open, since for every $(x_n)\in \mathcal{O}_s$, any sequence within $\frac{1}{m}$ of $(x_n)$ must agree with $x_n$ on the first $m$ terms, and hence have $s$ as its initial term. Moreover, the distance between any two elements of the set is less than $\epsilon$, so the radius of $\mathcal{O}_s$ is less than $\epsilon$. Since $X$ is the union of the $\mathcal{O}_s$, we see that $X$ is totally bounded.

Now suppose that $(x_n)_m$ is a Cauchy sequence. Then for every $k\in\mathbb{N}$ there exists $M(k)\gt 0$ such that if $j,\ell\geq M(k)$, then $d((x_n)_i,(x_n)_j)\lt \frac{1}{k}$. That means that $(x_n)_i$ and $(x_n)_j$ agree in the first $k$ terms. Define the sequence $(y_n)$ by letting $y_k$ be the common $k$th term to all sequences with index greater than $M(k)$. Show that $(x_n)_m\to (y_n)$.

Thus, $X$ is compact.

-