Degrees that are not degrees of categoricity

DOI10.1215/00294527-3496154zbMATH Open1436.03229arXiv1210.4220OpenAlexW3100375940MaRDI QIDQ306834FDOQ306834

Authors: Bernard Anderson, Barbara Csima 

Publication date: 1 September 2016

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

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.

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

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

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)

Cites Work

• Computability and randomness
• Title not available (Why is that?)
• Degrees of categoricity and the hyperarithmetic hierarchy
• Degrees of categoricity of computable structures
• Reals n-generic relative to some perfect tree
• Title not available (Why is that?)
• 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 on a cone via \(\eta\)-systems
• Degrees of categoricity of rigid structures
• Degrees of categoricity and spectral dimension
• A note on effective categoricity for linear orderings
• Degrees of autostability for linear orders and linearly ordered abelian groups
• Categoricity spectra of computable structures
• 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
• Degrees of categoricity and treeable degrees
• On decidable categoricity and almost prime models
• Title not available (Why is that?)
• 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
• Coding in the automorphism group of a computably categorical structure
• Turing degrees of complete formulas of almost prime models

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)