Is every degree spectrum of a countable structure the degree spectrum of a tree?

Harrison-Trainor and Montalbán ('The tree of tuples of a structure', J. Symb. Log. 87 (2022)) ask whether every degree spectrum of a countable structure — the set of Turing degrees computing an isomorphic copy of it — is also the degree spectrum of a (labeled) tree, and conjecture a negative answer. The natural candidate map, sending a structure $\mathcal{A}$ to its tree of tuples $\mathcal{T}(\mathcal{A})$, provably fails to preserve spectra: the paper's main theorem produces structures with no computable copy whose tree of tuples nevertheless has a computable copy. Graphs, fields, and partial orders are already known to realize every degree spectrum; trees are the prominent open case, sitting between these universal classes and linear orderings, for which uniform codings are known to fail. The question is open.

Background

Computable structure theory measures the information content of countable structures. A copy (or presentation) of a countable structure $\mathcal{A}$ is an isomorphic structure with domain the natural numbers; it is $X$-computable, for a set $X\subseteq\omega$, if its atomic diagram — the complete set of atomic facts about tuples, i.e. the relations and function values holding on them — is computable relative to $X$. The degree spectrum $\mathrm{DgSp}(\mathcal{A})$ is the set of Turing degrees of copies of $\mathcal{A}$; it records how much and what kind of information is intrinsically required to present $\mathcal{A}$. For automorphically non-trivial structures, degree spectra are upward closed under Turing reducibility.

A long-standing program asks which classes $\mathcal{K}$ of structures are universal for degree spectra, i.e., realize every degree spectrum within the class. Graphs are: every countable structure in a computable relational language is effectively bi-interpretable with a graph — a copy of each is uniformly recoverable from a copy of the other by computable procedures — so graphs realize every degree spectrum. Fields are universal too, via the computable functor from graphs to fields of Miller, Poonen, Schoutens, and Shlapentokh, and every degree spectrum of an automorphically non-trivial structure is realized by a partial order (Hirschfeldt, Khoussainov, Shore, and Slinko). Linear orderings behave differently: Knight, Soskova, and Vatev, and independently Harrison-Trainor and Montalbán, proved that graphs cannot be embedded into linear orderings by any uniform interpretation through $L_{\omega_1\omega}$-formulas (the infinitary logic allowing countably infinite conjunctions and disjunctions), ruling out the standard coding route there. Trees — the most basic relational data structure — sit between these extremes and are the natural next test case.

Here 'tree' means labeled tree: a tree equipped with a parent function and a labeling of its nodes by natural numbers. The labeled reading is the substantive one. Richter proved that trees viewed as plain partial orderings have the computable embeddability condition — every D-type realized in the structure is computable, where the D-type of a tuple is the set of indices of finite structures extending the tuple's pattern that can be realized inside the structure — and this condition forces severe restrictions on degree spectra: by her theorem, such a structure has no Turing degree and no enumeration degree unless it has a computable copy. Labels restore coding power: a labeled tree can code an arbitrary set of natural numbers. Friedman and Stanley's classical embedding already shows labeled trees are 'on top' for Turing-computable embeddings (uniform computable operators between classes that preserve isomorphism types): given a structure $\mathcal{A}$, one effectively builds its tree of tuples $\mathcal{T}(\mathcal{A})$ — nodes are the tuples from $\mathcal{A}$ ordered by extension, each node labeled by a code of the atomic diagram of the tuple, with each branch replicated infinitely often — and $\mathcal{A}\cong\mathcal{B}$ if and only if $\mathcal{T}(\mathcal{A})\cong\mathcal{T}(\mathcal{B})$.

Being on top for isomorphism types is much weaker than preserving degree spectra. The embedding produces $\mathcal{T}(\mathcal{A})$ uniformly from $\mathcal{A}$, but there is no general way back: Harrison-Trainor and Montalbán characterized exactly what is functorially recoverable — the families functorially c.e.-coded in $\mathcal{A}$ coincide with the families effectively interpreted in $\mathcal{A}$ — and their main theorem exhibits a structure $\mathcal{A}$ with no computable copy whose tree of tuples nevertheless has a computable copy; by $\alpha$-jump inversion, for each computable successor ordinal $\alpha$ there is such a structure with no $\Delta^0_\alpha$-computable copy. Thus $\mathrm{DgSp}(\mathcal{A})\neq\mathrm{DgSp}(\mathcal{T}(\mathcal{A}))$ in general, the direct strategy for realizing spectra by trees fails, and the paper shows moreover that $(\mathbb{Z};<)$ is not effectively bi-interpretable with any labeled tree. The paper therefore asks — its Question 1.12 — whether tree spectra are nevertheless universal by some other route, and conjectures they are not: there should exist a degree spectrum not realized by any tree. Determining which intrinsic computability-theoretic properties can be realized within the class of trees, despite being realizable by arbitrary structures, is the broader motivating program.

