Universal structures, GC MathFest, February 2014

Midtown in WinterThis will be a talk for the CUNY Graduate Center MathFest, held on the afternoon of Februrary 4, 2014, intended for graduate-school-bound undergraduate students, including prospective students for the CUNY Graduate Center, giving them a chance to meet graduate students and faculty at the CUNY Graduate Center and see the kind of mathematics that is done here.

In this 30 minute talk, I’ll introduce the concept of a universal structure, with various examples, including the countable random graph, the surreal number line and the hypnagogic digraph.

MathFest Program/schedule

Universal structures: the countable random graph, the surreal numbers and the hypnagogic digraph, Swarthmore College, October 2013

I’ll be speaking for the Swarthmore College Mathematics and Statistics Colloquium on October 8th, 2013.

220px-Swarthmore_College_Logo_Current

 

 

 

 

Abstract.  I’ll be giving an introduction to universal structures in mathematics, where a structure $\mathcal{M}$ is universal for a class of structures, if every structure in that class arises as (isomorphic to) a substructure of $\mathcal{M}$.  For example, Cantor proved that the rational line $\mathbb{Q}$ is universal for all countable linear orders.  Is a corresponding fact true of the real line for linear orders of that size? Are there countably universal partial orders? Is there a countably universal graph? directed graph? acyclic digraph?  Is there a countably universal group? We’ll answer all these questions and more, with an account of the countable random graph, generalizations to the random graded digraphs, Fraïssé limits, the role of saturation, the surreal numbers and the hypnagogic digraph.  The talk will conclude with some very recent work on universality amongst the models of set theory.

Poster

Every countable model of set theory is isomorphic to a submodel of its own constructible universe, Barcelona, December, 2012

This will be a talk for a set theory workshop at the University of Barcelona on December 15, 2012, organized by Joan Bagaria.

Vestíbul Universitat de Barcelona

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 with 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 | Barcelona research group in set theory