Set of perfect subsets of a Borel set

I believe that the answer is no, the set $S_B$ need not be Borel.

Edit: I've incorporated some of François' suggestions from the comments, which should clean up the proof.

Consider the following embedding of $\omega^{<\omega}$ into $2^{<\omega}$: For the first level, send the node $(0)$ to $(0,0)$, and for $n>0$, send the node $(n)$ to $(\underbrace{1,\ldots, 1}_{n\text{ times}},0,0)$. In general, having sent $s$ in $\omega^{<\omega}$ to $t$ in $2^{<\omega}$, send $s^{\frown}(0)$ to $t^{\frown}(0,0)$, and $s^{\frown}(n)$ to $t^{\frown}(\underbrace{1,\ldots, 1}_{n\text{ times}},0,0)$.

Define a map $f$ from $\omega$-trees to perfect binary trees as follows:

  • First, assume that every node in $T$ either has a successor which is a leaf, or has incomparable successors. Map $T$ to the downwards closure (under initial segment) of its image under the above map, except that at each leaf node, append the sequence $(1,0,1)$, followed by a copy of $2^{<\omega}$.

  • If $T$ has a node with no leaves or incomparable successors above it, replace it with $T'$, which is the downwards closure of $\{(t_0+1,\ldots,t_{k-1}+1,0):(t_0,\ldots,t_{k-1})\in T\}$. Then, $T'$ is as in the first case, and we let $f(T)$ be $f(T')$. Note that $T$ is well-founded if and only if $T'$ is, since a path through $T'$ can't have any $0$s.

This map is clearly Borel.

The image of a tree $T$ (in the first case above) under $f$ has the following property: each node in $T$ corresponds to a node in $f(T)$ ending in $(0,0)$ in $f$, and the only time an odd number of $0$s occurs in a row (with $1$s on either end) is after a leaf node.

Let $B\subseteq 2^\omega$ be the set of all binary strings which contain $(1,0,1)$ somewhere, or end in all $1$s. $B$ is $F_\sigma$.

For an $\omega$-tree $T$, $T$ has an infinite branch if and only if $f(T)$ contains an element not in $B$. In other words, if $S_B=\{p\in\mathbb{P}:[p]\subseteq B\}$, then $f(T)\in S_B$ if and only if $T$ is well-founded.

Thus, $S_B$ is $\mathbf{\Pi}^1_1$-complete, and in particular, not Borel.


This appears not to be the case: there is a $F_\sigma$ set $B$ such that $S_B$ is not Borel. This is optimal since the bullets in the question explain how $S_B$ is Borel when $B$ is $G_\delta$.

There is surely a better way to explain this. I arrived at this answer by first realizing that the answer is yes if we replace "$[p] \subseteq B$" by "$[p]\cap B$ is comeager in $[p]$" in the question. I then attempted to transform this into a positive answer to the question, and my failure to do so led to what follows.

Let $c_0 \subseteq c_1 \subseteq c_2 \subseteq \cdots$ be a sequence of nonempty subtrees of $2^{<\omega}$ with no dead ends. For a (possibly empty) tree $p \subseteq 2^{<\omega}$, define $$p' = \{ t \in p \mid (\forall n)(p_t \nsubseteq c_n)\},$$ where $p_t = \{ s \in p \mid s \subseteq t \lor t \subseteq s \}.$

Topologically: $c_0,c_1,c_2,\ldots$ is a sequence of codes for closed sets $[c_0] \subseteq [c_1] \subseteq [c_2] \subseteq \cdots$ If $U_i$ is the relative interior of $[c_i]\cap[p]$ in $[p]$, then $[p'] = [p] \setminus \bigcup_{i<\omega} U_i.$ By the Baire Category Theorem, if $[p] \cap \bigcup_{i<\omega} [c_i]$ is comeager in $[p]$ then $[p] \cap \bigcup_{i<\omega} U_i$ is open dense in $[p]$ and thus $[p']$ is nowhere dense in $[p]$.

So, as a first approximation to determining whether $[p] \subseteq \bigcup_{i<\omega} [c_i]$ we can check that $[p']$ is comeager in $[p]$. This is a $\Pi^0_2$ check: $(\forall t \in p)(\exists u \in p)(t \notin p' \land t \subseteq u).$ This is not enough however as we have merely reduced the question to whether $[p'] \subseteq \bigcup_{i<\omega} [c_i].$

We can iterate this operation: define $p^{(0)} = p,$ $p^{(\alpha+1)} = (p^{(\alpha)})',$ and $p^{(\alpha)} = \bigcap_{\beta<\alpha} p^{(\beta)}$ when $\alpha$ is a limit ordinal. Since $p$ is a countable set, there is always some $\alpha<\omega_1$ such that $p^{(\alpha+1)} = p^{(\alpha)}$ and the sequence stabilizes from then on. Let's call $p^{(\alpha)}$ the core of $p$ and lets call the first such $\alpha$ the core rank of $p$. For convenience, let's write $p^\ast$ for the core of $p$.

Note that $[p] \subseteq \bigcup_{i<\omega} [c_i]$ if and only if the core of $p$ is empty. The only if direction is follows from the observation that we always have $[p] \subseteq [p'] \cup \bigcup_{i<\omega} [c_i]$. For the if direction, notice that the core $p^\ast$, when nonempty, has the property that $p^\ast \setminus c_n$ is dense in $p^\ast$ for every $n$. So a generic path through $p^\ast$ witnesses that $[p^\ast] \subseteq [p] \nsubseteq \bigcup_{i<\omega} [c_i].$

For perfect $p$, there are $c_0 \subseteq c_1 \subseteq c_2 \subseteq\cdots$ with empty $p^\ast$ of arbitrarily large core rank with respect to $p$. For simplicity, we take $p = 2^{<\omega}.$ To get started, note that if $$c_i = \{0\}^{<\omega} \cup \{ s \in 2^{<\omega} \mid |s| > i \land (\exists j \leq i, s_j = 1)$$ then $2^\omega = \bigcup_{i<\omega} [c_i]$ and $c_0,c_1,c_2,\ldots$ has core rank $2$ with respect to $2^{<\omega}$. To get increasingly larger core ranks, given $c_{k,0} \subseteq c_{k,1} \subseteq \cdots$ for $k = 0,1,2,\ldots$ with $2^{\omega} = \bigcup_{i<\omega} [c_{k,i}].$ Define $$c_i = z \cup \bigcup\nolimits_{k<\omega} \{ 0^{k-1}1 t \mid t \in c_{k,i} \}.$$ Then $2^{\omega} = \bigcup_{i<\omega} [c_i]$ and a straghtforward inductive calculation shows that this sequence has core rank at least $\alpha+1$ where $\alpha$ is any ordinal for which there are infinitely many $k$'s where $c_{k,0},c_{k,1},c_{k,2},\ldots$ has core rank at least $\alpha$. In particular, if $c_{k,0},c_{k,1},c_{k,2},\ldots$ has core rank $\alpha_k$ and $\alpha_0 \leq \alpha_1 \leq \cdots$ then $c_0,c_1,c_2,\ldots$ has core rank $\sup_{k<\omega} (\alpha_k+1).$

Now a sequence $c_0 \subseteq c_1 \subseteq c_2 \subseteq \cdots$ can be encoded by an $f \in \omega^\omega$ in such a way that $f(n)$ determines all $c_i \cap 2^n$ at once. This is because $c_0 \cap 2^n \subseteq c_1 \cap 2^n \subseteq \cdots,$ so it suffices for $f(n)$ to encode the finitely many subsets of $2^n$ that occur in this sequence along with the first index at which they appear.

Define the universal sequence $d_0 \subseteq d_1 \subseteq d_2 \subseteq \cdots$ as follows: $t \in d_i$ if the longest initial segment of $t$ which is of the form $$1^{n_0}0s_01^{n_1}0s_1\cdots1^{n_{k-1}}0s_{k-1},$$ where each $n_j$ appropriately encodes an infinite nondecreasing sequence of subsets of $2^j$ according to the scheme above, is such that $s_0s_1\cdots s_{k-1}$ belongs to the $i$th set coded by $n_{k-1}.$

Note that if $f$ is the code for $c_0 \subseteq c_1 \subseteq c_2 \subseteq \cdots$ then the perfect set $p$ where $$[p] = \{1^{f(0)}0x_01^{f(1)}0x_11^{f(2)}0x_2\cdots \mid x \in 2^\omega\}$$ is such that $p,d_0 \cap p,d_1 \cap p, d_2 \cap p,\ldots$ is isomorphic to $2^{<\omega},c_0,c_1,c_2,\ldots$ It follows that for this sequence $d_0 \subseteq d_1 \subseteq d_2 \subseteq \cdots$ there are $p$ with $p^\ast = \varnothing$ and arbitrarily large core rank with respect to $d_0,d_1,d_2,\ldots$

Let $B = \bigcup_{i<\omega} [d_i]$, which is $F_\sigma.$ For each $\alpha<\omega_1,$ the set $S_\alpha = \{ p \mid p^{(\alpha)} = \varnothing \}$ is Borel, where $p^{(\alpha)}$ is computed with respect to $d_0,d_1,d_2,\ldots$, and if $\alpha \leq \beta < \omega_1$ then $S_\alpha \subseteq S_\beta$. We now have $S_B = \bigcup_{\alpha<\omega_1} S_\alpha$ but $S_B \nsubseteq S_\alpha$ for any $\alpha <\omega_1$. Therefore $S_B$ is not Borel.