Bi-embeddability spectra versus isomorphism spectra: separation and realizable bases

For a countable structure $\mathcal{A}$, the bi-embeddability spectrum $DgSp_{\approx}(\mathcal{A})$ is the family of Turing degrees of structures bi-embeddable with $\mathcal{A}$, while the classical degree spectrum $DgSp_{\cong}(\mathcal{A})$ uses isomorphic copies. Fokina, Rossegger, and San Mauro, who initiated this study in 2019, proved that every cone, the noncomputable degrees, and the hyperimmune degrees are bi-embeddability spectra — each via a structure whose bi-embeddability and isomorphism types coincide — and that linear orderings and open-ended strongly locally finite graphs have singleton bi-embeddability bases. This problem is that paper's closing list of four open questions: (1) whether some bi-embeddability spectrum is not an isomorphism spectrum, and conversely whether some isomorphism spectrum is not a bi-embeddability spectrum; (2) whether some structure has a finite bi-embeddability basis of size greater than one; (3) whether some structure has a countably infinite bi-embeddability basis; and (4) whether some structure's bi-embeddability spectrum is exactly the union of two cones above incomparable Turing degrees. The principal follow-up (Rossegger, Journal of Symbolic Logic, 2022; arXiv version 2, October 2023) establishes a jump-level relation between bi-embeddability and elementary bi-embeddability spectra of graphs but records explicitly that every attempt to separate the notions of isomorphism, bi-embeddability, and elementary bi-embeddability has so far failed. No resolution of any of the four questions is known.

Background

Computable structure theory studies the algorithmic content of countable mathematical structures. A countable structure in a countable language is coded by a set of natural numbers (its atomic diagram, the set of true and negated atomic formulas), and one asks which Turing degrees — equivalence classes of sets of natural numbers under mutual computability — compute some copy of it. The degree spectrum of a structure, studied since Richter and Knight, is $DgSp_{\cong}(\mathcal{A})=\{\mathrm{deg}(\mathcal{B}) : \mathcal{B}\cong\mathcal{A}\}$, the family of degrees of its isomorphic copies. Knight proved that this family is a singleton exactly for automorphically trivial structures (a finite subset of the domain such that every permutation fixing it pointwise is an automorphism), and is otherwise upward closed under Turing reducibility. A long-standing program asks which upward-closed families of degrees arise as spectra; a landmark is the independent construction by Slaman and by Wehner of a structure whose spectrum is exactly the noncomputable degrees.

Bi-embeddability is a much coarser equivalence than isomorphism: $\mathcal{A}\approx\mathcal{B}$ if each of the two structures embeds into the other, where an embedding is an isomorphism of one structure onto a substructure of the other. On the descriptive-set-theoretic side the two relations are cleanly separated: Louveau and Rosendal proved that bi-embeddability on countable graphs is complete among analytic equivalence relations under Borel reducibility (the standard complexity measure for classification problems on the space of countable structures), while graph isomorphism is far from complete. On the computability-theoretic side, Fokina, Semukhin, and Turetsky introduced degree spectra relative to an equivalence relation $\sim$ on structures, $DgSp_{\sim}(\mathcal{A})=\{\mathrm{deg}(\mathcal{B}) : \mathcal{B}\sim\mathcal{A}\}$, generalizing the classical spectrum ($\sim$ = isomorphism) and spectra under $\Sigma_n$-equivalence (two structures satisfying the same $\Sigma_n$ first-order sentences); Rossegger studied the intermediate relation of elementary bi-embeddability, where either structure admits an elementary embedding (an embedding preserving all first-order formulas) into the other. For $\sim=\approx$ one obtains the bi-embeddability spectrum, the object of this problem. Since isomorphic structures are bi-embeddable, $DgSp_{\cong}(\mathcal{A})\subseteq DgSp_{\approx}(\mathcal{A})$, and Knight's dichotomy carries over: the bi-embeddability spectrum of an automorphically trivial structure is a singleton, and all others are upward closed.

