# Proof that $\omega^\omega$ is completely metrizable and second countable

I have almost solved the following problem but am stuck at the very end, can you help me finish it? Thank you for your help. Let $n<\omega$ and $t\in {}^n\omega$. We define $U_t=\{s\in {}^\omega\omega : t\subseteq s\}$. The family $\mathcal B=\{U_t : t\in\bigcup {}^n\omega\}$ is a basis for a topology $\tau$ on ${}^\omega\omega$. This means that a set $X$ is in $\tau$ if and only if $X$ is a union of elements of $\mathcal B$.

EXERCISE 50 (PG): Show that $\langle {}^\omega\omega,\tau \rangle$ is a second countable completely metrizable space. Hint: For $r,s\in {}^\omega\omega$ such that $r\ne s$, the $\varrho(r,s)=1/\min\{n : r(n)\ne s(n)\}$. Moreover, let $\varrho(r,r)=0$. Show that $\varrho$ is a complete metric on ${}^\omega\omega$ that induces the topology $\tau$.

(i) Second countable: the set of $n$-tuples is countable since it is a finite union of countable sets.

(ii) complete with respect to $$d(f,g) = \frac{1}{\min \{n \mid f(n) \neq g(n) \}}$$ Let $f_k$ be a Cauchy sequence. This means that the index at which $f_k, f_i$ differ gets larger as $i,k$ get larger. Let $f(n)$ denote the pointwise limit, that is, $\lim_{k \to \infty} f_k(n)$. Then $f(n) \in \omega$ for every $n$ since $f_k(n)$ is eventually constant. Hence $f \in \omega^\omega$.

(iii) $d$ induces the same topolgy as $U_t$:

$\tau_t \subset \tau_d$: Let $s \in U_t$. Then $B(s, \frac{1}{n+1})$ is an open ball contained in $U_t$ hence $U_t$ is open in $\tau_d$.

$\tau_t \supset \tau_d$: Let $B(s, \frac{1}{k})$ be an open balls. If $k < n$, $s \in U_s \subset B(s, \frac{1}{k})$. But if $k \ge n$ then I'm stuck. The ball $B(s, \frac{1}{k})$ consists of all sequences that agree with $s$ on the first $k$ coordinates. So it is quite small. How do I make the $U_t$ small enough to fit in this ball? I have thought of intersection but since I'm only allowed to do finite intersections I don't see what to do.

• The problem in question is from the book Discovering Modern Set Theory: The basics By Winfried Just, Martin Weese, p.148. – Martin Sleziak Jan 29 '14 at 7:43

## 2 Answers

(i) No, $\mathcal B$ is countable because it’s the countable union of the countable sets $\mathcal B_n=\{U_t:t\in{^n\omega}\}$.

(ii) I assume that you’ve verified that $d$ really is a metric. What you’ve written to show that $\left\langle{^\omega\omega},d\right\rangle$ is complete is rather sloppy, but you have the right idea; let me know if you want me to elaborate.

(iii) Your $\tau_t$ should be simply $\tau$: the name was already given in the problem, and you don’t want the name to seem to refer to a specific element of ${^{<\omega}\omega}$. In your argument that $\tau\subseteq\tau_d$ you should say explicitly that $t\in{^n\omega}$ rather than forcing the reader to work this out from what follows:

Let $t\in{^n\omega}$ and $s\in U_t$; then $s\in B_d\left(s,\frac1n\right)\subseteq U_t$, so $U_t\in\tau_d$.

(You don’t need $n+1$.)

In fact $U_t=B_d\left(s,\frac1n\right)$, and this observation essentially finishes the proof that the two topologies are equal: if $s\in B_d(t,\epsilon)$, choose $n$ so that $B_d\left(s,\frac1n\right)\subseteq B_d(t,\epsilon)$ and observe that $$B_d\left(s,\frac1n\right)=U_{s\upharpoonright n}\;.$$

• Regarding (i): Yes. I argue that ${^n}\omega$ is a finite union of countable sets. Therefore $\mathcal B$ is countable. (I agree that I wrote the whole thing a bit sloppily and I admit to not verifying that $d$ is indeed a metric. I know how to do it but what I'm very much after is the second inclusion at the end of the proof. – Rudy the Reindeer Dec 4 '12 at 21:21
• @Matt: But $\mathcal B$ is indexed by ${^{<\omega}\omega}=\bigcup_{n\in\omega}{^n\omega}$, so it’s the union of countably infinitely many countable sets. – Brian M. Scott Dec 4 '12 at 21:24
• But in the book $\bigcup \mathcal A$ is used to mean $\bigcup_i A_i$ for some index set $I$ or $\bigcup_{A \in \mathcal A}A$ hence for $n$ fixed, the set $\bigcup {^n}\omega$ should denote the set of all $n$-tuples! – Rudy the Reindeer Dec 4 '12 at 21:25
• @Matt: That first sentence is just defining the notation $U_t$. It could perhaps better have been written: ‘For each $n<\omega$ and $t\in{^n\omega}$ we define $U_t=\ldots~$’, and the union should definitely have been indexed: $\bigcup_{n\in\omega}$. – Brian M. Scott Dec 4 '12 at 21:33
• @Matt: They were careful up at the top when they defined strategies; I don’t know why they omitted the indexing of the union in the description of $\mathcal B$, but I suspect that it was either a genuine typo or a simple oversight. You’re welcome! – Brian M. Scott Dec 4 '12 at 21:37

I'm going to alter the notations a little bit. In the below I will use $s,t$ to denote finite sequences, and $x,y$ to denote infinite sequences.

Also, note that there is a slight problem with the metric as presented: If $x , y \in {^\omega}\omega$ are such that $x(0) \neq y(0)$, then according to the formula we must have that $$d ( x , y ) = \frac{1}{\min \{ n : x(n) \neq y(n) \}} = \frac{1}{0},$$ which, as we have all learned, is slightly problematic. We can fix this by instead defining the metric by $$d ( x , y ) = \frac{1}{\min \{ n +1 : x(n) \neq y(n) \}}$$ when $x \neq y$.

To show that $\tau_t \supseteq \tau_d$ it suffices to show that given any $x \in {^\omega}\omega$ and every $\epsilon > 0$ there is a $s \in {^{< \omega}}\omega$ such that $x \in U_s \subseteq B ( x , \epsilon )$.

Note that given $x \in {^\omega}\omega$ and $\epsilon > 0$ there is an $N$ such that $\frac{1}{N+1} < \epsilon$. Consider now $s = x \restriction N$. Given any $y \in U_s$ we know that $y \supseteq s$, and so it must be that $y(n) = s(n) = x(n)$ for all $n < N$. Therefore either $y = x$ (whence $d(x,y) = 0$) or $\min \{ n : y(n) \neq x(n) \} \geq N$ (whence $d(x,y) \leq \frac{1}{N+1}$); in either case $d ( x , y ) < \epsilon$. As we clearly have that $x \supseteq s$, then $x \in U_s \subseteq B ( x , \epsilon )$.