# Set of perfect subsets of a Borel set

Let $$\mathbb{P}$$ be the set of all perfect (i.e., every node has incomparable successors) subtrees of the full binary tree $$2^{<\omega}$$. We can endow $$\mathbb{P}$$ with a Borel structure by considering it as a subspace of $$2^{2^{<\omega}}$$ with the product topology.

If $$p\in\mathbb{P}$$, let $$[p]$$ denote the set of infinite branches through $$p$$, a nonempty perfect subset of $$2^{\omega}$$.

Question: Given a Borel subset $$B\subseteq 2^\omega$$, is the set $$S_B=\{p\in\mathbb{P}:[p]\subseteq B\}$$ necessarily Borel?

Some observations:

• $$S_B$$ is $$\mathbf{\Pi}^1_1$$ (i.e., co-analytic), so this is equivalent to asking if $$S_B$$ is also $$\mathbf{\Sigma}^1_1$$ (i.e., analytic).

• If $$B$$ is open, then $$S_B$$ is Borel: Let $$\{t_n:n\in\omega\}$$ be finite binary strings such that $$B$$ is the union of the corresponding basic clopen sets $$\mathcal{N}_{t_n}$$. Then, $$p\in\mathbb{P}$$ if and only if every node in $$p$$ is comparable to some $$t_n$$; this is a Borel condition. It is likewise easy to see that if $$B$$ is closed, then $$S_B$$ is Borel.

• If you consider the collection $$\{B\subseteq 2^\omega:S_B\text{ is Borel}\}$$, it contains the open sets (by the previous bullet) and it is closed under countable intersections, so it suffices to show that it is closed under complements.

• One strategy to find a counterexample might be to embed trees $$T$$ on $$\omega$$ into $$2^{<\omega}$$, via some nice map $$f$$, and find a Borel $$B$$ such that $$T$$ is well-founded if and only if $$[f(T)]\in B$$.

• Though I don't have time right now to work out details, I think your last observation, about coding well-foundedness into the question, should work. Have you considered taking $B$ to consist of those sequences $x\in2^\omega$ in which only finitely many terms are 1? The idea is that an $x$ with infinitely many 1's codes an element of $\omega^\omega$, so to say that $[p]\subseteq B$ is to say that no element of $\omega^\omega$ corresponds to a path through $p$. (Apologies if I've overlooked something and this $B$ is too simplistic.) Jul 31 '19 at 14:22
• Andreas Blass: I had thought about that. One issue is that the embedding of $\omega$ trees into $2^{<\omega}$ I had in mind didn't map onto the perfect trees. You would need to decorate the dead ends of the trees with something to keep them perfect, and then $B$ would no longer work. Jul 31 '19 at 16:39

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.

• The embedding in the second paragraph seems to map $\omega^{<\omega}$ to the set of all those nodes in $2^{<\omega}$ whose last entry is $0$. I don't see how you can have (at the end of the next paragraph) "a finite segment which ensures that any extension is not in this image." You can always extend a node by appending a single $0$ and the result will be in the image. Aug 2 '19 at 0:12
• I think that it can be fixed, replacing the 0s with 00s, and then using a pattern like 101 to mark a leaf. I will work on it. Aug 2 '19 at 14:21
• Ah! I think you mean that if $x$ is a path through $T$ then $001^{x_0}001^{x_1}00\cdots$ is a path through $f(T)$ which is not in $B$ and vice versa. Aug 2 '19 at 17:21
• I think $f(T)$ can fail to be perfect if $T$ has no leaves and is not itself perfect. There is a way to remedy this: let $T'$ be the downward closure of $\{(t_0+1,\ldots,t_{k-1}+1,0) : (t_0,\ldots,t_{k-1}) \in T\}$. Then $T$ is well founded iff $T'$ is wellfounded since a path through $T'$ can't have any $0$s. Then $f(T')$ is always perfect since $T'$ is the downward closure of its set of leaves. Aug 2 '19 at 17:49
• Ok. Combining these suggestions, define $f(T)$ to be the downward closure of the set of all $001^{t_0+1}001^{t_1+1}\cdots001^{t_{k-1}+1}01\bar{s}$ where $(t_0,\ldots,t_{k-1}) \in T$ and $\bar{s} \in 2^{<\omega}$ is arbitrary. And then let $B$ be the set of $x \in 2^{\omega}$ that contain $101$ somewhere. Aug 2 '19 at 18:02

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.

• I would like to see the argument that "$[p]\cap B$ is comeager in $[p]$" is a Borel question. Would you mind sharing (either appended to your answer or in the comments here)? Aug 2 '19 at 23:25
• @IianSmythe If $B_0 \subseteq B_1 \subseteq \cdots$ are Borel sets with union $B$, define $p'$ to consist of all $t \in p$ such that, for every $n$, $[p_t] \cap B_n$ is not comeager in $[p_t]$. Then $[p]\cap B$ is comeager in $[p]$ iff $[p']$ is nowhere dense in $[p]$, which is a $\Pi^0_2$ check as explained above. (The reasoning for this is basically that explained in the paragraph that starts with "Topologically".) Denoting by $S^*_{B_n}$ the set of all $p$ such that $B_n \cap [p]$ is comeager in $[p]$, we see that if each $S^*_{B_n}$ is Borel, then $S^*_B$ is Borel as well. [...] Aug 2 '19 at 23:42
• [...] As in your second bullet, it is easy to see that $S_B^*$ is Borel when $B$ is open. When $B$ is closed, we actually have $S_B^* = S_B$, which is Borel. The Baire Category Theorem gives that $S_B^* = \bigcap_{n < \omega} S_{B_n}^*$ when $B = \bigcap_{n<\omega} B_n.$ From the previous comment, we get countable unions. So the class of all $B$ such that $S^*_B$ is Borel contains all open sets, all closed sets and is closed under both countable intersections and countable unions. So this includes all Borel sets. Aug 2 '19 at 23:47