Suppose $E$ and $F$ are Borel equivalence relations on Polish spaces $X$, $Y$, resp. Say that $E$ is surjectively Borel reducible to $F$ iff there is a Borel surjection $f:X \to Y$ such that $xEy$ iff $f(x) F f(y)$. This is (at least on the surface) stronger than normal Borel reducibility, weaker than Borel isomorphism.

What do we know about this reducibility? If $E$ is effectively Borel with only countably many classes, is $E$ effectively surjectively reducible to the trivial equivalence relation on $\omega$?

edit: Probably this is the version I am interested in: Say $E$ is strongly Borel reducible to $F$ iff $E$ reduces to $F$ via a Borel $f$ such that the range of $f$ is Borel. When $Y=\omega$ and $E$ has infinitely many classes, "$E$ is effectively stongly Borel reducible to the relation $F$ on $Y$" exactly means "$E$ is effectively surjectively Borel reducible to $F$".

edit again: Actually, the arXiv version of Fokina-Friedman-T¨ornquist "The Effective Theory of Borel Equivalence Relations" probably has a (minor) mistake. On page 9, the equivalence relation $E^*$ is $\Pi^1_1$, not Hyp. The $\Sigma^1_1$ line
$$(\exists x_0,x_1) ( x_0 \in H(d_0) \wedge x_1 \in H(d_1) \wedge x_0 E x_1)$$ fails when $H(d_0) = \emptyset$. The proof of Proposition 2 can be easily repaired, but the issue of empty set is worth attention when we seriously require the range being $\Delta^1_1$.

  • $\begingroup$ If a Borel equivalence relation $E$ has only countably many equivalence classes, isn't each class Borel? $\endgroup$ – Noah Schweber Mar 15 '15 at 16:37
  • $\begingroup$ Yes. But the range of the reduction is $\Sigma^1_1$, if $E$ is effective Borel. I wonder if it is possible to make the range $\Delta^1_1$. $\endgroup$ – Yizheng Zhu Mar 15 '15 at 16:57

The answer is no. The question is basically asking for a $\Delta^1_1$ transversal for a $\Delta^1_1$ Borel equivalence relation with only countably many classes. Let $A$ be a closed subset of $\mathbb{R}\times \omega$ whose projection to the second coordinate is not $\Delta^1_1$. Put $(x,m)E(y,n)$ iff either $(x,m)\notin A \wedge (y,n)\notin A$ or $(x,m)\in A \wedge (y,n)\in A\wedge m=n$. Then $E$ does not have a $\Delta^1_1$ transversal.

| cite | improve this answer | |

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.