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](https://wwwmath.uni-muenster.de/u/jclemens/public/Papers/aboveBorel.pdf) 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.



Equality of Borel sets
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$.


