Realizing Levels of the Hyperarithmetic Hierarchy as Degree
Spectra of Relations on Computable Structures
Status: published in the Notre Dame Journal of Formal Logic
vol. 43 (2002), pp. 51 - 64.
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 Sigmaa invariant relation whose degree
spectrum consists of all nontrivial Sigmaa
r-degrees. We extend this construction to show that
Sigmaa can be replaced by either
Pia or Deltaa.