Let $T$ be pruned subtree of $\omega^{<\omega}$. For my cases of interest, we may assume that $T$ is infinitely branching at every node, and consists of increasing sequences.

Let $A=\{x\in\omega^{\omega}:\exists y\in[T](x \text{ is a subsequence of } y)\}$, where $[T]$ denotes the (closed) set of infinite branches through $T$. Is $A$ necessarily a Borel set?

Clearly, $A$ is analytic. It might be useful to note the following: Given an infinite increasing $x\in\omega^\omega$, let $T'(x)=\{s\in T: x\upharpoonright m(s) \text{ is a subsequence of } s\}$, where $m(s)$ is the least integer $m$ such that $x(m)$ is greater than the last (greatest) entry of $s$. Then, $T'(x)$ is a tree and $x\in A$ if and only if $T'(x)$ is ill-founded. This doesn't improve the complexity, but might suggest how to show that $A$ is proper analytic (for certain choices of $T$).


With your assumption that the tree consists of increasing sequences only, then the answer is yes, this is Borel. The reason is that we can identify whether or not $x$ is a subsequence of a branch through the tree simply by checking the arithmetic-in-$T$ condition that every finite initial segment of $x$ is a subsequence of a node on the tree. We don't need any real quantifiers. To see this, suppose that for every $n$, we have that $x\upharpoonright n$ is a subsequence of some node of the tree $t_n\in T$. We may assume that the final node of $x\upharpoonright n$ is the last element of $t_n$. Let $T'$ be the tree of initial segments of the $t_n$'s, which is a subtree of $T$. Note that because the sequences are all increasing, it follows that $T'$ is finitely branching, because no initial segment of any $t_n$ can be extended in $T'$ so as to skip over the next higher element of $x$. So we have essentially reduced to the case where the tree is finitely branching. In particular, it follows that $[T']$ is sequentially compact. For each $n$, pick $y_n\in[T']$ with $x\upharpoonright n\subset y_n$. Because $T'$ is sequentially compact, there is a convergent subsequence, and so we may find a single $y\in [T']$ with unboundedly many $x\upharpoonright n$ contained in $y$. Thus, $x$ is a subsequence of $y$, which is a branch through $T'$ and hence through $T$, as desired. So the set is arithmetically definable from the tree and hence Borel.

If you don't insist on increasing sequences, then I believe the set of subsequences can be complete analytic, and I can explain this if you want.

  • $\begingroup$ Thanks Joel. While I don't need it at the moment, it might be nice to have a sketch of the argument for why the set can be complete analytic in the not-necessarily increasing case. $\endgroup$ – Iian Smythe Mar 8 '16 at 15:32
  • $\begingroup$ OK, I'll try to write something up later. Nice question! $\endgroup$ – Joel David Hamkins Mar 8 '16 at 15:56

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.