Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures (Q1430995)

This article continues the work on degree spectra of relations on computable structures begun by \textit{C. J. Ash} and \textit{A. Nerode} [Aspects of effective algebra, 26--41 (1981; Zbl 0467.03041)], \textit{V. S. Harizanov} [Ann. Pure Appl. Logic 55, No. 1, 51--65 (1991; Zbl 0756.03022)], and others. Suppose \(U\) is a relation on the domain of a computable structure \(\mathcal M\). \(U\) is intrinsically \(\Sigma_\alpha\) on \(\mathcal M\) if the image of \(U\) in each computable presentation of \(\mathcal M\) is in \(\Sigma_\alpha\). If \(s\) is a reducibility (e.g. \(m\)-reducibility) the \(s\)-degree spectrum of \(U\) on \(\mathcal M\), DgSp\(^s_{\mathcal M} (U)\), is the set of \(s\)-degrees of images of \(U\) in all computable presentations of \(\mathcal M\). The central result of the article states that all levels of the hyperarithmetic hierarchy can be realized as degree spectra. That is, given any computable ordinal \(\alpha\) and any reducibility \(s\) which is at least as strong as \(m\)-reducibility, there is an intrinsically \(\Sigma_\alpha\) invariant relation \(U\) on a computably presentable structure \(\mathcal M\) such that DgSp\(^s_{\mathcal M} (U)\) consists of all nontrivial \(\Sigma_\alpha\) \(s\)-degrees. In this statement, \(\Sigma_\alpha\) may be replaced by \(\Pi_\alpha\) or \(\Delta_\alpha\).