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?
> 
> 
> 



Minimal degrees of structures

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


No. [Diamondstone, Greenberg, and Turetsky](http://diamondstone.me/natural_degree_spectra.pdf) 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](http://www.jstor.org/discover/10.2307/2695025?uid=3739632&uid=2&uid=4&uid=3739256&sid=21106837731153) 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**](http://www.ams.org/mathscinet-getitem?mr=3123249), *Computability* **2** (2013), no. 1, 1--8.


*Russell Miller*, [**The $\Delta^0\_2$-spectrum of a linear order**](http://dx.doi.org/10.2307/2695025), *J. Symbolic Logic* **66** (2001), no. 2, 470--486.


