1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ – Ville Salo Apr 6 '20 at 9:48
  • $\begingroup$ 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.) $\endgroup$ – Ville Salo Apr 6 '20 at 9:56
  • $\begingroup$ @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.) $\endgroup$ – Will Brian Apr 6 '20 at 12:14
  • $\begingroup$ 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. $\endgroup$ – Ville Salo Apr 6 '20 at 12:18
  • $\begingroup$ 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$. $\endgroup$ – Ville Salo Apr 6 '20 at 12:21
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.