{
  "id": "2209.04524",
  "version": "v1",
  "published": "2022-09-09T21:00:43.000Z",
  "updated": "2022-09-09T21:00:43.000Z",
  "title": "The degrees of categoricity above $\\mathbf{0}\"$",
  "authors": [
    "Barbara F. Csima",
    "Dino Rossegger"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "We give a characterization of the degrees of categoricity of computable structures greater or equal to $\\mathbf 0\"$. They are precisely the treeable degrees - the least degrees of paths through computable trees - that compute $\\mathbf 0\"$. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree $\\mathbf d$ with $\\mathbf 0^{(\\alpha)}\\leq \\mathbf d\\leq \\mathbf 0^{(\\alpha+1)}$ or $\\alpha$ a computable ordinal greater than $2$ is the strong degree of categoricity of a rigid structure. Another corollary of our characterization partially answers a question of Fokina, Kalimullin, and Miller: Every degree of categoricity above $\\mathbf 0\"$ is strong. Using quite different techniques we show that every degree $\\mathbf d$ with $\\mathbf 0'\\leq \\mathbf d\\leq \\mathbf 0\"$ is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree $\\mathbf d$ with $\\mathbf 0'\\leq \\mathbf d\\leq \\mathbf 0\"$ that is not the degree of categoricity of a rigid structure.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-09-09T21:00:43.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03C75",
      "03D45",
      "03E15"
    ],
    "keywords": [
      "categoricity",
      "rigid structure",
      "strong degree",
      "computable structures greater",
      "computable ordinal greater"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}