{
  "id": "1405.7456",
  "version": "v2",
  "published": "2014-05-29T04:08:28.000Z",
  "updated": "2014-12-10T08:12:35.000Z",
  "title": "Computable structures in generic extensions",
  "authors": [
    "Julia Knight",
    "Antonio Montalban",
    "Noah Schweber"
  ],
  "comment": "15 pages; submitted",
  "categories": [
    "math.LO"
  ],
  "abstract": "In this paper, we investigate connections between structures present in every generic extension of the universe $V$ and computability theory. We introduce the notion of {\\em generic Muchnik reducibility} that can be used to to compare the complexity of uncountable structures; we establish basic properties of this reducibility, and study it in the context of {\\em generic presentability}, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making $\\omega_2$ countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentble by a forcing notion that does not make $\\omega_2$ countable has a copy in the ground model. We also show that any countable structure $\\mathcal{A}$ that is generically presentable by a forcing notion not collapsing $\\omega_1$ has a countable copy in $V$, as does any structure $\\mathcal{B}$ generically Muchnik reducible to a structure $\\mathcal{A}$ of cardinality $\\aleph_1$. The former positive result yields a new proof of Harrington's result that counterexamples to Vaught's conjecture have models of power $\\aleph_1$ with Scott rank arbitrarily high below $\\omega_2$. Finally, we show that a rigid structure with copies in all generic extensions by a given forcing has a copy already in the ground model.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-29T04:08:28.000Z",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-12-10T08:12:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "generic extension",
      "computable structures",
      "ground model",
      "forcing notion",
      "countable structure"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.7456K"
    }
  }
}