I would like to understand the complexity of "equality of Borel sets". By complexity, I mean the complexity in the sense of Borel reducibility.

Of course, since there is no standard Borel space of Borel sets of a Polish space, we have to work with Borel codes to make sense of "equality of Borel sets". Here is a nice paper by Clemens. In Section 1, he explains how we construct the space of Borel codes and what "equality of Borel sets" means (see Definition 8).

Let $E_B$ be the equivalence relation on Borel codes defined as follows: Two Borel codes are $E_B$-equivalent if and only if they define the same Borel set. It can be seen that the equivalence relation $E_B$ on the set of Borel codes is not a Borel equivalence relation (for example, see the remarks in Page 5). The set of Borel codes is not even a Borel set.

On the other hand, if we fix some $\alpha < \omega_1$, then the set ${BC}_{\alpha}$ of Borel codes of rank less than $\alpha$ is a Borel set. My question is whether or not $E_{\alpha}$, equivalence of Borel codes of rank less than $\alpha$, is Borel?

I specifically want to know if this is true when $\alpha$ is finite (more specifically, $\alpha=4$). My first reaction was to carry out an induction argument trying to bound $E_{\alpha}$ from above by using jumps or powers of the previous bounds but I can't seem to figure out what to do. I suspect that these relations might not be Borel even for small finite values.

  • $\begingroup$ I am interested in the paper of Clemens, however I cannot click it. Would you like to share it with me again? $\endgroup$ – user97597 Oct 31 '16 at 16:06
  • 1
    $\begingroup$ Dear User, It seems that the link I provided is not working anymore and I unfortunately do not have a copy of the paper mentioned in the OP. However, you can reach Clemens' dissertation here and it seems to contain the material mentioned in the OP. $\endgroup$ – Burak Oct 31 '16 at 16:25

Nice question!

Unfortunately, this relation is not Borel. Indeed, it is $\Pi^1_1$-complete, even at very low levels of the hierarchy.

To see this, suppose that $x$ is a real coding a binary relation $E_x$ on the natural numbers $\mathbb{N}$. Let $W_x$ be the set of reals $y$ coding an infinite $E_x$-descending sequence. So $W_x$ is a Borel set with very low complexity, since we just need to say that $y_{n+1} \mathrel{E_x} y_n$ for all $n$, and this is amounts to a countable intersection. (I'll let you determine the exact complexity.) Indeed, the Borel definition is uniform in $x$, in that there is a Borel map $x\mapsto w_x$, where $w_x$ is a Borel code for $W_x$.

But notice that the relation coded by $x$ is well-founded just in case $W_x$ is empty. So we can Borel reduce the question of well-foundedness, which is $\Pi^1_1$-complete, to the question of whether a given Borel code $w_x$ is equivalent to a fixed Borel code for the empty set.

Meanwhile, the equivalence is in general $\Pi^1_1$, since two codes are equivalent just in case, for every real $x$, and every assignment of "yes/no" to the nodes of the codes which conforms with the definition of the Borel code as to whether it contains $x$, yields the same answer. This assertion has complexity $\Pi^1_1$.

| cite | improve this answer | |
  • $\begingroup$ Nice! I was so fixated on proving that it is Borel that I did not even try showing it was not. $\endgroup$ – Burak Aug 17 '15 at 20:23

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.