Minimal degrees of structures

Question

For this question, a structure means a first-order structure in a computable language with domain $\omega$; a copy of a structure $\mathcal{A}$ is a structure $\mathcal{B}\cong\mathcal{A}$.

---

Given a structure $\mathcal{A}$, we can try to understand the computability-theoretic complexity of $\mathcal{A}$ in various ways. One very natural approach is to analyze the spectrum of $\mathcal{A}$: $$Spec(\mathcal{A})=\{d: d\text{ computes a copy of $\mathcal{A}$}\}.$$ The spectrum is always(ish) closed upwards, but beyond that can be a very complicated object, so it is natural to consider the degree of $\mathcal{A}$: $$deg(\mathcal{A})=\min\{d: d\text{ computes a copy of $\mathcal{A}$}\}.$$ Unfortunately, not every structure has a degree: Linda Richter showed that, unless $\mathcal{A}$ is "locally complicated," then $Spec(\mathcal{A})$ contains a minimal pair: there are $d_0, d_1\in Spec(\mathcal{A})$ such that $d_0, d_1>_T0$ but $d_0\wedge d_1\equiv_T0$. If $\mathcal{A}$ does not have a computable copy, this means $deg(\mathcal{A})$ does not exist. For example, if $\mathcal{L}$ is a linear order with no computable copy, $\mathcal{L}$ has no degree.

This addresses the existence of least degrees of presentations; I'm wondering about minimal degrees of presentations. Say $d\in Spec(\mathcal{A})$ is $\mathcal{A}$-minimal if there is no $e\in Spec(\mathcal{A})$ with $e<_Td$.

Optimistically:

Question 1: Does every structure $\mathcal{A}$ have an $\mathcal{A}$-minimal degree?

And in the opposite direction,

Question 2: Is there a linear order $\mathcal{L}$ - with no computable copy - which has a $\mathcal{L}$-minimal degree?

Answer 1

Question 1: Does every structure $\mathcal{A}$ have an $\mathcal{A}$-minimal degree?

No. Diamondstone, Greenberg, and Turetsky show that the set of array noncomputable degrees is a degree spectrum.

And Downey, Jockusch and Stob showed that a degree is array noncomputable iff it computes a pb-generic set. Now if $G=A\oplus B$ is pb-generic, then so are $A$ and $B$, and they are strictly Turing below $A\oplus B$.

Question 2: Is there a linear order $\mathcal{L}$ which has a $\mathcal{L}$-minimal degree?

Yes. Russell Miller showed that there is a linear order whose degree spectrum includes every nonzero $\Delta^0_2$ degree, but not $\mathbf 0$.

And Sacks showed that there is a minimal Turing degree that is $\Delta^0_2$; so we are done.

References

David Diamondstone, Noam Greenberg, and Daniel Turetsky, Natural large degree spectra, Computability 2 (2013), no. 1, 1--8.

Russell Miller, The $\Delta^0_2$-spectrum of a linear order, J. Symbolic Logic 66 (2001), no. 2, 470--486.