Borel hierarchy and tail sets Let $A$ be a finite set, and let $A^\infty$ be the set of all sequences $(a_n)_{n=1}^\infty$ of elements of $A$.
A set $B \subseteq A^\infty$ is a tail set if for every two sequences $\vec a, \vec b \in A$ that differ in finitely many coordinates, either both are in $A$ or both are not in $A$.
Question: How high can we find tail sets in the Borel hierarchy? That is, do tail sets can be found only in the first $\alpha$ levels of the hierarchy for some ordinal $\alpha$ (maybe even some finite ordinal $\alpha$), or can we find them as high as we look?
 A: Here is an example: Let $A=\{0,1\}$ and for any $x\in \{0,1\}^{\omega}$, let $n<_x m$ if $x(2^n\cdot 3^m)=1$. For any countable ordinal $\alpha$,   let $x\in U_{\alpha}$ if there is some $l$ so that $<_x$ over the set $\{n\mid n>l\}$ codes a well order $\leq \alpha$.
Now for any Borel set $B$, there is real $z$ so that $B$ is $\Delta_1^1(z)$ and so there is a recursive function $\Phi$ and a $z$-recursive ordinal $\alpha$ so that $x\in B\Leftrightarrow \Phi^{x\oplus z} \mbox{codes a well order} \Leftrightarrow \Phi^{x\oplus z} \mbox{codes a well order} \leq \alpha$. Moreover   $x\not\in B\Leftrightarrow \Phi^{x\oplus z} \mbox{codes a linear order with an infinite descending subsequence}$. 
Now let $\Psi$ be a $z$-recursive function so that $\Phi^{x\oplus z}$ codes $n<m$ iff $\Psi^{x\oplus z}(2^n\cdot 3^m)=1$; otherwise $\Psi^{x\oplus z}(2^n\cdot 3^m)=0$.
Then it is clear that for any $x$, $x\in B$ implies $\Psi^{x\oplus z}\in U_{\alpha}$. For a contradiction, suppose that $x\not\in B$ and $\Psi^{x\oplus z} \in U_{\alpha}$ for some $x$. Then $\Phi^{x\oplus z}$ codes a linear with an infinite descending subsequence over $\{n\mid n>l\}$. Then,    for arbitrarily large $l$,    $\Psi^{x\oplus z}$ contains an infinite descending subsequence, a contradiction. 
So $x\in B$ if and only if $\Psi^{x\oplus z}\in U_{\alpha}$.  
I think that by a more complicated argument, it can be shown that this is true for any countable Borel equivalence relation.
