Equality of Borel sets

Question

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.

Answer 1

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