The Union Problem for hyperfinite Borel equivalence relations

The Union Problem, posed by Dougherty, Jackson and Kechris in 1994 and restated as Problem 2.12 of Gao and Xiao's 2024 order analysis of hyperfinite Borel equivalence relations, asks whether every hyper-hyperfinite countable Borel equivalence relation is hyperfinite — that is, whether an increasing union of hyperfinite Borel equivalence relations must itself be hyperfinite, or equivalently whether every countable Borel equivalence relation Borel reducible to $E_0(E_0)$ is reducible to $E_0$. It is one of the deepest open problems of the theory of countable Borel equivalence relations and is generally considered harder than Weiss's 1984 question on hyperfiniteness of orbit equivalence relations of amenable group actions.

Background

Countable Borel equivalence relations are the central objects of the branch of descriptive set theory that studies classification problems via definable reductions. A standard Borel space is a set carrying the Borel σ-algebra of some complete separable metric topology; a Borel equivalence relation $E$ on such a space $X$ is an equivalence relation that is a Borel subset of $X \times X$, and it is countable (a CBER) if all of its classes are countable. By the theorem of Feldman and Moore, the CBERs are exactly the orbit equivalence relations $E_G^X = \{(x,y) : \exists g \in G,\ gx = y\}$ of Borel actions of countable groups $G$.

The simplest CBERs are the smooth ones, those admitting a Borel complete invariant, i.e. a Borel map that is constant exactly on equivalence classes. By the Glimm–Effros dichotomy of Harrington, Kechris and Louveau, every non-smooth Borel equivalence relation contains a copy of $E_0$, eventual equality of infinite binary sequences on $2^{\mathbb{N}}$ ($x E_0 y$ iff $x(n) = y(n)$ for all but finitely many $n$). A CBER $E$ is hyperfinite if it decomposes as an increasing union $E = \bigcup_n F_n$ of Borel equivalence relations each having finite classes; equivalently, it admits a Borel assignment of linear orderings, one on each class, each of order type embeddable in $\mathbb{Z}$. Dougherty, Jackson and Kechris proved that a Borel equivalence relation is hyperfinite exactly when it is Borel reducible to $E_0$, where a Borel map $f : X \to Y$ reduces $E$ to $F$ if $x E x' \iff f(x) F f(x')$ (written $E \leq_B F$). The hyperfinite relations are thus the base of the CBER hierarchy under Borel reducibility.

Two natural closure operations on this base class lead to the problems recorded in the 2024 order-theoretic study of Gao and Xiao. First, a CBER is hyper-hyperfinite if $E = \bigcup_n F_n$ for some increasing sequence $F_0 \subseteq F_1 \subseteq\cdots$ of hyperfinite Borel subrelations (the terminology is recent, due to Frisch, Shinko and Vidnyánszky); Gao and Xiao show that a CBER is hyper-hyperfinite if and only if it is reducible to $E_0(E_0)$, the relation of eventual agreement modulo $E_0$ on sequences of reals ($x E_0(E_0) y$ iff $x(n) E_0 y(n)$ for all sufficiently large $n$). Second, a CBER is hyperfinite-over-hyperfinite if it admits a Borel assignment of linear orderings, one on each class, each of order type embeddable in the lexicographic ordering of $\mathbb{Z}^2$; Gao and Xiao show this is equivalent to reducibility to $E_S(E_0)$, the shift analogue of $E_0(E_0)$ on bi-infinite sequences ($x, y \in (2^{\mathbb{N}})^{\mathbb{Z}}$ are $E_S(E_0)$-equivalent iff some integer shift $n$ has $x(n+k) E_0 y(k)$ for every $k \in\mathbb{Z}$). They prove that such a relation is hyperfinite provided the witnessing ordering is self-compatible, a compatibility condition between the two coordinate orderings. Both classes contain the hyperfinite relations, both are contained in the class of Fréchet-amenable CBERs — Kechris's pointwise Borel analogue of amenability for equivalence relations — and it is unknown whether the two classes coincide.

