This will be a talk for the Rutgers Logic Seminar on November 19, 2012.

Abstract.  I will speak on my recent theorem that every countable model of set theory 𝑀, including every well-founded model, is isomorphic to a submodel of its own constructible universe. In other words, there is an embedding 𝑗 :𝑀 →𝐿𝑀 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 ℚ-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 𝐿𝑀 contains a submodel that is a universal acyclic digraph of rank Ord𝑀. 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, the bi-embeddability classes form a well-ordered chain of length 𝜔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 𝑀 is universal for all countable well-founded binary relations of rank at most Ord𝑀; 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 𝑀 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 𝐻⁡𝐹𝑀 of 𝑀. Indeed, 𝐻⁡𝐹𝑀 is universal for all countable acyclic binary relations.

Article | Rutgers Logic Seminar