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$
2
  • $\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$ Commented Jul 31, 2019 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$ Commented Jul 31, 2019 at 16:39

2 Answers 2

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$
11
  • 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$ Commented Aug 2, 2019 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$ Commented Aug 2, 2019 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$ Commented Aug 2, 2019 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$ Commented Aug 2, 2019 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$ Commented Aug 2, 2019 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$
3
  • $\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$ Commented Aug 2, 2019 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$ Commented Aug 2, 2019 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$ Commented Aug 2, 2019 at 23:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .