Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

enter image description here

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.

share|improve this question
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 at 7:43

2 Answers 2

(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}\;.$$

share|improve this answer
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 )$.

share|improve this answer
Hmm... you write $t \in {^\omega}\omega$ but it appears to me as if $n$ was fixed in the definition of $\mathcal B$. What am I missing? –  Rudy the Reindeer Dec 4 '12 at 21:19
@Matt: That $n$ is not fixed in the definition of $\mathcal B$. The union in the definition of $\mathcal B$ is over $n\in\omega$. (Now I understand why you thought that $\mathcal B$ was a finite union.) –  Brian M. Scott Dec 4 '12 at 21:25
@Matt: Sorry. My notation got a bit mixed up, which might have lead to more difficulties. I'll try to fix it presently. –  Arthur Fischer Dec 5 '12 at 7:29
Thank you. And don't worry about induced confusions: as it turned out my confusion arose from a typo in the book. (see comments to Brian's answer) –  Rudy the Reindeer Dec 5 '12 at 7:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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