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

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.

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

• Thanks! This is brilliant!
– Y.Z.
Commented Aug 24, 2022 at 20:48

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.

• Thanks! This is a really neat. (I'll have to convince myself that $\{r: R_r \equiv S\}$ is Borel but as you said it is a good exercise.)
– Y.Z.
Commented Aug 24, 2022 at 21:07