Degree Spectra of Relations on a Cone
Matthew Harrison‐Trainor · Memoirs of the American Mathematical Society · 2018
Let A \mathcal {A} be a mathematical structure with an additional relation R R . We are interested in the degree spectrum of R R , either among computable copies of A \mathcal {A} when ( A , R ) (\mathcal {A},R) is a “natural” structure, or (to make this rigorous) among copies of ( A , R ) (\mathcal {A},R) computable in a large degree d . We introduce the partial order of degree spectra on a cone and begin the study of these objects. Using a result of Harizanov—that, assuming an effectiveness condition on A \mathcal {A} and R R , if R 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 \Delta ^0_\alpha must have a degree spectrum which contains all of the α \alpha -CEA degrees. We give a positive answer to this question for α = 2 \alpha = 2 by showing that any degree spectrum on a cone which strictly contains the Δ 2 0 \Delta ^0_2