Every countable model of set theory embeds into its own constructible universe, Fields Institute, Toronto, August 2012

This will be a talk for the  Toronto set theory seminar at the Fields Institute, University of Toronto, on August 24, 2012.

Abstract.  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 $\mathbb{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 Image: Igougo.comwith the surreal numbers. The proof shows that $L^M$ contains a submodel that is a universal acyclic digraph of rank $\text{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, the bi-embeddability classes form a well-ordered chain of length $\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 $\text{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.

Article | my profile at set theory talks | Toronto Set Theory Seminar post

Fields Institute, Toronto, Scientific Researcher, 2012

During August 2012, I was a visiting Scientific Researcher at the Fields Institute at the University of Toronto, participating in their thematic program on Forcing and it Applications.

What is the theory of ZFC-Powerset? Toronto 2011

This was a talk at the Toronto Set Theory Seminar held April 22, 2011 at the Fields Institute in Toronto.

The theory ZFC-, consisting of the usual axioms of ZFC but with the powerset axiom removed, when axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the axiom of choice, is weaker than commonly supposed, and suffices to prove neither that a countable union of countable sets is countable, nor that $\omega_1$ is regular, nor that the Los theorem holds for ultrapowers, even for well-founded ultrapowers on a measurable cardinal, nor that the Gaifman theorem holds, that is, that every $\Sigma_1$-elementary cofinal embedding $j:M\to N$ between models of the theory is fully elementary, nor that $\Sigma_n$ sets are closed under bounded quantification. Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory obtained by using the collection axiom rather than replacement in the axiomatization above. These results extend prior work of Zarach. This is joint work with Victoria Gitman and Thomas Johnstone.

Article | Victoria Gitman’s post