The published memoir 'Realizations of Countable Borel Equivalence Relations' by Frisch, Kechris, Shinko, and Vidnyánszky proves that Turing equivalence ≡T\equiv_T on 2N2^{\mathbb{N}} is Borel isomorphic, via a Baire class 2 bijection, to the orbit equivalence relation of a continuous action of a countable group on the Baire space NN\mathbb{N}^{\mathbb{N}}, and leaves open the exact regularity frontier: (i) whether ≡T\equiv_T admits a compact action realization (Problem 4.46); (ii) whether the isomorphism can be lowered to Baire class 1 (Problem 4.55); and (iii) whether it can be arranged that Φ(x)≤Tx′\Phi(x) \leq_T x' on a cone (Problem 4.56), the natural barrier being that Φ(x)≤Tx\Phi(x) \leq_T x on a cone is impossible. The authors themselves still list all three questions as open in the published memoir.

Background

A countable Borel equivalence relation (CBER) is a Borel equivalence relation EE on a standard Borel space whose equivalence classes are countable; by a theorem of Feldman–Moore every CBER is the orbit equivalence relation of a Borel action of some countable group. A CBER is smooth if it admits a Borel map separating classes, hyperfinite if it is an increasing union of Borel equivalence relations with finite classes, and aperiodic if all of its classes are infinite. Realization theory asks which CBERs arise from actions with better regularity than mere Borelness — for example, continuous actions on Polish spaces. The source memoir studies when a CBER EE admits a compact action realization: a compatible compact Polish topology on the underlying space under which EE is induced by a continuous action of a countable group; equivalently, EE is Borel isomorphic to the orbit equivalence relation of such an action on some compact Polish space. (Whether the compact space can always be taken to be the Cantor space 2N2^{\mathbb{N}} is itself left open by the memoir, as its Problem 4.14.) Among the positive results: every aperiodic CBER has a continuous action realization on the Baire space NN\mathbb{N}^{\mathbb{N}} (Proposition 4.4); every non-smooth aperiodic hyperfinite CBER admits a minimal compact action realization on 2N2^{\mathbb{N}} (Theorem 4.9); and arithmetical equivalence ≡A\equiv_A (the relation of computing the same arithmetic sets), which is universal and compressible by work of Marks–Slaman–Steel, admits a compact action realization on 2N2^{\mathbb{N}} (Corollary 4.45). Turing equivalence ≡T\equiv_T relates x,y∈2Nx, y \in 2^{\mathbb{N}} when each is computable from the other; it has countable classes and is non-smooth, and it is known not to be hyperfinite (Slaman–Steel). The memoir proves (Theorem 4.47, improving an unpublished Baire class 3 argument of Andrew Marks) that there is a Baire class 2 bijection Φ:2N→NN\Phi: 2^{\mathbb{N}} \to \mathbb{N}^{\mathbb{N}} that is an isomorphism between ≡T\equiv_T and the orbit relation of a continuous action; for the specific Φ\Phi constructed in the proof one has Φ(x)≡Tx′′\Phi(x) \equiv_T x'', where x′′x'' is the double Turing jump (the relativized halting-problem oracle iterated twice; x′x', the single Turing jump of xx, is defined analogously). A Baire class 1 map is a pointwise limit of continuous maps (equivalently, preimages of open sets are Σ20\Sigma^0_2). A cone is the set of reals computing some fixed real, and 'on a cone' means for all reals in some cone; this quantifier is the standard one in Martin's conjecture, the conjectural classification of Turing-invariant functions (functions ff with x≡Ty  ⟹  f(x)≡Tf(y)x \equiv_T y \implies f(x) \equiv_T f(y)) under the cone ordering. The authors show a genuine obstruction (Proposition 4.57): no such Borel isomorphism can satisfy Φ(x)≤Tx\Phi(x) \leq_T x on a cone, using Martin's pointed perfect trees (perfect binary trees all of whose branches compute the tree). The first arXiv version of the memoir noted, in a discussion dropped from the published version, that if Martin's conjecture holds then any Φ\Phi as in Theorem 4.47 should satisfy Φ(x)≡T\Phi(x) \equiv_T one of x,x′,x′′x, x', x'' on a cone; xx is ruled out by Proposition 4.57, x′′x'' is achieved, and whether the single jump x′x' suffices is exactly the third question below. The authors state that a negative answer to the compactness question would give a new proof of the failure of hyperfiniteness for ≡T\equiv_T and — in their words, more importantly — a negative answer to the long-standing universality problem for ≡T\equiv_T of Dougherty–Kechris, since a positive answer would follow from hyperfiniteness of ≡T\equiv_T by Theorem 4.9.

Problem Statement

The coherent objective is to determine the minimal topological and effective regularity with which Turing equivalence ≡T\equiv_T on 2N2^{\mathbb{N}} can be realized as the orbit equivalence relation of a continuous action of a countable group, along the three axes the published memoir leaves open. Fix the conventions: x≤Tyx \leq_T y means xx is computable from yy; x′x' is the Turing jump of xx; a cone is the set of reals yy with z≤Tyz \leq_T y for some fixed real zz, and a property holds 'on a cone' if it holds on the cone of some such zz; an isomorphism between equivalence relations EE on XX and FF on YY is a bijection Φ:X→Y\Phi: X \to Y with x E y  ⟺  Φ(x) F Φ(y)x \, E \, y \iff \Phi(x) \, F \, \Phi(y); and in questions (2) and (3) below, 'an equivalence relation given by a continuous group action on NN\mathbb{N}^{\mathbb{N}}' means the orbit equivalence relation of a continuous action of a countable group on the Baire space NN\mathbb{N}^{\mathbb{N}} with its usual Polish topology. A compact action realization of a CBER EE means a compatible compact Polish topology on the underlying standard Borel space of EE under which EE is the orbit equivalence relation of a continuous action of a countable group; equivalently, EE is Borel isomorphic to the orbit equivalence relation of such an action on some compact Polish space. (The Cantor space 2N2^{\mathbb{N}} is the natural special case, but whether it can always be achieved is the memoir's separate open Problem 4.14, so for question (1) a construction on any compact Polish space answers the question.) The three published questions are:

