Realizing Levels of the Hyperarithmetic Hierarchy as Degree
Spectra of Relations on Computable Structures
Status: published in the Notre Dame
Journal of Formal Logic 43 (2002) 51 - 64.
version and preprint
Abstract. We construct a class of relations on computable
structures whose degree spectra form natural classes of degrees. Given
any computable ordinal a and reducibility r stronger than or
equal to m-reducibility, we show how to construct a structure with an
intrinsically Σa invariant relation whose degree
spectrum consists of all nontrivial Σa
r-degrees. We extend this construction to show that
Σa can be replaced by either
Πa or Δa.