Degrees that are not degrees of categoricity

DOI10.1215/00294527-3496154MaRDI QIDQ306834zbMATH OpenOpenAlexFDO

Authors Bernard Anderson, Barbara Csima

Publication date 1 September 2016

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

Full work available at URL https://arxiv.org/abs/1210.4220, https://projecteuclid.org/euclid.ndjfl/1460032557

zbMATH Keywords

category spectrumCatSpeccomputable structurecomputably categoricaldegree of categoricitystrong degree of categoricity

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: A computable structure A is x-computably categorical for some Turing degree x, if for every computable structure B isomorphic to A there is an isomorphism f:B -> A with f computable in x. A degree x is a degree of categoricity if there is a computable A such that A is x-computably categorical, and for all y, if A is y-computably categorical then y computes x. We construct a Sigma_2 set whose degree is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity.

Recommendations

• Degrees of categoricity of computable structures
• Degrees of categoricity and the hyperarithmetic hierarchy
• Categoricity spectra for rigid structures
• Degrees of categoricity and spectral dimension
• Degrees of categoricity on a cone via \(\eta\)-systems

Cites work

• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 1302870 (Why is no real title available?)
• Computability and randomness
• Degrees of categoricity and the hyperarithmetic hierarchy
• Degrees of categoricity of computable structures
• Reals n-generic relative to some perfect tree
• The Degrees of Hyperimmune Sets

Cited in

(25)

• Categoricity spectra for rigid structures
• Finite computable dimension and degrees of categoricity
• Computability-theoretic categoricity and Scott families
• Strength and weakness in computable structure theory
• Degrees of categoricity of rigid structures
• Degrees of categoricity on a cone via \(\eta\)-systems
• Degrees of categoricity and spectral dimension
• Categoricity spectra of computable structures
• Degrees of autostability for linear orders and linearly ordered abelian groups
• A note on effective categoricity for linear orderings
• Degrees of categoricity vs. strong degrees of categoricity
• Strong degrees of categoricity and weak density
• Analytic computable structure theory and \(L^p\)-spaces. II
• Prime model with no degree of autostability relative to strong constructivizations
• On decidable categoricity and almost prime models
• Degrees of categoricity and treeable degrees
• scientific article; zbMATH DE number 5354050 (Why is no real title available?)
• Degrees of categoricity and the hyperarithmetic hierarchy
• Degrees of categoricity of trees and the isomorphism problem
• Every Δ20 degree is a strong degree of categoricity
• Degrees of bi-embeddable categoricity
• Degrees of categoricity of computable structures
• Lowness for isomorphism and degrees of genericity
• Turing degrees of complete formulas of almost prime models
• Coding in the automorphism group of a computably categorical structure

This page was built for publication: Degrees that are not degrees of categoricity

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