(1) Problem 4.46: Does Turing equivalence ≡T\equiv_T on 2N2^{\mathbb{N}} admit a compact action realization?

(2) Problem 4.55: Is there a Baire class 1 bijection that is an isomorphism between ≡T\equiv_T and an equivalence relation given by a continuous group action on NN\mathbb{N}^{\mathbb{N}}?

(3) Problem 4.56: Is there a Borel bijection Φ:2N→NN\Phi: 2^{\mathbb{N}} \to \mathbb{N}^{\mathbb{N}} that is an isomorphism between ≡T\equiv_T and an equivalence relation given by a continuous group action on NN\mathbb{N}^{\mathbb{N}} such that Φ(x)≤Tx′\Phi(x) \leq_T x' on a cone?

Known boundary conditions: Theorem 4.47 gives such an isomorphism of Baire class 2 with Φ(x)≡Tx′′\Phi(x) \equiv_T x'' (for the constructed Φ\Phi), and Proposition 4.57 shows the bound cannot be improved to Φ(x)≤Tx\Phi(x) \leq_T x on a cone, so question (3) asks whether the single jump suffices. An answer to any of the three in the natural direction (positive construction or impossibility proof) constitutes an answer to that part; the three questions are jointly the regularity frontier for ≡T\equiv_T within the memoir's realization program.

References

  1. Joshua Frisch, Alexander S. Kechris, Forte Shinko, Zoltán Vidnyánszky, Realizations of Countable Borel Equivalence Relations, Memoirs of the American Mathematical Society 320 (1632), American Mathematical Society, 2026. DOI: 10.1090/memo/1632, https://doi.org/10.1090/memo/1632; preprint arXiv:2109.12486, https://arxiv.org/abs/2109.12486
  2. Andrew Marks, Theodore A. Slaman, John R. Steel, Martin's conjecture, arithmetic equivalence, and countable Borel equivalence relations, in Ordinal Definability and Recursion Theory: The Cabal Seminar, Volume III (Lecture Notes in Logic 43), Cambridge University Press, 2016. DOI: 10.1017/CBO9781139519694.017, https://doi.org/10.1017/CBO9781139519694.017; preprint arXiv:1109.1875, https://arxiv.org/abs/1109.1875
  3. Adam Day, Andrew Marks, On a question of Slaman and Steel, Transactions of the American Mathematical Society, Series B 13 (2026), 379–402. DOI: 10.1090/btran/253, https://doi.org/10.1090/btran/253; preprint arXiv:2004.00174, https://arxiv.org/abs/2004.00174
  4. Randall Dougherty, Alexander S. Kechris, How many Turing degrees are there?, in Computability Theory and Its Applications (Boulder, CO, 1999), Contemporary Mathematics 257, American Mathematical Society, 2000, 83–94. DOI: 10.1090/conm/257/04029, https://doi.org/10.1090/conm/257/04029; preprint arXiv:math/0001173, https://arxiv.org/abs/math/0001173
  5. Alexander S. Kechris, The Theory of Countable Borel Equivalence Relations, Cambridge University Press, 2024. DOI: 10.1017/9781009562256, https://doi.org/10.1017/9781009562256