# Hyperfinite equivalence relation

In descriptive set theory and related areas of mathematics, a hyperfinite equivalence relation on a standard Borel space X is a Borel equivalence relation E with countable classes, that can, in a certain sense, be approximated by Borel equivalence relations that have finite classes.

## Definitions

Definition 1. Let X be a standard Borel space, that is; it is a measurable space which arises by equipping a Polish space X with its σ-algebra of Borel subsets (and forgetting the topology). Let E be an equivalence relation on X. We will say that E is Borel if E is a Borel subset of the cartesian product of X with itself, when equipped with the product σ-algebra. We will say that E is finite (respectively, countable) if E has finite (respectively, countable) classes.
The above names might be misleading, since if X is an uncountable standard Borel space, the equivalence relation will be uncountable when considered as a set of ordered pairs from X.
Definition 2. Let E be a countable Borel equivalence relation on a standard Borel space X. We will say that E is hyperfinite if $E=\bigcup _{n\in \mathbb {N} }F_{n}$, where $F_{n}$ is an increasing sequence of finite Borel equivalence relations on X.
Intuitively, this means that there is a sequence finite equivalence relations on X, each finer than its predecessors, approximating E arbitrarily well.

## Discussion

A major area of research in descriptive set theory is the classification of Borel equivalence relations, and in particular those which are countable. Among these, finite equivalence relations are considered to be the simplest (for instance, they admit Borel transversals). Therefore, it is natural to ask whether certain equivalence relations, which are not necessarily finite, can be approximated by finite equivalence relations. This turns out to be a notion which is both rich enough to encapsulate many natural equivalence relations appearing in mathematics, yet restrictive enough to allow deep theorems to develop.
It is also worthwhile to note that any countable equivalence relation E can be written down as an increasing union of finite equivalence relations. This can be done, for instance, by taking a partition of every class into classes of size two, then joining two classes in the new equivalence relation which are within the same E-class to form a partition with classes of size four, and so forth. The key observation is that this process requires the axiom of choice in general, and therefore it is not clear that this process generates Borel approximations. Indeed, there are countable Borel equivalence relations that are not hyperfinite, and so in particular the process described above will fail to generate Borel equivalence relations approximating the larger equivalence relation.

## Examples and non-examples

* Any finite Borel equivalence relation is hyperfinite. Indeed, it is a finite approximation of itself.
* A subequivalence relation of a hyperfinite equivalence relation is hyperfinite.
* Suppose G is a locally finite group acting Borel-measurably on a standard Borel space X. Then a filtration $F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq ...\subseteq G$ into finite subgroups naturally gives rise to a filtration of the orbit equivalence relation of the action of G on X into finite Borel equivalence relations, thereby proving its hyperfiniteness.
* If E is a countable equivalence relation and $E'\subset E$ is hyperfinite and of finite index (meaning that every E-class contains finitely many E'-classes), then E is hyperfinite.
* Any countable Borel equivalence relation that admits a Borel transversal is hyperfinite; this can be shown by a simple application of the Feldman-Moore theorem.
* Any Borel action of the integers on a standard Borel space generates a hyperfinite orbit equivalence relation (recall that a Borel action of a countable group G on a standard Borel space X is a Borel-measurable action $a:G\times X\rightarrow X$, where G is equipped with the σ-algebra of all its subsets). Moreover, it turns out that any hyperfinite equivalence relation is equal to the orbit equivalence relation generated by some Borel action of the integers, making this an equivalent definition to hyperfiniteness that is often more accessible.
* More generally, any Borel action of a countable abelian group on a standard Borel space induces a hyperfinite orbit equivalence relation.
* If F is a countable Borel equivalence relation on a standard Borel space X, E is a hyperfinite equivalence relation on a standard borel space Y and $f:X\rightarrow Y$ is a Borel reduction of F to E, then F is hyperfinite (recall that $f$ as above is a Borel reduction whenever it satisfies $\forall x,y\in X,f(x)Ef(y)\iff xEy$). Note that the above does not hold if we remove the assumption of F being countable; the equivalence relation on the real line identifying every two points is Borel and can be reduced to any other Borel equivalence relation, and in particular to any hyperfinite Borel equivalence relation, but it has an uncountable class, so it cannot be hyperfinite.
* Any Borel action of a finitely-generated group with polynomial growth on a standard Borel space induces a hyperfinite orbit equivalence relation.
* The action of a finitely-generated hyperbolic group on its Gromov boundary is hyperfinite.
* Any countable Borel equivalence relation can be restricted to a comeagre set on which it is hyperfinite. Explicitly, this means that one can remove a collection of equivalence classes which is meagre, and get that the equivalence relation is hyperfinite on the remaining space.
* Any group which is not amenable admits a Borel action on a standard Borel space which induces an equivalence relation that is not hyperfinite.
* The action of the free group $F_{2}$ on two generators on the space $2^{F_{2}}$ by the shift maps is not hyperfinite. This fact is often considered to be a combinatorial variant of the Banach–Tarski paradox.

## Open problems
### Weiss's conjecture

The above examples seem to indicate that Borel actions of "tame" countable groups induce hyperfinite equivalence relations. Weiss conjectured that any Borel action of a countable amenable group on a standard Borel space induces a hyperfinite orbit equivalence relation. While this is still an open problem, some partial results are known.

### The union problem

Another open problem in the area is whether a countable increasing union of hyperfinite equivalence relations is hyperfinite. This is often referred to as the union problem.
Under certain conditions, it is known that a countable increasing union of hyperfinite equivalence relations is hyperfinite. For example, if the union of the equivalence relations has a property known as "Borel-boundedness" (which roughly means that any Borel assignment of functions $f:\mathbb {N} \rightarrow \mathbb {N}$ to points on the space can be "eventually bounded" by such a Borel assignment which is constant on equivalence classes), then it is hyperfinite. However, it is unknown whether every such union satisfies this property.

## Measure-theoretic results

Under the assumption that the underlying space X is equipped with a Borel probability measure μ and that one is willing to remove sets of measure zero, the theory is much better understood. For instance, if the equivalence relation is generated by a Borel action of a countable amenable group, the resulting orbit equivalence relation is "μ-hyperfinite", meaning that it is hyperfinite on a subset of the space of full measure (it is worthwhile to note that the action need not be measure-preserving, or even quasi-measure preserving). Since every countable Borel equivalence relation E on a standard non-atomic Borel probability space (X,$\mu$) that admits a Borel transversal is a finite equivalence relation on a subset of full measure (this is essentially Feldman-Moore, together with Vitali's argument in his classical proof of the non-existence of a nontrivial invariant measure on the $\sigma$-algebra of all subsets of the real line), the above shows us that unlike equivalence relations which admit transversals, many examples of group actions which appear naturally in ergodic theory give rise to hyperfinite orbit equivalence relations (in particular, whenever the underlying space is a standard Borel space and the group is countable and amenable).
Similarly, a countable increasing union of hyperfinite equivalence relations on such a space is μ-hyperfinite as well.