Problem Statement

Decide, in full generality, whether every degree spectrum of a countable structure — the set of Turing degrees computing an isomorphic copy (presentation) of that structure — is the degree spectrum of a labeled tree (a tree with a parent function and labels from $\omega$):

(1) Positive: prove that for every countable structure $\mathcal{A}$ there exists a labeled tree $T$ with $\mathrm{DgSp}(T)=\mathrm{DgSp}(\mathcal{A})$ — equivalently, every set of Turing degrees realized as the degree spectrum of some countable structure is realized by some labeled tree. The construction need not be uniform or functorial, but it must control both inclusions of the spectra across all presentations.

(2) Negative (the direction conjectured by Harrison-Trainor and Montalbán): exhibit a countable structure $\mathcal{A}$, or a degree spectrum $S=\mathrm{DgSp}(\mathcal{A})$, and prove that no labeled tree $T$ satisfies $\mathrm{DgSp}(T)=S$.

This is the source paper's Question 1.12. Partial variants — universality restricted to special shapes of spectra, to special subclasses of trees, to a cone of degrees, or to structures up to effective bi-interpretability — do not by themselves resolve the question as stated.

References

1. Matthew Harrison-Trainor and Antonio Montalbán, 'The tree of tuples of a structure', Journal of Symbolic Logic 87(1), 21–46 (published online 2020, print 2022). DOI: 10.1017/jsl.2019.92. https://doi.org/10.1017/jsl.2019.92
2. J. Knight, A. Soskova, and S. Vatev, 'Coding in graphs and linear orderings', Journal of Symbolic Logic 85, 673–690 (2020). DOI: 10.1017/jsl.2019.91. https://doi.org/10.1017/jsl.2019.91 (preprint at https://arxiv.org/abs/1903.06948)
3. David Gonzalez and Dino Rossegger, 'Scott sentence complexities of linear orderings', Journal of Symbolic Logic 90, 1563–1592 (2025). DOI: 10.1017/jsl.2024.59. https://doi.org/10.1017/jsl.2024.59 (preprint at https://arxiv.org/abs/2305.07126)
4. David Gonzalez and Julia Knight, 'Computable Scott Sentences and the Friedman-Stanley embedding', preprint (2026), arXiv:2605.04404. https://arxiv.org/abs/2605.04404
5. J. F. Knight, 'Classes of Algebraic Structures', Journal of Mathematical Sciences 275(1), 16–24 (2023). DOI: 10.1007/s10958-023-06656-y. https://doi.org/10.1007/s10958-023-06656-y
6. D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A. M. Slinko, 'Degree spectra and computable dimensions in algebraic structures', Annals of Pure and Applied Logic 115, 71–113 (2002). DOI: 10.1016/S0168-0072(01)00087-2. https://doi.org/10.1016/S0168-0072(01)00087-2
7. R. Miller, B. Poonen, H. Schoutens, and A. Shlapentokh, 'A computable functor from graphs to fields', Journal of Symbolic Logic 83, 326–348 (2018). DOI: 10.1017/jsl.2017.50. https://doi.org/10.1017/jsl.2017.50
8. Harvey Friedman and Lee Stanley, 'A Borel reductibility theory for classes of countable structures' [title as published; 'reductibility' is the original publication's spelling], Journal of Symbolic Logic 54(3), 894–914 (1989). DOI: 10.2307/2274750. https://doi.org/10.2307/2274750
9. Linda Jean Richter, 'Degrees of structures', Journal of Symbolic Logic 46(4), 723–731 (1981). DOI: 10.2307/2273222. https://doi.org/10.2307/2273222
10. Antonio Montalbán, 'Computable structure theory: Within the arithmetic', Cambridge University Press, Perspectives in Logic (2021). DOI: 10.1017/9781108525749. https://doi.org/10.1017/9781108525749
11. Nikolay A. Bazhenov, Iskander Sh. Kalimullin, and Marina V. Schwidefsky, 'An effective version of the Stone duality', preprint (2026), arXiv:2604.04492. https://arxiv.org/abs/2604.04492
12. Rodney G. Downey and Alexander Melnikov, 'Computable structure theory: A unified approach', Springer, Theory and Applications of Computability (2026). DOI: 10.1007/978-3-031-92433-0. https://doi.org/10.1007/978-3-031-92433-0