Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
type: Item
instance of: scholarly article
title: Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
zbMATH Open document ID: 1048.03035
author: Denis R. Hirschfeldt
author: Walker M. White
published in: Notre Dame Journal of Formal Logic
publication date: 2004-05-27T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D55
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03C15
zbMATH DE Number: 2068391
zbMATH Keywords: degree spectrum
zbMATH Keywords: degree spectra of relations
zbMATH Keywords: computable structures
zbMATH Keywords: computable model theory
zbMATH Keywords: hyperarithmetic hierarchy
reviewed by: Jeffry L. Hirst
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1305/ndjfl/1071505769
OpenAlex ID: W2029067240
cites work: Generalizations of enumeration reducibility using recursive infinitary propositional sentences
cites work: Permitting, forcing, and copying of a given recursive relation
cites work: Computable structures and the hyperarithmetical hierarchy
cites work: Pairs of recursive structures
cites work: Relatively recursive expansions
cites work: A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
cites work: Ramified systems
cites work: Possible degrees in recursive copies
cites work: Possible degrees in recursive copies. II
cites work: Q3919698
cites work: Q3919704
cites work: Some effects of Ash-Nerode and other decidability conditions on degree spectra
cites work: Turing degrees of certain isomorphic images of computable relations
cites work: Degree Spectra of Relations on Computable Structures
cites work: Degree spectra of relations on computable structures in the presence of Δ20isomorphisms
cites work: Degree spectra and computable dimensions in algebraic structures
cites work: Q4938557
cites work: Coding a family of sets
cites work: Q4040890
cites work: Q4428702
cites work: Q3819052
cites work: Q5494238
cites work: Regular enumerations
DOI: 10.1305/NDJFL/1071505769
description: scientific article; zbMATH DE number 2068391