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 vol. 43 (2002), pp. 51 - 64.

Availability: PostScript

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.