Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
3 of 5
added 164 characters in body
Joel David Hamkins
  • 246.6k
  • 48
  • 808
  • 1.5k

The answer is no, and this kind of question is part of the subject of the theory of Borel equivalence relations.

The equivalence relations $\sim$ for which there is a Borel function $g:X\to Z$ into a standard Borel space $Z$, with $x\sim y\iff g(x)=g(y)$ are, by definition, precisely the smooth equivalence relations (see the definition on page 5 of the link above). But there are equivalence relations that are not smooth, such as the relation $E_0$ of eventual equality of infinite binary sequences. You can find the arguments that various relations are not smooth in the article to which I linked (see also page 5 of these notes of Simon Thomas and Scott Schneider).

The subject of Borel equivalence relations studies the entire hierarchy of Borel equivalence relations under Borel reducibility, which is a kind of complexity notion that in effect analyzes the relative difficulty of classification problems in mathematics, and the smooth equivalence relations occupy a region near the very bottom of the hierarchy, among the simplest relations.

Joel David Hamkins
  • 246.6k
  • 48
  • 808
  • 1.5k