Hyperfinite equivalence relation

<h2 id="definitions">Definitions</h2>
Definition 1. Let X be a standard Borel space, that is; it is a <a href="/facts/Measurable_space/AJ98lhT4">measurable space</a> which arises by equipping a <a href="/facts/Polish_space/CkUFcGap">Polish space</a> X with its <a href="/facts/%25CE%25A3-algebra/8LJINLNc">σ-algebra</a> of <a href="/facts/Borel_set/jvSsfpkP">Borel subsets</a> (and forgetting the <a href="/facts/Topology/2EqW47cU">topology</a>). Let E be an equivalence relation on X. We will say that E is Borel if E is a Borel subset of the <a href="/facts/Cartesian_product/BfqBWzdL">cartesian product</a> of X with itself, when equipped with the product σ-algebra. We will say that E is finite (respectively, countable) if E has <a href="/facts/Finite_set/za1newlP">finite</a> (respectively, <a href="/facts/Countable_set/Wj4DmWPv">countable</a>) 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 <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> 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
 =
 
 ⋃
 
 n
 ∈
 
 N
 
 
 
 
 F
 
 n
 
 
 
 
 {\displaystyle E=\bigcup _{n\in \mathbb {N} }F_{n}}
 
, where 
 
 
 
 
 F
 
 n
 
 
 
 
 {\displaystyle 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.

<h2 id="discussion">Discussion</h2>
A major area of research in descriptive set theory is the classification of <a href="/facts/Borel_equivalence_relation/LSy25sXx">Borel equivalence relations</a>, and in particular those which are countable. Among these, finite equivalence relations are considered to be the simplest (for instance, they admit Borel <a href="/facts/Transversal_(combinatorics)/HFg4qQfj">transversals</a>). 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 <a href="/facts/Union_(mathematics)/KVVXKfWl">union</a> of finite equivalence relations. This can be done, for instance, by taking a <a href="/facts/Partition_of_a_set/VeP9g8CA">partition</a> 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 <a href="/facts/Axiom_of_choice/1Ura2HTh">axiom of choice</a> 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.

<h2 id="examples-and-non-examples">Examples and non-examples</h2>
<ul><li>Any finite Borel equivalence relation is hyperfinite. Indeed, it is a finite approximation of itself.</li>
<li>A subequivalence relation of a hyperfinite equivalence relation is hyperfinite.</li>
<li>Suppose G is a <a href="/facts/Locally_finite_group/aLHBpa9n">locally finite</a> group acting Borel-measurably on a standard Borel space X. Then a filtration 
 
 
 
 
 F
 
 0
 
 
 ⊆
 
 F
 
 1
 
 
 ⊆
 
 F
 
 2
 
 
 ⊆
 .
 .
 .
 ⊆
 G
 
 
 {\displaystyle F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq ...\subseteq G}
 
 into finite subgroups naturally gives rise to a filtration of the <a href="/facts/Orbit_equivalence_relation/Vh9VtUUw">orbit equivalence relation</a> of the action of G on X into finite Borel equivalence relations, thereby proving its hyperfiniteness.</li>
<li>If E is a countable equivalence relation and 
 
 
 
 
 E
 ′
 
 ⊂
 E
 
 
 {\displaystyle E'\subset E}
 
 is hyperfinite and of finite index (meaning that every E-class contains finitely many E'-classes), then E is hyperfinite.</li>
<li>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.</li>
<li>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 <a href="/facts/Group_action/Vh9VtUUw">action</a> 
 
 
 
 a
 :
 G
 ×
 X
 →
 X
 
 
 {\displaystyle 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,<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> making this an equivalent definition to hyperfiniteness that is often more accessible.</li>
<li>More generally, any Borel action of a countable <a href="/facts/Abelian_group/FfWwmx4R">abelian group</a> on a standard Borel space induces a hyperfinite orbit equivalence relation.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li>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
 →
 Y
 
 
 {\displaystyle f:X\rightarrow Y}
 
 is a Borel reduction of F to E, then F is hyperfinite (recall that 
 
 
 
 f
 
 
 {\displaystyle f}
 
 as above is a Borel reduction whenever it satisfies 
 
 
 
 ∀
 x
 ,
 y
 ∈
 X
 ,
 f
 (
 x
 )
 E
 f
 (
 y
 )
 
 ⟺
 
 x
 E
 y
 
 
 {\displaystyle \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.</li>
<li>Any Borel action of a <a href="/facts/Finitely-generated_group/fVsFHrmb">finitely-generated group</a> with <a href="/facts/Growth_rate_(group_theory)/IlKFW6Fj">polynomial growth</a> on a standard Borel space induces a hyperfinite orbit equivalence relation.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li>The action of a finitely-generated hyperbolic group on its Gromov boundary is hyperfinite.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>Any countable Borel equivalence relation can be restricted to a <a href="/facts/Meagre_set/AxTk8frw">comeagre set</a> on which it is hyperfinite.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 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.</li>
<li>Any group which is not <a href="/facts/Amenable_group/08XrAwvx">amenable</a> admits a Borel action on a standard Borel space which induces an equivalence relation that is not hyperfinite.</li>
<li>The action of the free group 
 
 
 
 
 F
 
 2
 
 
 
 
 {\displaystyle F_{2}}
 
 on two generators on the space 
 
 
 
 
 2
 
 
 F
 
 2
 
 
 
 
 
 
 {\displaystyle 2^{F_{2}}}
 
 by the shift maps is not hyperfinite. This fact is often considered to be a combinatorial variant of the <a href="/facts/Banach%25E2%2580%2593Tarski_paradox/MBfD5eyM">Banach–Tarski paradox</a>.</li></ul>
<h2 id="open-problems">Open problems</h2>
<h3>Weiss's conjecture</h3>
The above examples seem to indicate that Borel actions of "tame" countable <a href="/facts/Group_(mathematics)/IQTYqINt">groups</a> induce hyperfinite equivalence relations. <a href="/facts/Benjamin_Weiss/e8BSxcQV">Weiss</a> conjectured that any Borel action of a countable <a href="/facts/Amenable_group/08XrAwvx">amenable group</a> on a standard Borel space induces a hyperfinite orbit equivalence relation. While this is still an open problem, some partial results are known.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h3>The union problem</h3>
Another open problem in the area is whether a countable increasing union of hyperfinite equivalence relations is hyperfinite.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> 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
 :
 
 N
 
 →
 
 N
 
 
 
 {\displaystyle 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="measure-theoretic-results">Measure-theoretic results</h2>
Under the assumption that the underlying space X is equipped with a Borel <a href="/facts/Probability_measure/8BjhgoPR">probability measure</a> μ and that one is willing to remove sets of <a href="/facts/Null_set/kMudL8Mn">measure zero</a>, 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<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> (it is worthwhile to note that the action need not be <a href="/facts/Measure-preserving_dynamical_system/acIdlpqt">measure-preserving</a>, or even <a href="/facts/Quasi-invariant_measure/tr4xwRqx">quasi-measure preserving</a>). Since every countable Borel equivalence relation E on a standard non-atomic Borel probability space (X,
 
 
 
 μ
 
 
 {\displaystyle \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 
 
 
 
 σ
 
 
 {\displaystyle \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.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Hyperfinite_type_II_factor/TAs9Q0sq">Hyperfinite type II factor</a></li>
<li><a href="/facts/Borel_equivalence_relation/LSy25sXx">Borel equivalence relation</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Conley, Clinton; Jackson, Steve; Marks, Andrew; Seward, Brandon; Tucker-Drob, Robin (2020), Borel asymptotic dimension and hyperfinite equivalence relations, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/2009.06721">2009.06721</a></li>
<li>Connes, Alain; Feldman, Joel; Weiss, Benjamin (1995), "An amenable equivalence relation is generated by a single transformation", Ergodic Theory and Dynamical Systems, 1 (4): 431–450, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1017%2FS014338570000136X">10.1017/S014338570000136X</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:119385336">119385336</a></li>
<li>Coskey, Samuel; Schneider, Scott (2017), <a href="https://scholarworks.boisestate.edu/cgi/viewcontent.cgi?article=1200&context=math_facpubs">"Cardinal characteristics and countable Borel equivalence relations"</a>, Mathematical Logic Quarterly, 63 (3–4): 211–227, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1103.2312">1103.2312</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1002%2Fmalq.201400111">10.1002/malq.201400111</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:41429052">41429052</a></li>
<li>Dougherty, Randall; Jackson, Steve; Kechris, Alexander S. (1994), "The structure of hyperfinite Borel equivalence relations", Transactions of the American Mathematical Society, 341: 193–225, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0002-9947-1994-1149121-0">10.1090/S0002-9947-1994-1149121-0</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:29620563">29620563</a></li>
<li>Gao, Su; Jackson, Steve (2007), "Countable abelian groups and hyperfinite equivalence relations", Inventiones Mathematicae, 201 (1), <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00222-015-0603-y">10.1007/s00222-015-0603-y</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:24460955">24460955</a></li>
<li>Jackson, Steve; Kechris, Alexander S.; Louveau, Alain (2002), "Countable Borel equivalence relations", Journal of Mathematical Logic, 2 (1): 1–144, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1142%2FS0219061302000138">10.1142/S0219061302000138</a></li>
<li>Kechris, Alexander S.; Miller, Benjamin D. (2004), Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fb99421">10.1007/b99421</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-22603-1</li>
<li>Marquis, Timothée; Sabok, Marcin (2020), "Hyperfiniteness of boundary actions of hyperbolic groups", Mathematische Annalen, 377 (4): 1129–1153, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1907.09928">1907.09928</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00208-020-02001-9">10.1007/s00208-020-02001-9</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:198179841">198179841</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Connes, Feldman & Weiss 1995 - Connes, Alain; Feldman, Joel; Weiss, Benjamin (1995), "An amenable equivalence relation is generated by a single transformation", Ergodic Theory and Dynamical Systems, 1 (4): 431–450, doi:10.1017/S014338570000136X, S2CID 119385336 <a href="https://doi.org/10.1017%2FS014338570000136X" target="_blank">https://doi.org/10.1017%2FS014338570000136X</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gao & Jackson 2007 - Gao, Su; Jackson, Steve (2007), "Countable abelian groups and hyperfinite equivalence relations", Inventiones Mathematicae, 201 (1), doi:10.1007/s00222-015-0603-y, S2CID 24460955 <a href="https://doi.org/10.1007%2Fs00222-015-0603-y" target="_blank">https://doi.org/10.1007%2Fs00222-015-0603-y</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Jackson, Kechris & Louveau 2002 - Jackson, Steve; Kechris, Alexander S.; Louveau, Alain (2002), "Countable Borel equivalence relations", Journal of Mathematical Logic, 2 (1): 1–144, doi:10.1142/S0219061302000138 <a href="https://doi.org/10.1142%2FS0219061302000138" target="_blank">https://doi.org/10.1142%2FS0219061302000138</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Marquis & Sabok 2020 - Marquis, Timothée; Sabok, Marcin (2020), "Hyperfiniteness of boundary actions of hyperbolic groups", Mathematische Annalen, 377 (4): 1129–1153, arXiv:1907.09928, doi:10.1007/s00208-020-02001-9, S2CID 198179841 <a href="https://arxiv.org/abs/1907.09928" target="_blank">https://arxiv.org/abs/1907.09928</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Kechris & Miller 2004 - Kechris, Alexander S.; Miller, Benjamin D. (2004), Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer, doi:10.1007/b99421, ISBN 978-3-540-22603-1 <a href="https://doi.org/10.1007%2Fb99421" target="_blank">https://doi.org/10.1007%2Fb99421</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Conley et al. 2020 - Conley, Clinton; Jackson, Steve; Marks, Andrew; Seward, Brandon; Tucker-Drob, Robin (2020), Borel asymptotic dimension and hyperfinite equivalence relations, arXiv:2009.06721 <a href="https://arxiv.org/abs/2009.06721" target="_blank">https://arxiv.org/abs/2009.06721</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Dougherty, Jackson & Kechris 1994 - Dougherty, Randall; Jackson, Steve; Kechris, Alexander S. (1994), "The structure of hyperfinite Borel equivalence relations", Transactions of the American Mathematical Society, 341: 193–225, doi:10.1090/S0002-9947-1994-1149121-0, S2CID 29620563 <a href="https://doi.org/10.1090%2FS0002-9947-1994-1149121-0" target="_blank">https://doi.org/10.1090%2FS0002-9947-1994-1149121-0</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Coskey & Schneider 2017 - Coskey, Samuel; Schneider, Scott (2017), "Cardinal characteristics and countable Borel equivalence relations", Mathematical Logic Quarterly, 63 (3–4): 211–227, arXiv:1103.2312, doi:10.1002/malq.201400111, S2CID 41429052 <a href="https://scholarworks.boisestate.edu/cgi/viewcontent.cgi?article=1200&context=math_facpubs" target="_blank">https://scholarworks.boisestate.edu/cgi/viewcontent.cgi?article=1200&context=math_facpubs</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Connes, Feldman & Weiss 1995 - Connes, Alain; Feldman, Joel; Weiss, Benjamin (1995), "An amenable equivalence relation is generated by a single transformation", Ergodic Theory and Dynamical Systems, 1 (4): 431–450, doi:10.1017/S014338570000136X, S2CID 119385336 <a href="https://doi.org/10.1017%2FS014338570000136X" target="_blank">https://doi.org/10.1017%2FS014338570000136X</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Hyperfinite equivalence relation open-in-new

Hyperfinite equivalence relation