Abstract
A computable structure is -computably categorical for some Turing degree if for every computable structure there is an isomorphism with . A degree is a degree of categoricity if there is a computable structure such that is -computably categorical, and for all , if is -computably categorical, then .
We construct a 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.
Bernard Anderson. Barbara Csima. "Degrees That Are Not Degrees of Categoricity." Notre Dame J. Formal Logic 57 (3) 389 - 398, 2016. https://doi.org/10.1215/00294527-3496154
Information