Realizing Levels of the Hyperarithmetic Hierarchy as Degree Spectra of Relations on Computable Structures

by Denis R. Hirschfeldt and Walker M. White

Status: published in the Notre Dame Journal of Formal Logic 43 (2002) 51 - 64.

Availability: journal 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.