{
  "id": "1210.4220",
  "version": "v2",
  "published": "2012-10-15T23:56:21.000Z",
  "updated": "2014-04-06T21:55:52.000Z",
  "title": "Degrees that are not degrees of categoricity",
  "authors": [
    "Bernard A. Anderson",
    "Barbara F. Csima"
  ],
  "comment": "10 pages. Minor revisions",
  "categories": [
    "math.LO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-04-06T21:55:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D50",
      "F.4.1"
    ],
    "keywords": [
      "categoricity",
      "computable structure",
      "noncomputable hyperimmune-free degree",
      "perfect tree",
      "large class"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.4220A"
    }
  }
}