Degrees that are not degrees of categoricity

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

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• The Degrees of Hyperimmune Sets

Cited In (21)

• Finite computable dimension and degrees of categoricity
• Computability-theoretic categoricity and Scott families
• Degrees of categoricity of rigid structures
• 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
• Strength and Weakness in Computable Structure Theory
• A Note on Effective Categoricity for Linear Orderings
• Analytic computable structure theory and \(L^p\)-spaces. II
• Degrees of categoricity and treeable degrees
• On decidable categoricity and almost prime models
• Title not available (Why is that?)
• Degrees of categoricity of trees and the isomorphism problem
• DEGREES OF CATEGORICITY AND SPECTRAL DIMENSION
• Every Δ20 degree is a strong degree of categoricity
• Degrees of bi-embeddable categoricity
• Prime Model with No Degree of Autostability Relative to Strong Constructivizations
• DEGREES OF CATEGORICITY ON A CONE VIAη-SYSTEMS
• 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)