Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures
Denis R. Hirschfeldt, Walker M. White · Notre Dame Journal of Formal Logic · 2002
We construct a class of relations on computable structures whose degree spectra form natural classes of degrees. Given any computable ordinal $\alpha$ and reducibility r stronger than or equal to m-reducibility, we show how to construct a structure with an intrinsically $\Sigma_\alpha$ invariant relation whose degree spectrum consists of all nontrivial $\Sigma_\alpha$ r-degrees. We extend this construction to show that $\Sigma_\alpha$ can be replaced by either $\Pi_\alpha$ or $\Delta_\alpha$.