Is the set of subsequences of branches through a tree Borel? 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$).
 A: 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.
