# Universal countable Borel equivalence relations with an eye toward finitely generated groups

In the previous post, I discussed a technique due to Neumann and Neumann for embedding any countable group into a 2-generated group, and mentioned in passing that they used the same ideas to create a finitely generated 3-solvable non-Hopfian group.  This construction turned out to be very useful to my own research, but to describe how requires a few definitions, which I’ll get to in a moment.  The aim of this post is not really to discuss my research, but instead to gear up to look at a related result, which I hope to understand better.  That will be the subject of the next post.  Perhaps it will help with my research again.

I’ve previously mentioned Borel equivalence relations in passing.  Let’s talk about them in a bit more detail.

Definition: If $X$ is a Polish space (or more generally, a standard Borel space) and $E$ is an equivalence relation on $X$, then we say $E$ is Borel if $E$ is Borel as a subset of $X\times X$.

Definition: We call an equivalence relation countable if all of its equivalence classes are countable.

My research focuses on countable Borel equivalence relations.  Many interesting equivalence relations are countable Borel; for example Turing equivalence, eventual equality of infinite binary sequences (known as $E_0$, which you may have seen in a hat problem), isomorphism of finitely generated groups, or orbit equivalence relations arising from Borel actions of countable groups.  (In fact, a theorem of Feldman and Moore says that every countable Borel equivalence relation can be realized as the orbit equivalence relation arising from a Borel action of a countable group!)  When discussing Borel equivalence relations, we are mainly interested in comparing them using the notion of a Borel reduction.

Definition: Suppose $E$ and $F$ are Borel equivalence relations on Polish spaces $X,Y$.  Then a Borel homomorphism from $E$ to $F$ is a Borel map $f\colon X \rightarrow Y$ such that

$\displaystyle x \mathbin{E} y \,\, \Rightarrow \,\, f(x) \mathbin{F} f(y)$

Borel reduction from $E$ to $F$ is a map $f\colon X \rightarrow Y$ such that

$\displaystyle x \mathbin{E} y \,\, \Leftrightarrow \,\, f(x) \mathbin{F} f(y)$

If $E$ Borel reduces to $F$, we write $E \leq_B F$.

The idea behind a Borel reduction is that if $E \leq_B F$, then $F$ is at least as complicated as $F$.  If one could classify the elements of $Y$ up to $F$-equivalence, then using the Borel reduction you could also classify the elements of $X$ up to $E$-equivalence.  (Note that this is not so different from the justification for using poly-time reductions in complexity theory to compare the difficulty of decision problems.)  The point of keeping things Borel that Borel objects are in some sense explicit.  Using the axiom of choice one can show there exist reductions between any two equivalence relations with the same number of equivalence classes, but the reductions are in general not Borel.  In fact, there are a whole host of results establishing non-reducibility of certain Borel equivalence relations.  A relatively simple example is that equality on $2^\mathbb{N}$ Borel reduces to $E_0$, but not vice versa, as can be seen using Baire category or measure arguments.

Definition: A countable Borel equivalence relation $E$ is universal (or complete) if for any countable Borel equivalence relation $F$, $F\leq_B E$.

To extend the analogy with complexity theory, a universal countable Borel equivalence relation (if it exists) relates to countable Borel equivalence relations in the same way an NP-complete decision problem relates to NP decision problems; it’s as complicated as it possibly could be given its complexity.  Note that one could easily make a similar definition for any class of Borel equivalence relations.  Indeed, this is done.  Some classes have universal equivalence relations and some don’t.

Theorem (Dougherty-Jackson-Kechris): There is a universal countable Borel equivalence relation.

Once one has one example of universal countable equivalence relation $E_\infty$, then one can show another countable Borel equivalence relation $E$ is universal simply by showing $E_\infty \leq_B E$, and indeed this is how most proofs of universality proceed.

Theorem (Thomas-Velickovic): Isomorphism of finitely generated groups is a universal countable Borel equivalence relation.

There are many other examples, but this is the one which interests us in this post.  Finitely generated groups can be quite complicated, and this result puts some rigor behind that intuition.  The proof rather heavily uses free products with amalgamation.  These are “large” from a group-theoretic standpoint (for example, they all contain free non-abelian subgroups), and so seen as complicated in and of themselves.  So it’s not surprising that isomorphism of these sorts of groups is complicated.  But what about finitely generated groups which are not as complicated?  Is the isomorphism relation still complex?  There has been some progress towards answering this, but we need one more definition.

Definition: A countable Borel equivalence relation $E$ is weakly universal if for any countable Borel equivalence relation $F$ there is a countable-to-1 Borel homomorphism from $F$ to $E$.  Equivalently (this is not obvious), $E$ is weakly universal if it contains a universal countable equivalence relation.

Clearly every universal countable Borel equivalence relations is weakly universal.  The idea behind looking at countable-to-1 Borel homomorphisms from an equivalence relation $E$ to another equivalence relation $F$ is that although these are not necessarily Borel reductions, they can’t fail too badly to be such, sending at most countably many $E$-inequivalent elements to $F$-equivalent elements .  Compare this with $E_0$ and equality on $2^\mathbb{N}$; every Borel homomorphism from $E_0$ to equality must send a measure 1 set to the same point!

Whether or not every weakly universal equivalence relation is in fact universal is a notorious open problem.  A positive answer would make many proofs of universality trivial (or at least much simpler); creating Borel homomorphisms from a universal $E$ to another Borel equivalence relation $F$ is always the easy part, it’s making these maps reductions which is trickier.  A negative answer follows from Martin’s Conjecture, a stubbornly open conjecture in its own right, but which seems to provide excellent tools for analyzing weakly universal equivalence relations.  In any event, weakly universal equivalence relations are pretty high up in the $\leq_B$-hierarchy (which is not at all linear, so this should be understood as an imprecise-but-ultimately-mathematically-defensible statement).

So, back to isomorphism of finitely generated groups.  We have the following:

Theorem (Thomas-Williams): Isomorphism of Kazhdan groups is weakly universal.

Theorem (Williams): Isomorphism of finitely generated 3-solvable groups is weakly universal.

In both of these cases, we expect that the relations are in fact universal, but as I mentioned, making Borel reductions is a bit trickier than making Borel homomorphisms, which is all that is needed to prove weak universality.  My proof of the second theorem makes use of a modification of the Neumann and Neumann construction mentioned at the beginning of this post; in fact to modern eyes their construction already showed that $E_0$ Borel reduces to isomorphism of finitely generated 3-solvable groups, a non-trivial lower bound on the complexity.  It is known that $E_0$ is strictly below any weakly universal equivalence relation with respect to Borel complexity, so my result is a stronger lower bound than Neumann and Neumann’s.

It would be nice to make the leap from weak universality to universality.  In the next post, we’ll look at how a different group-theoretic equivalence relation was shown to be universal in the hopes of learning something we can use.