# 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?

• Let $A = \{0,1\}$, let $U \subset A^{\infty}$ be any Borel. Construct $t(U) \subset A^{\infty}$ by letting $x \in t(U)$ iff $\sum x = \infty$, and when $10^n1$ appears in $x$ it does infinitely many times, and the characteristic sequence of $n$ s.t. $10^n1$ appears is in $U$. Clearly $t(U)$ is tail, and is Borel because can be constructed just like $U$, replacing basic opens by $\Sigma^0_2$s stating appearance of words of form $1 0^n 1$, and recurrence. There is continuous $f : A^{\infty} \to A^{\infty}$ reducing $U$ to $t(U)$, so if $t(U)$ is $Q^0_\alpha$ then so is $f^{-1}(t(U)) = U$. – Ville Salo Apr 6 '20 at 9:48
• Slightly wrong, since changing finitely many can break the recurrence condition. I suppose just drop the recurrence assumption. (Also I'm not sure this is a research level question.) – Ville Salo Apr 6 '20 at 9:56
• @VilleSalo: I'm a little confused by your comment. But I do know that in $\mathcal P(\mathbb N)$, the set of all $A \subseteq \mathbb N$ with positive upper density is a tail set in $\Sigma^0_3 \setminus \Sigma^0_2$. (I can't tell if this fact contradicts your claim or not.) – Will Brian Apr 6 '20 at 12:14
• So maybe it should be $\Sigma^0_3$ instead of $\Sigma^0_2$, I wrote $\Sigma^0_2$ and was going to think about what the correct number is but apparently didn't. We agree it is a Borel set, though, that's all we need. – Ville Salo Apr 6 '20 at 12:18
• What I believe is correct is: encode a set $U$ into those distances between $1$s that appear infinitely many times. The resulting set is Borel, tail, and at least as high as $U$. – Ville Salo Apr 6 '20 at 12:21

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