Universality and embeddability amongst the models of set theory, CTFM 2015, Tokyo, Japan

Tokyo Institute of TechnologyThis will be a talk for the Computability Theory and Foundations of Mathematics conference at the Tokyo Institute of Technology, September 7-11, 2015.  The conference is held in celebration of Professor Kazuyuki Tanaka’s 60th birthday.

Abstract. Recent results on the embeddability phenomenon and universality amongst the models of set theory are an appealing blend of ideas from set theory, model theory and computability theory. Central questions remain open.

A surprisingly vigorous embeddability phenomenon has recently been uncovered amongst the countable models of set theory. It turns out, for instance, that among these models embeddability is linear: for any two countable models of set theory, one of them embeds into the other. Indeed, one countable model of set theory $M$ embeds into another $N$ just in case the ordinals of $M$ order-embed into the ordinals of $N$. This leads to many surprising instances of embeddability: every forcing extension of a countable model of set theory, for example, embeds into its ground model, and every countable model of set theory, including every well-founded model, embeds into its own constructible universe.

V to LAlthough the embedding concept here is the usual model-theoretic embedding concept for relational structures, namely, a map $j:M\to N$ for which $x\in^M y$ if and only if $j(x)\in^N j(y)$, it is a weaker embedding concept than is usually considered in set theory, where embeddings are often elementary and typically at least $\Delta_0$-elementary. Indeed, the embeddability result is surprising precisely because we can easily prove that in many of these instances, there can be no $\Delta_0$-elementary embedding.

The proof of the embedding theorem makes use of universality ideas in digraph combinatorics, including an acyclic version of the countable random digraph, the countable random $\mathbb{Q}$-graded digraph, and higher analogues arising as uncountable Fraïssé limits, leading to the hypnagogic digraph, a universal homogeneous graded acyclic class digraph, closely connected with the surreal numbers. Thus, the methods are a blend of ideas from set theory, model theory and computability theory.

Results from Incomparable $\omega_1$-like models of set theory show that the embedding phenomenon does not generally extend to uncountable models. Current joint work of myself, Aspero, Hayut, Magidor and Woodin is concerned with questions on the extent to which the embeddings arising in the embedding theorem can exist as classes inside the models in question. Since the embeddings of the theorem are constructed externally to the model, by means of a back-and-forth-style construction, there is little reason to expect, for example, that the resulting embedding $j:M\to L^M$ should be a class in $M$. Yet, it has not yet known how to refute in ZFC the existence of a class embedding $j:V\to L$ when $V\neq L$. However, many partial results are known. For example, if the GCH fails at an uncountable cardinal, if $0^\sharp$ exists, or if the universe is a nontrivial forcing extension of some ground model, then there is no embedding $j:V\to L$. Meanwhile, it is consistent that there are non-constructible reals, yet $\langle P(\omega),\in\rangle$ embeds into $\langle P(\omega)^L,\in\rangle$.

CFTM 2015 extended abstract | Article | CFTM | Slides

The hypnagogic digraph, with applications to embeddings of the set-theoretic universe, JMM Special Session on Surreal Numbers, Seattle, January 2016

JMM 2016 SeattleThis will be an invited talk for the AMS-ASL special session on Surreal Numbers at the 2016 Joint Mathematics Meetings in Seattle, Washington, January 6-9, 2016.

Abstract. The hypnagogic digraph, a proper-class analogue of the countable random $\mathbb{Q}$-graded digraph, is a surreal-numbers-graded acyclic digraph exhibiting the set-pattern property (a form of existential-closure), making it set-homogeneous and universal for all class acyclic digraphs. A natural copy of this canonical structure arises during the course of the usual construction of the surreal number line, using as vertices the surreal-number numerals $\{\ A \mid B\ \}$.  I shall explain the construction and elementary theory of the hypnagogic digraph and describe recent uses of it in connection with embeddings of the set-theoretic universe, such as in the proof that the countable models of set theory are linearly pre-ordered by embeddability.

Slides | schedule | related article | surreal numbers (Wikipedia)

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

Universality, saturation and the surreal number line, Shanghai, June 2013

Fudan bridgeThis will be a short lecture series given at the conclusion of the graduate logic class in the Mathematical Logic group at Fudan University in Shanghai, June 13, 18 (or 20), 2013.

