7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Andreas Blass Jul 31 '19 at 14:22
  • $\begingroup$ 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. $\endgroup$ – Iian Smythe Jul 31 '19 at 16:39
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Andreas Blass Aug 2 '19 at 0:12
  • $\begingroup$ 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. $\endgroup$ – Iian Smythe Aug 2 '19 at 14:21
  • 1
    $\begingroup$ 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. $\endgroup$ – François G. Dorais Aug 2 '19 at 17:21
  • 1
    $\begingroup$ 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. $\endgroup$ – François G. Dorais Aug 2 '19 at 17:49
  • 1
    $\begingroup$ 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. $\endgroup$ – François G. Dorais Aug 2 '19 at 18:02
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Iian Smythe Aug 2 '19 at 23:25
  • 1
    $\begingroup$ @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. [...] $\endgroup$ – François G. Dorais Aug 2 '19 at 23:42
  • 1
    $\begingroup$ [...] 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. $\endgroup$ – François G. Dorais Aug 2 '19 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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