User:Boris Tsirelson/sandbox2

Negative results

$\newcommand{\M}{\mathscr M}$ As was noted, the normal form of an object $M\in\M$ is a "selected representative" from the equivalence class $[M]$, usually possessing some nice properties. The set of all these "representatives" intersect each equivalence class exactly once; such set is called a transversal (for the given equivalence relation). Existence of a transversal is ensured by the axiom of choice for arbitrary equivalence relation on arbitrary set. However, a transversal in general is far from being nice. For example, consider the equivalence relation "$x-y$ is rational" for real numbers $x,y$. Its transversal (so-called Vitali set) cannot be Lebesgue measurable!

Typically, the set $\M$, endowed with its natural σ-algebra, is a standard Borel space, and the set $\{(x,y)\in\M\times\M:x\sim y\}$ is a Borel subset of $\M\times\M$; this case is well-known as a "Borel equivalence relation". Still, existence of a Borel transversal is not guaranteed (for an example, use the Vitali set again).

Existence of Borel transversals and related properties of equivalence relations are investigated in descriptive set theory. According to [K, Sect. 4], a lot of work in this area is philosophically motivated by problems of classification of objects up to some equivalence. A number of negative results are available. They show that in many cases, classification by a Borel transversal is impossible, and moreover, much weaker kinds of classification are also impossible. For example, a negative result is available for isomorphism of locally finite connected graphs (or trees), see [K, Sect. 7, Item (B)(iii)].

[K]	Alexander S. Kechris, "New directions in descriptive set theory", Bull. Symb. Logic 5 (1999), 161–174. Zbl 0933.03057