I will present an elementary introduction to the theory of universal orders and relations and saturated structures.  We’ll start with the classical fact, proved by Cantor, that the rational line is the universal countable linear order.  But what about universal partial orders, universal graphs and other mathematical structures?  Is there a computable universal partial order?  What is the countable random graph? Which orders embed into  the power set of the natural numbers under the subset relation $\langle P(\mathbb{N}),\subset\rangle$? Proceeding to larger and larger universal orders, we’ll eventually arrive at the surreal numbers and the hypnagogic digraph.

Fudan University seal

 

Playing go with Jiachen

The countable models of set theory are linearly pre-ordered by embeddability, Rutgers, November 2012

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 $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 | Rutgers Logic Seminar

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

Every countable model of set theory embeds into its own constructible universe

  • J. D. Hamkins, “Every countable model of set theory embeds into its own constructible universe,” J. Math. Log., vol. 13, iss. 2, p. 1350006, 27, 2013.  
    @article {Hamkins2013:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL,
    AUTHOR = {Hamkins, Joel David},
    TITLE = {Every countable model of set theory embeds into its own
    constructible universe},
    JOURNAL = {J. Math. Log.},
    FJOURNAL = {Journal of Mathematical Logic},
    VOLUME = {13},
    YEAR = {2013},
    NUMBER = {2},
    PAGES = {1350006, 27},
    ISSN = {0219-0613},
    MRCLASS = {03C62 (03E99 05C20 05C60 05C63)},
    MRNUMBER = {3125902},
    MRREVIEWER = {Robert S. Lubarsky},
    DOI = {10.1142/S0219061313500062},
    eprint = {1207.0963},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    URL = {http://jdh.hamkins.org/every-model-embeds-into-own-constructible-universe/},
    }

In this article, I prove that every countable model of set theory $\langle M,{\in^M}\rangle$, including every well-founded model, is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$. Another way to say this is that there is an embedding
$$j:\langle M,{\in^M}\rangle\to \langle L^M,{\in^M}\rangle$$
that is elementary for quantifier-free assertions in the language of set theory.

Main Theorem 1. Every countable model of set theory $\langle M,{\in^M}\rangle$ is isomorphic to a submodel of its own constructible universe $\langle L^M,{\in^M}\rangle$.

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 eventually to what I call the hypnagogic digraph, a set-homogeneous, class-universal, surreal-numbers-graded acyclic class digraph, which is closely connected with the surreal numbers. The proof shows that $\langle L^M,{\in^M}\rangle$ contains a submodel that is a universal acyclic digraph of rank $\text{Ord}^M$, and so in fact this model is universal for all countable acyclic binary relations of this rank. When $M$ is ill-founded, this includes all acyclic binary relations. The method of proof also establishes the following, thereby answering a question posed by Ewan Delanoy.

Main Theorem 2. The countable models of set theory are linearly pre-ordered by embeddability: for any two countable models of set theory $\langle M,{\in^M}\rangle$ and $\langle N,{\in^N}\rangle$, either $M$ is isomorphic to a submodel of $N$ or conversely. Indeed, the countable models of set theory are pre-well-ordered by embeddability in order type exactly $\omega_1+1$.

The proof shows that the embeddability relation on the models of set theory conforms with their ordinal heights, in that any two models with the same ordinals are bi-embeddable; any shorter model embeds into any taller model; and the ill-founded models are all bi-embeddable and universal.

The proof method arises most easily in finite set theory, showing that the nonstandard hereditarily finite sets $\text{HF}^M$ coded in any nonstandard model $M$ of PA or even of $I\Delta_0$ are similarly universal for all acyclic binary relations. This strengthens a classical theorem of Ressayre, while simplifying the proof, replacing a partial saturation and resplendency argument with a soft appeal to graph universality.

Main Theorem 3. If $M$ is any nonstandard model of PA, then every countable model of set theory is isomorphic to a submodel of the hereditarily finite sets $\langle \text{HF}^M,{\in^M}\rangle$ of $M$. Indeed, $\langle\text{HF}^M,{\in^M}\rangle$ is universal for all countable acyclic binary relations.

In particular, every countable model of ZFC and even of ZFC plus large cardinals arises as a submodel of $\langle\text{HF}^M,{\in^M}\rangle$. Thus, inside any nonstandard model of finite set theory, we may cast out some of the finite sets and thereby arrive at a copy of any desired model of infinite set theory, having infinite sets, uncountable sets or even large cardinals of whatever type we like.

The proof, in brief:  for every countable acyclic digraph, consider the partial order induced by the edge relation, and extend this order to a total order, which may be embedded in the rational order $\mathbb{Q}$.  Thus, every countable acyclic digraph admits a $\mathbb{Q}$-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed $\mathbb{Q}$-graded digraph, simply by starting with nothing, and then adding finitely many nodes at each stage, so as to realize the finite pattern property. The result is a computable presentation of what I call the countable random $\mathbb{Q}$-graded digraph $\Gamma$.  If $M$ is any nonstandard model of finite set theory, then we may run this computable construction inside $M$ for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of $\Gamma$.  Furthermore, since $M$ thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of $M$.  By looking at the sets corresponding to the nodes in the copy of $\Gamma$, we find a submodel of $M$ that is isomorphic to $\Gamma$, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of $M$.

The article closes with a number of questions, which I record here (and which I have also asked on mathoverflow:  Can there be an embedding $j:V\to L$ from the set-theoretic universe $V$ to the constructible universe $L$, when $V\neq L$?) Although the main theorem shows that every countable model of set theory embeds into its own constructible universe  $$j:M\to L^M,$$ this embedding $j$ is constructed completely externally to $M$ and there is little reason to expect that $j$ could be a class in $M$ or otherwise amenable to $M$.  To what extent can we prove or refute the possibility that $j$ is a class in $M$? This amounts to considering the matter internally as a question about $V$. Surely it would seem strange to have a class embedding $j:V\to L$ when $V\neq L$, even if it is elementary only for quantifier-free assertions, since such an embedding is totally unlike the sorts of embeddings that one usually encounters in set theory. Nevertheless, I am at a loss to refute the hypothesis, and the possibility that there might be such an embedding is intriguing, if not tantalizing, for one imagines all kinds of constructions that pull structure from $L$ back into $V$.

Question 1.  Can there be an embedding $j:V\to L$ when $V\neq L$?

By embedding, I mean an isomorphism from $\langle V,{\in}\rangle$ to its range in $\langle L,{\in}\rangle$, which is the same as a quantifier-free-elementary map $j:V\to L$. The question is most naturally formalized in Gödel-Bernays set theory, asking whether there can be a GB-class $j$ forming such an embedding.  If one wants $j:V\to L$ to be a definable class, then this of course implies $V=\text{HOD}$, since the definable $L$-order can be pulled back to $V$, via $x\leq y\iff j(s)\leq_L j(y)$. More generally, if $j$ is merely a class in Gödel-Bernays set theory, then the existence of an embedding $j:V\to L$ implies global choice, since from the class $j$ we can pull back the $L$-order. For these reasons, we cannot expect every model of ZFC or of GB to have such embeddings. Can they be added generically? Do they have some large cardinal strength? Are they outright refutable?

It they are not outright refutable, then it would seem natural that these questions might involve large cardinals; perhaps $0^\sharp$ is relevant. But I am unsure which way the answers will go. The existence of large cardinals provides extra strength, but may at the same time make it harder to have the embedding, since it pushes $V$ further away from $L$. For example, it is conceivable that the existence of $0^\sharp$ will enable one to construct the embedding, using the Silver indiscernibles to find a universal submodel of $L$; but it is also conceivable that the non-existence of $0^\sharp$, because of covering and the corresponding essential closeness of $V$ to $L$, may make it easier for such a $j$ to exist. Or perhaps it is simply refutable in any case. The first-order analogue of the question is:

Question 2.  Does every set $A$ admit an embedding $j:\langle A,{\in}\rangle \to \langle L,{\in}\rangle$?  If not, which sets do admit such embeddings?

The main theorem shows that every countable set $A$ embeds into $L$. What about uncountable sets? Let us make the question extremely concrete:

Question 3. Does $\langle V_{\omega+1},{\in}\rangle$ embed into $\langle L,{\in}\rangle$? How about $\langle P(\omega),{\in}\rangle$ or $\langle\text{HC},{\in}\rangle$?

It is also natural to inquire about the nature of $j:M\to L^M$ even when it is not a class in $M$. For example, can one find such an embedding for which $j(\alpha)$ is an ordinal whenever $\alpha$ is an ordinal?  The embedding arising in the proof of the main theorem definitely does not have this feature.

Question 4. Does every countable model $\langle M,{\in^M}\rangle$ of set theory admit an embedding $j:M\to L^M$ that takes ordinals to ordinals?

Probably one can arrange this simply by being a bit more careful with the modified Mostowski procedure in the proof of the main theorem.  And if this is correct, then numerous further questions immediately come to mind, concerning the extent to which we ensure more attractive features for the embeddings $j$ that arise in the main theorems. This will be particularly interesting in the case of well-founded models, as well as in the case of $j:V\to L$, as in question , if that should be possible.

Question 5. Can there be a nontrivial embedding $j:V\to L$ that takes ordinals to ordinals?

Finally, I inquire about the extent to which the main theorems of the article can be extended from the countable models of set theory to the $\omega_1$-like models:

Question 6. Does every $\omega_1$-like model of set theory $\langle M,{\in^M}\rangle$ admit an embedding $j:M\to L^M$ into its own constructible universe? Are the $\omega_1$-like models of set theory linearly pre-ordered by embeddability?

The countable models of ZFC, up to isomorphism, are linearly pre-ordered by the submodel relation; indeed, every countable model of ZFC, including every transitive model, is isomorphic to a submodel of its own $L$, New York, 2012

This will be a talk on May 18, 2012 for the CUNY Logic Workshop on some extremely new work. The proof uses finitary digraph combinatorics, including the countable random digraph and higher analogues involving uncountable Fraisse limits, the surreal numbers and the hypnagogic digraph.

The story begins with Ressayre’s remarkable 1983 result that if $M$ is any nonstandard model of PA, with $\langle\text{HF}^M,{\in^M}\rangle$ the corresponding nonstandard hereditary finite sets of $M$, then for any consistent computably axiomatized theory $T$ in the language of set theory, with $T\supset ZF$, there is a submodel $N\subset\langle\text{HF}^M,{\in^M}\rangle$ such that $N\models T$. In particular, one may find models of ZFC or even ZFC + large cardinals as submodels of $\text{HF}^M$, a land where everything is thought to be finite. Incredible! Ressayre’s proof uses partial saturation and resplendency to prove that one can find the submodel of the desired theory $T$.

My new theorem strengthens Ressayre’s theorem, while simplifying the proof, by removing the theory $T$. We need not assume $T$ is computable, and we don’t just get one model of $T$, but rather all models—the fact is that the nonstandard models of set theory are universal for all countable acyclic binary relations. So every model of set theory is a submodel of $\langle\text{HF}^M,{\in^M}\rangle$.

Theorem.(JDH) Every countable model of set theory is isomorphic to a submodel of any nonstandard model of finite set theory. Indeed, every nonstandard model of finite set theory is universal for all countable acyclic binary relations.

The proof involves the construction of what I call the countable random $\mathbb{Q}$-graded digraph, a countable homogeneous acyclic digraph that is universal for all countable acyclic digraphs, and proving that it is realized as a submodel of the nonstandard model $\langle M,\in^M\rangle$. Having then realized a universal object as a submodel, it follows that every countable structure with an acyclic binary relation, including every countable model of ZFC, is realized as a submodel of $M$.

The proof, in brief:  for every countable acyclic digraph, consider the partial order induced by the edge relation, and extend this order to a total order, which may be embedded in the rational order $\mathbb{Q}$.  Thus, every countable acyclic digraph admits a $\mathbb{Q}$-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed $\mathbb{Q}$-graded digraph, simply by starting with nothing, and then adding finitely many nodes at each stage, so as to realize the finite pattern property. The result is a computable presentation of what I call the countable random $\mathbb{Q}$-graded digraph $\Gamma$.  If $M$ is any nonstandard model of finite set theory, then we may run this computable construction inside $M$ for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of $\Gamma$.  Furthermore, since $M$ thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of $M$.  By looking at the sets corresponding to the nodes in the copy of $\Gamma$, we find a submodel of $M$ that is isomorphic to $\Gamma$, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of $M$.

The proof idea adapts, with complications, to the case of well-founded models, via the countable random $\lambda$-graded digraph, as well as the internal construction of what I call the hypnagogic digraph, a proper class homogeneous surreal-numbers-graded digraph, which is universal for all class acyclic digraphs.

Theorem.(JDH) Every countable model $\langle M,\in^M\rangle$ of ZFC, including the transitive models, is isomorphic to a submodel of its own constructible universe $\langle L^M,\in^M\rangle$. In other words, there is an embedding $j:M\to L^M$ that is quantifier-free-elementary.

The proof is guided by the idea of finding a universal submodel inside $L^M$. The embedding $j$ is constructed completely externally to $M$.

Corollary.(JDH) The countable models of ZFC are linearly ordered and even well-ordered, up to isomorphism, by the submodel relation. Namely, any two countable models of ZFC with the same well-founded height are bi-embeddable as submodels of each other, and all models embed into any nonstandard model.

The work opens up numerous questions on the extent to which we may expect in ZFC that $V$ might be isomorphic to a subclass of $L$. To what extent can we expect to have or to refute embeddings $j:V\to L$, elementary for quantifier-free assertions?

Article | CUNY Logic Workshop