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

DOI10.1305/NDJFL/1071505769zbMath1048.03035OpenAlexW2029067240MaRDI QIDQ1430995

Denis R. Hirschfeldt, Walker M. White

Publication date: 27 May 2004

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1071505769

zbMATH Keywords

computable structurescomputable model theoryhyperarithmetic hierarchydegree spectrumdegree spectra of relations

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Model theory of denumerable and separable structures (03C15) Hierarchies of computability and definability (03D55)

Related Items (12)

Degrees of categoricity of trees and the isomorphism problem ⋮ Degrees of categoricity and the hyperarithmetic hierarchy ⋮ Strength and Weakness in Computable Structure Theory ⋮ The property “arithmetic-is-recursive” on a cone ⋮ Π₁⁰ classes and strong degree spectra of relations ⋮ Degree spectra of structures relative to equivalences ⋮ On the orbits of computably enumerable sets ⋮ Tree-Automatic Well-Founded Trees ⋮ The isomorphism problem on classes of automatic structures with transitive relations ⋮ RELATIVE TO ANY NON-HYPERARITHMETIC SET ⋮ ORDINAL ANALYSIS OF PARTIAL COMBINATORY ALGEBRAS ⋮ SCOTT COMPLEXITY OF COUNTABLE STRUCTURES

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pairs of recursive structures
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• Generalizations of enumeration reducibility using recursive infinitary propositional sentences
• Turing degrees of certain isomorphic images of computable relations
• Coding a family of sets
• Ramified systems
• Permitting, forcing, and copying of a given recursive relation
• Possible degrees in recursive copies. II
• Computable structures and the hyperarithmetical hierarchy
• Degree spectra and computable dimensions in algebraic structures
• Possible degrees in recursive copies
• Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms
• A Completeness Theorem for Certain Classes of Recursive Infinitary Formulas
• Relatively recursive expansions
• Regular enumerations
• Degree Spectra of Relations on Computable Structures

This page was built for publication: Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures