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.






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.


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

  1. Super talk yesterday. Thanks! Here is a question I didn’t get to ask after the talk: Is the power set of the natural numbers universal for a natural collection of posets which is larger than the collection of countable posets? (Here, of course I don’t know what I mean by “natural.” Of course it is universal for the collection of all of its subobjects. I want a more illuminating answer than that.)

    Thanks again!


    • I’m glad to hear that you enjoyed the talk; it was a pleasure to visit Swarthmore. I was impressed by the students and in particular by the sophisticated nature of their mathematical conversations.

      Meanwhile, your question is extremely natural. The proof that $\langle\mathbb{R},\lt\rangle$ embeds into $\langle P(\mathbb{N}),\subset\rangle$, which I think many find surprising (as we saw yesterday), can be generalized to a more general theorem about partial orders having a countable separating set, in the sense that there is a countable set $Q$ such that for any two distinct elements $a\neq b$ of the partial order, they have distinct predecessors in $Q$. In the case of the reals $\mathbb{R}$, we had used the rationals $\mathbb{Q}$ in this way. But the same idea works in the general case: you map each $a$ in the partial order to the elements in $Q$ below it. This is an order-preserving map into $P(Q)$, which is isomorphic to $P(\mathbb{N})$, and so we get the universality result. Since there are many uncountable partial orders that are separated by countable sets in that way, this is a strictly more general universality property.

      Meanwhile, one can also construct partial orders and even linear orders of size at most continuum that do not embed into $P(\mathbb{N})$. For example, the first uncountable ordinal $\omega_1$ has no embedding into $P(\mathbb{N})$, because any such embedding would provide an injection of $\omega_1$ into $\mathbb{N}$.

Leave a Reply

Your email address will not be published. Required fields are marked *