Continuous Reduction of $A \subset \mathbb{N}^{\mathbb{N}}$ in $F_{\sigma}$ to countable dense $Q \subset 2^{\mathbb{N}}$.

Question

I am trying to complete problem 21.17 in Kechris' book Classical Descriptive Set Theory, which asks to show that if $Q \subset 2^{\mathbb{N}}$ is countable dense, then $A \leq_{W} Q$ for any $A \subset \mathbb{N}^{\mathbb{N}}$ in $F_{\sigma}$, where the notation $A \leq_{W} Q$ means that there exists a continuous function $f : \mathbb{N}^{\mathbb{N}} \rightarrow 2^{\mathbb{N}}$ such that $x \in A \ \text{iff} \ f(x) \in Q$.

I'm very stumped here. Any advice on how to tackle this problem would be very appreciated.

Answer 1

Actually, the first hint to this exercise is that it belongs to the chapter on games; this hint is made explicit in Exercise 23.1, where you are asked to give a strategy for Player II in the Wadge game $\mathit{WG}(A,Q)$. So the rest of the solution is to provide such strategy.

Recall that the game $\mathit{WG}(A,Q)$ has the following form: $$ \begin{array}{rcccccc} \mathrm{I}: & x_0 & & x_1 & & \dots \\ \mathrm{II}: & & y_0 & & y_1 & & \dots \end{array} $$ where $x_i\in\mathbb{N}$, $y_i\in\{0,1\}$, and II wins iff $\ \overline{x} \in A \iff \overline{y}\in Q$.

I'll write the answer as a series of hints (hover to unveil); when you are done I will edit it to show them.

Preliminary observation:

Since $A$ is $F_\sigma$, there are countably many pruned trees on $\mathbb{N}$, $T_n$ ($n\in \mathbb{N}$) such that $A=\bigcup_n [T_n]$.

First real hint:

Player II will play in order to “miss” elements from $Q$ as Player I leaves the trees $T_n$ behind. That is, II must ensure that in the limit, if Player I is to avoid every tree, the partial plays $\overline {y} \restriction m = (y_0,\dots,y_{m-1})$ must avoid each element from the countable set $Q$.

How to make that work, easy case:

If at some point the partial play by I doesn't belong to any of the trees, then II must play in order to dodge all elements of $Q$. This is easy since there are continuum many choices for the final play $\overline{y}$.

Otherwise,

for each $m$ there is a minimum $n$ such that $\overline{y} \restriction m \in T_n$; call it $n_m$. Enumerate $Q=\{q^{(k)} : k\in\mathbb{N}\}$. The strategy for II is to keep choosing longer and longer initial segments of some $q^{(k)}\in Q$ while the $n$'s remains constant. If $n_m<n_{m+1}$, take $q'\in Q$ with the least $k$ such that the partial play is consistent with $q'$, i.e., $\overline{y}\restriction (m+1)$ is an initial segment of $q'$. Then II continues to take successive elements of $q'$ until $n$ increases again. Minimality of $k$ ensures that if $n$ tends to infinity, II will avoid every element of $Q$.