{
  "id": "1207.0963",
  "version": "v3",
  "published": "2012-07-04T12:55:16.000Z",
  "updated": "2014-02-13T16:52:30.000Z",
  "title": "Every countable model of set theory embeds into its own constructible universe",
  "authors": [
    "Joel David Hamkins"
  ],
  "comment": "25 pages, 2 figures. Questions and commentary can be made at http://jdh.hamkins.org/every-model-embeds-into-own-constructible-universe. (v2 adds a reference and makes minor corrections) (v3 includes further changes, and removes the previous theorem 15, which was incorrect.)",
  "journal": "Journal of Mathematical Logic, vol. 13, iss. 2, p. 1350006, 2013",
  "doi": "10.1142/S0219061313500062",
  "categories": [
    "math.LO"
  ],
  "abstract": "The main theorem of this article is that every countable model of set theory M, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding $j:M\\to L^M$ that is elementary for quantifier-free assertions. The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random Q-graded digraph, and higher analogues arising as uncountable Fraisse limits, leading to the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, closely connected with the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $Ord^M$. The method of proof also establishes that the countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory, one of them is isomorphic to a submodel of the other. Indeed, they are pre-well-ordered by embedability in order-type exactly $\\omega_1+1$. Specifically, the countable well-founded models are ordered by embeddability in accordance with the heights of their ordinals; every shorter model embeds into every taller model; every model of set theory $M$ is universal for all countable well-founded binary relations of rank at most $Ord^M$; and every ill-founded model of set theory is universal for all countable acyclic binary relations. Finally, strengthening a classical theorem of Ressayre, the same proof method shows that if $M$ is any nonstandard model of PA, then every countable model of set theory---in particular, every model of ZFC---is isomorphic to a submodel of the hereditarily finite sets $HF^M$ of $M$. Indeed, $HF^M$ is universal for all countable acyclic binary relations.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-02-13T16:52:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03Exx",
      "03C62",
      "03Hxx"
    ],
    "keywords": [
      "countable model",
      "set theory embeds",
      "constructible universe",
      "countable acyclic binary relations",
      "shorter model embeds"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1207.0963H"
    }
  }
}