a non-Borel equivalence relation whose every equivalence class is Borel

Question

Let $(X, \mathcal{A})$ be a standard Borel space where $\mathcal{A}$ is the sigma algebra of Borel sets of $X$. An equivalence relation $E$ on $X$ is Borel if it is a Borel subset of $X^2$ (with respect to the product topology). Say $E$ is measurable (my temrinology) if every equivalence class of $E$ is a Borel set of $X$. I am curious if there is an equivalence relation on $X$ that is measurable but not Borel in this sense (my suspicion is yes but I have yet been able to prove it). Also I suspect that the converse is false as well -- there should be Borel equivalence relations that are non-measurable (given that the projections of a Borel subset is not always Borel). But again that's mere conjecture. Any hint would be much appreciated.

Answer 1

There are in fact many ways to prove that such an equivalence relation need not be Borel. Here's one that I like:

We can think of each real $r$ as representing a binary relation $R_r$ on the natural numbers. For example, think about binary expansions, with the $2^i3^j$th bit telling us the status of the pair $(i,j)$. Note that there are many ways to do this; we merely need the map $r\mapsto R_r$ to be surjective (or "surjective enough," anyways) and reasonably simple.

Fixing some such representation scheme, it's not hard to show that the set $Lin$ of $r$ such that $R_r$ is a linear order on the naturals is Borel. Consequently, the complement of $Lin$ is also Borel. Now consider the following equivalence relation $\sim$ on the reals: we set $r\sim s$ iff

• $r=s$, or

• neithe $r$ nor $s$ is in $Lin$, or

• both $r$ and $s$ are in $Lin$ and $R_r$ and $R_s$ are isomorphic well-orderings of $\mathbb{N}$.

Every $\sim$-class is Borel; the only nontrivial step is showing that whenever $S$ is a well-ordering of $\mathbb{N}$ the set $$\{r: R_r\cong S\}$$ is Borel, and this is a good exercise. But the relation $\sim$ itself is definitely not Borel, since we can tell in a "Borel-relative-to-$\sim$" way whether a real codes a well-ordering and the set of reals coding well-orderings is well-known (:P) to be non-Borel.

Answer 2

Consider equivalence relations on $\mathbb R$ for which all equivalence classes are $2$-element sets (which are of course Borel sets). There are $2^\mathfrak c$ such equivalence relations, and they are not all Borel, seeing as there are only $\mathfrak c$ Borel subsets of $\mathbb R^2$.