2012/07/31 by Joel David Hamkins · 1 voice
Mathematics · #math.LO #msc:03Exx #msc:03C62 #msc:03Hxx
paper · pdf · doi:10.1142/s0219061313500062
published as Journal of Mathematical Logic, vol. 13, iss. 2, p. 1350006, 2013 · 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.)
arxiv created 2014/02/13 · arxiv updated 2014/02/14
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→ LM 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 LM contains a submodel that is a universal acyclic digraph of rank OrdM. 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 ω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 OrdM; 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 HFM of M. Indeed, HFM is universal for all countable acyclic binary relations.