Fokina, Rossegger, and San Mauro began the systematic study of $DgSp_{\approx}$. Their central model-theoretic notion is b.e. triviality: $\mathcal{A}$ is b.e. trivial if every structure bi-embeddable with $\mathcal{A}$ is isomorphic to $\mathcal{A}$, in which case the two spectra of $\mathcal{A}$ coincide. All classical realizations they transfer — every cone $\{\mathbf{d} : \mathbf{d}\geq\mathbf{a}\}$, the noncomputable degrees, and the hyperimmune degrees (those containing a function not dominated by any computable function) — are realized by b.e. trivial structures, so each of these families is simultaneously an isomorphism spectrum. To decompose a bi-embeddability spectrum into isomorphism spectra they use Muchnik reducibility: $\mathcal{A}\leq_w\mathcal{B}$ if every copy of $\mathcal{B}$ computes a copy of $\mathcal{A}$, equivalently $DgSp_{\cong}(\mathcal{B})\subseteq DgSp_{\cong}(\mathcal{A})$. A family $\mathcal{B}$ of structures is a bi-embeddability basis of $\mathcal{A}$ if every member is bi-embeddable with $\mathcal{A}$, distinct members are pairwise Muchnik-incomparable, and $DgSp_{\approx}(\mathcal{A})=\bigcup_{\mathcal{B}\in\mathcal{B}}DgSp_{\cong}(\mathcal{B})$; a basis is thus a minimal generating set of isomorphism types for the whole spectrum, in the sense of the bases of topology or linear algebra. Every structure analyzed in that paper has a singleton basis: b.e. trivial structures; every linear ordering (relativizing Montalbán's theorem that every hyperarithmetic linear ordering is bi-embeddable with a computable one, they show the bi-embeddability spectrum of a linear ordering equals the isomorphism spectrum of a well-ordering of its Hausdorff rank, an ordinal measuring the iterated nesting of finite condensation classes, defined for scattered orderings, i.e., those containing no copy of the ordering $\eta$ of the rationals); and open-ended strongly locally finite graphs (graphs that are disjoint unions of finite components, each component embedding into ever larger components), whose skeleton — the disjoint union of one representative of every finite graph embeddable into the graph — is a basis. Nevertheless, the same authors construct bi-embeddability spectra without a least degree, for example spectra equal to that of the well-ordering of type $\omega_1^{CK}$ (the first noncomputable ordinal), so having a singleton basis does not force the spectrum to have a minimum.

For neighboring equivalence relations the analogous questions have positive answers. Andrews and Miller constructed a complete first-order theory whose family of degrees of models is the union of two cones above incomparable Turing degrees, and Fokina, Semukhin, and Turetsky proved the same for $\Sigma_n$-equivalence with $n>2$; in the basis language, elementary equivalence and $\Sigma_n$-equivalence admit bases of size two. The model-theoretic analogue of the basis-size questions is Thomassé's conjecture that a countable relational structure has either $1$, $\aleph_0$, or $2^{\aleph_0}$ isomorphism types within its bi-embeddability type, studied through the counting of bi-embeddable copies ('siblings') by Laflamme, Pouzet, Sauer, and Woodrow. For bi-embeddability itself, no example is known that separates its spectra from isomorphism spectra in either direction, no basis other than a singleton is known, and each family realized so far — cones, the noncomputable and hyperimmune degrees, the jump spectra $\{\mathbf{d}:\mathbf{d}^{(\alpha)}\geq\mathbf{0}^{(\beta)}\}$ for computable successor ordinals, and the spectra of linear orderings, equal to isomorphism spectra of well-orderings — is simultaneously an isomorphism spectrum; making these gaps precise is the content of the problem.

Problem Statement

Settle the four questions posed by Fokina, Rossegger, and San Mauro at the close of 'Bi-embeddability spectra and bases of spectra' (Section 5), which together ask how the class of bi-embeddability spectra compares with the class of isomorphism spectra and which sizes of bi-embeddability bases are realizable. Each question requires either an explicit countable structure (or family of structures) together with a proof of the required degree-theoretic properties, or a proof that no such structure exists. Recall that a bi-embeddability basis of a structure $\mathcal{A}$ is a minimal family of pairwise Muchnik-incomparable structures, each bi-embeddable with $\mathcal{A}$, whose classical degree spectra union to $DgSp_{\approx}(\mathcal{A})$; questions (Q2) and (Q3) ask which cardinalities other than one such a basis can have. The questions are posed for structures in arbitrary countable languages, with no restriction on the class of structures:

(Q1) Is there a bi-embeddability spectrum $DgSp_{\approx}(\mathcal{A})$ that is not an isomorphism spectrum, i.e., not equal to $DgSp_{\cong}(\mathcal{B})$ for any structure $\mathcal{B}$; and, conversely, is there an isomorphism spectrum $DgSp_{\cong}(\mathcal{B})$ that is not equal to $DgSp_{\approx}(\mathcal{A})$ for any structure $\mathcal{A}$?

(Q2) Is there a structure having a bi-embeddability basis that is finite of size greater than one?

(Q3) Is there a structure having a countably infinite bi-embeddability basis?

(Q4) Is there a structure $\mathcal{A}$ and Turing degrees $\mathbf{a},\mathbf{b}$, incomparable under Turing reducibility, such that $DgSp_{\approx}(\mathcal{A})=\{\mathbf{d} : \mathbf{d}\geq\mathbf{a}\}\cup\{\mathbf{d} : \mathbf{d}\geq\mathbf{b}\}$?

The four parts are linked: a positive answer to (Q4) would entail a positive answer to (Q2) — as it is for elementary equivalence and $\Sigma_n$-equivalence — provided the two cone pieces are the isomorphism spectra of two structures bi-embeddable with $\mathcal{A}$ and Muchnik-incomparable with each other; and (Q2) together with (Q3) are the computability-theoretic analogues of Thomassé's sibling-count conjecture. The problem is complete when each of (Q1)-(Q4) is answered, in the affirmative by construction or in the negative by proof.

References

1. 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://arxiv.org/abs/1808.05451
2. Dino Rossegger, 'Degree spectra of analytic complete equivalence relations', The Journal of Symbolic Logic 87(4):1663-1676, 2022. DOI: 10.1017/jsl.2021.82; arXiv:2010.00755. https://arxiv.org/abs/2010.00755
3. Pavel M. Semukhin, Daniel Turetsky, Ekaterina B. 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
4. 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
5. Antonio Montalbán, 'Up to equimorphism, hyperarithmetic is recursive', The Journal of Symbolic Logic 70(2):360-378, 2005. DOI: 10.2178/jsl/1120224717. https://doi.org/10.2178/jsl/1120224717
6. Linda Jean Richter, 'Degrees of structures', The Journal of Symbolic Logic 46(4):723-731, 1981. DOI: 10.2307/2273222. https://doi.org/10.2307/2273222
7. Julia F. Knight, 'Degrees coded in jumps of orderings', The Journal of Symbolic Logic 51(4):1034-1042, 1986. DOI: 10.2307/2273915. https://doi.org/10.2307/2273915
8. Theodore Slaman, 'Relative to any nonrecursive set', Proceedings of the American Mathematical Society 126(7):2117-2122, 1998. DOI: 10.1090/s0002-9939-98-04307-x. https://doi.org/10.1090/s0002-9939-98-04307-x
9. Stephan Wehner, 'Enumerations, countable structures and Turing degrees', Proceedings of the American Mathematical Society 126(7):2131-2139, 1998. DOI: 10.1090/s0002-9939-98-04314-7. https://doi.org/10.1090/s0002-9939-98-04314-7
10. Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger, Luca San Mauro, 'Computable bi-embeddable categoricity', Algebra and Logic 57(5):392-396, 2018. DOI: 10.1007/s10469-018-9511-8. https://doi.org/10.1007/s10469-018-9511-8
11. Nikolay Bazhenov, Dino Rossegger, Maxim Zubkov, 'On bi-embeddable categoricity of algebraic structures', Annals of Pure and Applied Logic 173(3):103060, 2022. DOI: 10.1016/j.apal.2021.103060; arXiv:2005.07829. https://arxiv.org/abs/2005.07829
12. Matthew Harrison-Trainor, 'Relative to any non-arithmetic set', arXiv:2505.23613, 2025. https://arxiv.org/abs/2505.23613
13. Dino Rossegger, 'Elementary bi-embeddability spectra of structures', in: Sailing Routes in the World of Computation (CiE 2018), Lecture Notes in Computer Science, Springer, pp. 349-358, 2018. DOI: 10.1007/978-3-319-94418-0_35. https://doi.org/10.1007/978-3-319-94418-0_35
14. Claude Laflamme, Maurice Pouzet, Norbert Sauer, Robert Woodrow, 'Siblings of an $\aleph_0$-categorical relational structure', arXiv:1811.04185, 2018. https://arxiv.org/abs/1811.04185
15. 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
16. Ivan N. Soskov, 'A note on ω-jump inversion of degree spectra of structures', in: The Nature of Computation. Logic, Algorithms, Applications (CiE 2013), Lecture Notes in Computer Science, Springer, pp. 365-370, 2013. DOI: 10.1007/978-3-642-39053-1_43. https://doi.org/10.1007/978-3-642-39053-1_43
17. Marat Faizrahmanov, Asher Kach, Iskander Kalimullin, Antonio Montalbán, Vadim Puzarenko, 'Jump inversions of algebraic structures and Σ-definability', Mathematical Logic Quarterly 65(1):37-45, 2019. DOI: 10.1002/malq.201800015. https://doi.org/10.1002/malq.201800015