For a countable structure one can study the degree spectrum with respect to an equivalence relation on structures: the set of Turing degrees of structures equivalent to it. Rossegger (J. Symbolic Logic, 2022) proved that elementary bi-embeddability on graphs is analytic (Σ11\boldsymbol{\Sigma}^1_1) complete, that graphs are complete for elementary bi-embeddability spectra via computable functors, and that for every automorphically non-trivial graph G there is a graph whose elementary bi-embeddability spectrum is the jump-preimage of the bi-embeddability spectrum of G. He then asked whether the classes of Turing degree spectra realized by bi-embeddability and by elementary bi-embeddability on graphs actually coincide, whether these spectra (and theory spectra of graphs) are closed under the Turing jump, and whether graphs are complete for bi-embeddability spectra. These four questions remain open.

Background

In computable structure theory one measures the algorithmic complexity of a countable structure, taken to have domain the natural numbers, by the Turing degree of its atomic diagram D(A)D(A), the characteristic function of the set of atomic formulas true in AA; two sets have the same Turing degree when they are Turing equivalent, meaning that each computes the other. The degree spectrum of a structure, introduced by Knight (1986), is DgSp(A)={deg⁡D(B):B≅A}\mathrm{DgSp}(A)=\{\deg D(B) : B \cong A\}, the set of Turing degrees of isomorphic copies of AA. This notion generalizes to arbitrary equivalence relations EE on structures: the EE-spectrum of AA is DgSpE(A)={X:∃B (B E A∧D(B)≡TX)}\mathrm{DgSp}_E(A)=\{X : \exists B\,(B\,E\,A \wedge D(B) \equiv_T X)\}, where ≡T\equiv_T denotes Turing equivalence. Variants of this definition were proposed independently by Montalbán (2015), by Semukhin, Turetsky, and Fokina (2019), and by Yu (2015), and the program of comparing equivalence relations by the degree spectra they realize was taken up by Andrews and Miller for elementary equivalence, by Andrews, Cai, Diamondstone, Lempp, and Miller for theories, by Fokina, Rossegger, and San Mauro for bi-embeddability, and by Rossegger for elementary bi-embeddability. Two equivalence relations are central here. A structure AA is embeddable in BB if there is an injection of the domain of AA into BB that preserves the interpretations of the relation symbols in both directions; AA and BB are bi-embeddable, written A≈BA \approx B, if each embeds in the other. An embedding is elementary if it preserves all first-order formulas, and AA and BB are elementary bi-embeddable if each elementarily embeds in the other. Elementary bi-embeddability is a strictly finer equivalence relation than bi-embeddability, which in turn is coarser than isomorphism. Separately, for a complete first-order theory TT, its theory spectrum is the set of Turing degrees of (diagrams of) models of TT, in the sense of Andrews, Cai, Diamondstone, Lempp, and Miller; the theory spectrum of a graph is the theory spectrum of its complete theory. In descriptive set theory, one compares equivalence relations on standard Borel spaces of structures by Borel reducibility: EE reduces to FF if a Borel function maps EE-equivalent pairs to FF-equivalent pairs and conversely. Louveau and Rosendal (2005) proved that bi-embeddability on graphs is a complete analytic equivalence relation, where analytic means belonging to the pointclass Σ11\boldsymbol{\Sigma}^1_1 (a continuous image of a Borel set) and complete means maximal among analytic equivalence relations under Borel reducibility. Rossegger (2022) proved the analogue for elementary bi-embeddability on graphs: it is Σ11\boldsymbol{\Sigma}^1_1 complete under Borel reducibility, and Σ11\Sigma^1_1 complete on the class of computable graphs under computable reducibility, the effective counterpart of Borel reducibility. He further studied the degree spectra realized by these relations. A key tool is reducibility by computable functors, following Harrison-Trainor, Melnikov, Miller, and Montalbán (2017): a pair of computable functors between categories of structures that are effectively isomorphic to identity functors in both directions. Rossegger showed that the class of graphs is complete for elementary embeddability under this notion (his Theorem 15), from which it follows that every elementary bi-embeddability spectrum of an arbitrary structure is realized by some graph (his Corollary 16). His main spectral result (Theorem 3) is that for every automorphically non-trivial graph GG (a structure AA is automorphically trivial if there is a finite set D⊆AD \subseteq A such that every permutation of AA that fixes DD pointwise is an automorphism, and non-trivial otherwise) there is a graph G^\hat{G} whose elementary bi-embeddability spectrum is {X:X′∈DgSp≈(G)}\{X : X' \in \mathrm{DgSp}_{\approx}(G)\}, where X′X' denotes the Turing jump of XX. Since spectra of automorphically non-trivial structures are upwards closed in the Turing degrees (Knight 1986), this embeds each bi-embeddability spectrum, up to one application of the jump, into the class of elementary bi-embeddability spectra. A jump of a structure is, by analogy with the isomorphism case, a uniform construction assigning to a structure AA a structure A∗A^* intended to satisfy DgSp(A∗)={x′:x∈DgSp(A)}\mathrm{DgSp}(A^*)=\{x' : x \in \mathrm{DgSp}(A)\}; no known such construction preserves elementary embeddability, or even elementary equivalence, which is the central obstruction behind Question 2 below. The paper closes with the questions below, motivated by the stated goal of the whole research line: while elementary equivalence and Σn\Sigma_n equivalence can be distinguished from each other and from isomorphism by their spectra, all attempts to separate isomorphism, bi-embeddability, and elementary bi-embeddability by their degree spectra have so far been unsuccessful.

Problem Statement

The common objective is to determine the relationship between the classes of Turing degree spectra realized on graphs by the bi-embeddability relation and by the elementary bi-embeddability relation, and, in the same setting, the behavior of theory spectra under the Turing jump. Rossegger (2022) poses the following four questions, reproduced faithfully. These four questions are posed independently; a definitive answer, in either direction, to any one of them settles that question. Question 1: Is every bi-embeddability spectrum of a graph the elementary bi-embeddability spectrum of a graph, and vice versa? (Equivalently: do the two classes of sets of Turing degrees realized by these two equivalence relations on graphs coincide?) Question 2: If XX is the elementary bi-embeddability spectrum of a graph, is the pointwise jump X′={x′:x∈X}X' = \{x' : x \in X\} also the elementary bi-embeddability spectrum of a graph? (The paper notes this is one route to a positive answer to Question 1, but that all known definitions of the jump of a structure fail to preserve elementary embeddability, and not even elementary equivalence.) Question 3: If XX is the theory spectrum of a graph (the set of Turing degrees of models of its complete theory), is X′X' again the theory spectrum of a graph? Question 4: Is every bi-embeddability spectrum of a countable structure realized as the bi-embeddability spectrum of a graph? (The analogue is known for elementary bi-embeddability spectra, by computable-functor completeness of graphs for elementary embeddability.) In all four questions the spectra are taken over arbitrary countable graphs and structures, not restricted to computable ones, and any answer must be established at this full generality.

References

  1. Dino Rossegger, "Degree spectra of analytic complete equivalence relations", Journal of Symbolic Logic 87(4):1663-1676, 2022. DOI: 10.1017/jsl.2021.82; arXiv:2010.00755. https://doi.org/10.1017/jsl.2021.82
  2. Dino Rossegger, "Elementary Bi-embeddability Spectra of Structures", in: Sailing Routes in the World of Computation (CiE 2018), Lecture Notes in Computer Science 10936, Springer, 2018, pp. 349-358. DOI: 10.1007/978-3-319-94418-0_35. https://doi.org/10.1007/978-3-319-94418-0_35
  3. Ekaterina Fokina, Dino Rossegger, Luca San Mauro, "Bi-embeddability spectra and bases of spectra", Mathematical Logic Quarterly 65(2):228-236, 2019. DOI: 10.1002/malq.201800056; arXiv:1808.05451. https://doi.org/10.1002/malq.201800056
  4. Pavel Semukhin, Daniel Turetsky, Ekaterina Fokina, "Degree Spectra of Structures Relative to Equivalences", Algebra and Logic 58(2):158-172, 2019. DOI: 10.1007/s10469-019-09534-2. https://doi.org/10.1007/s10469-019-09534-2
  5. Uri Andrews, Mingzhong Cai, David Diamondstone, Steffen Lempp, Joseph Miller, "Theory spectra and classes of theories", Transactions of the American Mathematical Society 369(9):6493-6510, 2017. DOI: 10.1090/tran/6917. https://doi.org/10.1090/tran/6917
  6. Uri Andrews, Joseph S. Miller, "Spectra of theories and structures", Proceedings of the American Mathematical Society 143(3):1283-1298, 2015. DOI: 10.1090/S0002-9939-2014-12283-0. https://doi.org/10.1090/S0002-9939-2014-12283-0
  7. Antonio Montalbán, "Analytic equivalence relations satisfying hyperarithmetic-is-recursive", Forum of Mathematics, Sigma 3, 2015. DOI: 10.1017/fms.2015.5. https://doi.org/10.1017/fms.2015.5
  8. Liang Yu, "Degree Spectra of Equivalence Relations", in: Proceedings of the 13th Asian Logic Conference, World Scientific, 2015, pp. 237-242. DOI: 10.1142/9789814678001_0013. https://doi.org/10.1142/9789814678001_0013
  9. Alain Louveau, Christian Rosendal, "Complete analytic equivalence relations", Transactions of the American Mathematical Society 357(12):4839-4866, 2005. DOI: 10.1090/S0002-9947-05-04005-5. https://doi.org/10.1090/S0002-9947-05-04005-5
  10. Julia F. Knight, "Degrees coded in jumps of orderings", Journal of Symbolic Logic 51(4):1034-1042, 1986. DOI: 10.2307/2273915. https://doi.org/10.2307/2273915
  11. Matthew Harrison-Trainor, Alexander Melnikov, Russell Miller, Antonio Montalbán, "Computable functors and effective interpretability", Journal of Symbolic Logic 82(1):77-97, 2017. DOI: 10.1017/jsl.2016.12. https://doi.org/10.1017/jsl.2016.12
  12. Uri Andrews, David Gonzalez, Steffen Lempp, Dino Rossegger, Hongyu Zhu, "The Borel complexity of the class of models of first-order theories", Proceedings of the American Mathematical Society, 2025. DOI: 10.1090/proc/17308; arXiv:2402.10029. https://doi.org/10.1090/proc/17308
  13. Vittorio Cipriani, Ekaterina Fokina, Matthew Harrison-Trainor, Liling Ko, Dino Rossegger, "Dichotomy results for classes of countable graphs", arXiv:2512.09832, 2025. https://arxiv.org/abs/2512.09832
  14. Gianluca Paolini, Saharon Shelah, "Torsion-free abelian groups are faithfully Borel complete and pure embeddability is a complete analytic quasi-order", Science China Mathematics 68:2809-2814, 2025. DOI: 10.1007/s11425-024-2401-0. https://doi.org/10.1007/s11425-024-2401-0