The Union Problem — whether the first operation already leaves the hyperfinite class unchanged — was posed by Dougherty, Jackson and Kechris in 1994 and is intertwined with Weiss's 1984 question of whether $E_G^X$ is hyperfinite for every Borel action of every countable amenable group, where amenability is the group-theoretic analogue of finite approximability. Ornstein and Weiss proved the measure-theoretic counterpart: for every such action and every Borel probability measure, the orbit relation is hyperfinite off a μ-null invariant set. In the Borel, pointwise setting Weiss's question remains open, with positive answers known for $\mathbb{Z}^d$ (unpublished work of Weiss), finitely generated groups of polynomial volume growth (Jackson–Kechris–Louveau), countable abelian groups (Gao–Jackson), locally nilpotent groups (Schneider–Seward), polycyclic groups (Conley–Jackson–Marks–Seward–Tucker-Drob, via their theory of Borel asymptotic dimension, a definable analogue of Gromov's asymptotic dimension for Borel graphs), groups locally of volume growth $\exp(O(r^{\gamma}))$ with $\gamma \approx 0.1523$ (Grebík–Marks–Rozhoň–Shinko), and treeable relations satisfying strong pointwise amenability conditions (Naryshkin–Vaccaro). The two problems are linked structurally: writing a countable group as an increasing union of finitely generated subgroups $G_n$ gives $E_G^X = \bigcup_n E_{G_n}^X$, so whenever the finitely generated levels act hyperfinitely, the whole orbit relation is presented as a hyper-hyperfinite tower, and recognizing it as hyperfinite is exactly an instance of the Union Problem; this is the difficulty Gao and Jackson had to overcome for infinitely generated abelian groups, and Conley–Jackson–Marks–Seward–Tucker-Drob explicitly call the Union Problem 'generally considered harder than Weiss's question'. The problem has genuine content, since non-hyperfinite CBERs do exist: Jackson–Kechris–Louveau showed that every countable non-amenable group admits a Borel action whose orbit equivalence relation is not hyperfinite. Finally, Frisch, Shinko and Vidnyánszky connect the Union Problem to definability: it is open whether the collection of hyperfinite CBERs (as a set of Borel codes) is $\Pi^1_1$, and they prove that the existence of a hyper-hyperfinite non-hyperfinite CBER would force this collection to be $\Sigma^1_2$-complete, that is, of maximal complexity among projectively definable sets.

Problem Statement

The Union Problem (Dougherty–Jackson–Kechris 1994; restated as Problem 2.12 of Gao–Xiao 2024): is every hyper-hyperfinite Borel equivalence relation hyperfinite? Explicitly, if $X$ is a standard Borel space and $F_0 \subseteq F_1 \subseteq F_2 \subseteq\cdots$ is an increasing sequence of hyperfinite Borel equivalence relations on $X$, must $E = \bigcup_{n<\omega} F_n$ be hyperfinite (the union $E$ is automatically Borel and has countable classes, since each $F_n$ does)? By the characterization results recalled above, this is equivalently the question of whether, for every countable Borel equivalence relation $E$, Borel reducibility $E \leq_B E_0(E_0)$ implies $E \leq_B E_0$; that is, whether the class of hyperfinite CBERs is closed under countable increasing unions. A resolving answer must settle this statement in full generality, with no auxiliary hypotheses — no growth, dimension, or asymptotic-dimension bound on the levels (as in the known special cases), no freeness or bounded-to-one condition on generators, and no self-compatibility condition on any ordering.

References

1. Su Gao and Ming Xiao, 'An order analysis of hyperfinite Borel equivalence relations', arXiv:2404.17516 (2024); journal version in the Journal of Symbolic Logic, DOI 10.1017/jsl.2024.82 (2025). https://arxiv.org/abs/2404.17516
2. R. Dougherty, S. Jackson and A. S. Kechris, 'The structure of hyperfinite Borel equivalence relations', Transactions of the American Mathematical Society 341 (1994), no. 1, 193–225, DOI 10.1090/s0002-9947-1994-1149121-0. https://doi.org/10.1090/s0002-9947-1994-1149121-0
3. S. Jackson, A. S. Kechris and A. Louveau, 'Countable Borel equivalence relations', Journal of Mathematical Logic 2 (2002), no. 1, 1–80, DOI 10.1142/s0219061302000138. https://doi.org/10.1142/s0219061302000138
4. Benjamin Weiss, 'Measurable dynamics', Contemporary Mathematics 26 (1984), 395–421, DOI 10.1090/conm/026/737417. https://doi.org/10.1090/conm/026/737417
5. Donald S. Ornstein and Benjamin Weiss, 'Ergodic theory of amenable group actions. I: The Rohlin lemma', Bulletin of the American Mathematical Society 2 (1980), 161–164, DOI 10.1090/s0273-0979-1980-14702-3. https://doi.org/10.1090/s0273-0979-1980-14702-3
6. Jacob Feldman and Calvin C. Moore, 'Ergodic equivalence relations, cohomology, and von Neumann algebras. I', Transactions of the American Mathematical Society 234 (1977), no. 2, 289–324, DOI 10.1090/s0002-9947-1977-0578656-4. https://doi.org/10.1090/s0002-9947-1977-0578656-4
7. L. A. Harrington, A. S. Kechris and A. Louveau, 'A Glimm-Effros dichotomy for Borel equivalence relations', Journal of the American Mathematical Society 3 (1990), no. 4, 903–928, DOI 10.1090/s0894-0347-1990-1057041-5. https://doi.org/10.1090/s0894-0347-1990-1057041-5
8. Alexander S. Kechris, 'Amenable equivalence relations and Turing degrees', Journal of Symbolic Logic 56 (1991), no. 1, 182–194, DOI 10.2307/2274913. https://doi.org/10.2307/2274913
9. Su Gao and Steve Jackson, 'Countable abelian group actions and hyperfinite equivalence relations', Inventiones mathematicae 201 (2015), no. 1, 309–383, DOI 10.1007/s00222-015-0603-y. https://doi.org/10.1007/s00222-015-0603-y
10. Clinton T. Conley, Steve C. Jackson, Andrew S. Marks, Brandon M. Seward and Robin D. Tucker-Drob, 'Borel asymptotic dimension and hyperfinite equivalence relations', Duke Mathematical Journal 172 (2023), no. 16, 3175–3226, DOI 10.1215/00127094-2022-0100; preprint arXiv:2009.06721. https://arxiv.org/abs/2009.06721
11. Scott Schneider and Brandon Seward, 'Locally nilpotent groups and hyperfinite equivalence relations', Mathematical Research Letters 31 (2024), no. 2, 511–578, DOI 10.4310/mrl.241024235042. https://doi.org/10.4310/mrl.241024235042
12. Joshua Frisch, Forte Shinko and Zoltán Vidnyánszky, 'Hyper-hyperfiniteness and complexity', arXiv:2409.16445 (2024). https://arxiv.org/abs/2409.16445
13. Alexander S. Kechris, 'The Theory of Countable Borel Equivalence Relations', Cambridge Tracts in Mathematics 234, Cambridge University Press, 2025, DOI 10.1017/9781009562256. https://doi.org/10.1017/9781009562256
14. Anton Bernshteyn and Jing Yu, 'Large-scale geometry of Borel graphs of polynomial growth', Advances in Mathematics 473 (2025), 110290, DOI 10.1016/j.aim.2025.110290. https://doi.org/10.1016/j.aim.2025.110290
15. Petr Naryshkin and Andrea Vaccaro, 'Hyper-u-amenablity and Hyperfiniteness of Treeable Equivalence Relations' (title as on arXiv), arXiv:2507.07891 (2025, revised 2 February 2026). https://arxiv.org/abs/2507.07891
16. Jan Grebík, Andrew S. Marks, Václav Rozhoň and Forte Shinko, 'Borel dimension growth and hyperfiniteness', arXiv:2608.22565 (submitted 23 August 2026). https://arxiv.org/abs/2608.22565
17. Forte Shinko, Felix Weilacher and Jing Yu, 'Hyperfiniteness of bounded-to-one actions of commutative monoids', arXiv:2608.18439 (submitted 19 August 2026, v2 23 August 2026). https://arxiv.org/abs/2608.18439
18. Ruijun Wang, 'Borel graphs generated by finitely many bounded-to-1 commuting Borel functions and hyperfinite equivalence relations', arXiv:2608.01231 (2026). https://arxiv.org/abs/2608.01231
19. Samuel Coskey and Scott Schneider, 'Cardinal characteristics and countable Borel equivalence relations', arXiv:1103.2312 (2011, revised 2016). https://arxiv.org/abs/1103.2312