Paper detail

Degree Spectra of Relations on a Cone

Let $\mathcal{A}$ be a mathematical structure with an additional relation $R$. We are interested in the degree spectrum of $R$, either among computable copies of $\mathcal{A}$ when $(\mathcal{A},R)$ is a "natural" structure, or (to make this rigorous) among copies of $(\mathcal{A},R)$ computable in a large degree \textbf{d}. We introduce the partial order of degree spectra \textit{on a cone} and begin the study of these objects. Using a result of Harizanov---that, assuming an effectiveness condition on $\mathcal{A}$ and $R$, if $R$ is not intrinsically computable, then its degree spectrum contains all c.e.\ degrees---we see that there is a minimal non-trivial degree spectrum on a cone, consisting of the c.e.\ degrees. We show that this does not generalize to d.c.e.\ degrees by giving an example of two incomparable degree spectra on a cone. We also give a partial answer to a question of Ash and Knight: they asked whether (subject to some effectiveness conditions) a relation which is not intrinsically $Δ^0_α$ must have a degree spectrum which contains all of the $α$-CEA degrees. We give a positive answer to this question for $α= 2$ by showing that any degree spectrum on a cone which strictly contains the $Δ^0_2$ degrees must contain all of the 2-CEA degrees. We also investigate the particular case of degree spectra on the structure $(ω,<)$. This work represents the beginning of an investigation of the degree spectra of "natural" structures, and we leave many open questions to be answered.