Is the set of subsequences of branches through a tree Borel?

Question

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

Answer 1

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.