Degree spectra of relations on a cone

DOI10.1090/MEMO/1208zbMATH Open1435.03005arXiv1412.3842OpenAlexW2269014414MaRDI QIDQ4645836FDOQ4645836

Authors: Matthew Harrison-Trainor 

Publication date: 11 January 2019

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

Abstract: Let $mathcalA$ be a mathematical structure with an additional relation $R$. We are interested in the degree spectrum of $R$, either among computable copies of $mathcalA$ when $(mathcalA,R)$ is a "natural" structure, or (to make this rigorous) among copies of $(mathcalA,R)$ computable in a large degree extbf{d}. We introduce the partial order of degree spectra extit{on a cone} and begin the study of these objects. Using a result of Harizanov---that, assuming an effectiveness condition on $mathcalA$ and $R$, if $R$ is not intrinsically computable, then its degree spectrum contains all c.e. degrees---we see that there is a minimal non-trivial degree spectrum on a cone, consisting of the c.e. degrees. We show that this does not generalize to d.c.e. degrees by giving an example of two incomparable degree spectra on a cone. We also give a partial answer to a question of Ash and Knight: they asked whether (subject to some effectiveness conditions) a relation which is not intrinsically $Delt{a}_a^{0}lpha$ must have a degree spectrum which contains all of the $alpha$-CEA degrees. We give a positive answer to this question for $alpha=2$ by showing that any degree spectrum on a cone which strictly contains the $Delt{a}_2^0$ degrees must contain all of the 2-CEA degrees. We also investigate the particular case of degree spectra on the structure $(omega,<)$. This work represents the beginning of an investigation of the degree spectra of "natural" structures, and we leave many open questions to be answered.

Full work available at URL: https://arxiv.org/abs/1412.3842

Recommendations

• Degree spectra of intrinsically c. e. relations
• Degree spectra of relations on structures of finite computable dimension
• Degree spectra of relations on computable structures in the presence of Δ₂⁰isomorphisms
• Degrees of relations on ordinals
• Some effects of Ash-Nerode and other decidability conditions on degree spectra

zbMATH Keywords

computable structuredegree spectrum of a relationcone of Turing degrees

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Cites Work

• Borel determinacy
• Set Theory
• Title not available (Why is that?)
• Generic copies of countable structures
• Computable structures and the hyperarithmetical hierarchy
• The axiom of determinateness and reduction principles in the analytical hierarchy
• Effective model theory vs. recursive model theory
• The theory of well-quasi-ordering: a frequently discovered concept
• Title not available (Why is that?)
• Recursive Structures and Ershov's Hierarchy
• Title not available (Why is that?)
• Title not available (Why is that?)
• A classification of jump operators
• Degrees coded in jumps of orderings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Degree spectra of unary relations on $\langle \omega, \leq \rangle$
• Degree Spectra of Relations on Computable Structures
• Title not available (Why is that?)
• Notes on the Jump of a Structure
• Intrinsic Reducibilities
• Title not available (Why is that?)
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Some effects of Ash-Nerode and other decidability conditions on degree spectra
• On the spectrum of degrees of decidable relations
• The possible Turing degree of the nonzero member in a two element degree spectrum
• Computable isomorphisms, degree spectra of relations, and Scott families
• Coding a family of sets
• Possible degrees in recursive copies. II
• Possible degrees in recursive copies

Cited In (8)

• Relativized Degree Spectra
• Logical Approaches to Computational Barriers
• Degrees of categoricity on a cone via \(\eta\)-systems
• Categoricity spectra of computable structures
• Degrees of relations on ordinals
• Degree spectra of intrinsically c. e. relations
• THE COMPLEMENTS OF LOWER CONES OF DEGREES AND THE DEGREE SPECTRA OF STRUCTURES
• Relación entre conos de direcciones decrecientes y conos de direcciones de descenso

This page was built for publication: Degree spectra of relations on a cone

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645836)