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,” Journal of mathematical logic, vol. 13, iss. 2, p. 1350006, 2013.  
    @ARTICLE{Hamkins:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL,
    author = {Joel David Hamkins},
    title = {Every countable model of set theory embeds into its own constructible universe},
    journal = {Journal of Mathematical Logic},
    year = {2013},
    volume = {13},
    number = {2},
    pages = {1350006},
    month = {},
    note = {},
    abstract = {},
    keywords = {},
    source = {},
    doi = {10.1142/S0219061313500062},
    eprint = {1207.0963},
    URL = {http://www.worldscientific.com/doi/abs/10.1142/S0219061313500062},
    }

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?

12 thoughts on “Every countable model of set theory embeds into its own constructible universe

  1. Pingback: Every countable model of set theory embeds into its own constructible universe, Fields Institute, Toronto, August 2012 | Joel David Hamkins

  2. Considering Conway’s system ‘No’ and Philip Ehrlich’s assertion that ‘No’ is an “absolute arithmetic continuum” containing “all numbers great and small”, could ‘No’ act as a foundation (so to speak) of the naturalistic account of forcing?

    • Thomas, I don’t quite follow your suggestion. I believe that Ehrlich is using the word “absolute” in a way that recall’s Cantor’s term of “absolute infinity”, which is often understood to refer to the class of all ordinals. But the truth remains that different models of set theory have different non-isomorphic surreals, and so No is not absolute in that sense. For example, forcing creates new surreal numbers. Indeed, for models V and W of ZFC, I claim that V is isomorphic to W if and only if No^V is isomorphic to No^W, and in this sense, the surreals of a model of ZFC capture the whole model. This is because the surreal numbers correspond to the transfinite binary sequences, which in turn corresponds to a set of ordinals, and two models of ZFC set theory with the same ordinals and the same sets of ordinals are the same.

  3. I will quote Ehrlich (quote found on page 240) from his paper “The Absolute Arithmetic Continuum and Its Peircean Counterpart”, “No not only exhibits [the rest of the sentence is italicized for emphasis] all possible types of algebraic and set-theoretically [the word ‘set’ is underlined for further emphasis] defined order -theoretic gradations consistent with its structure as an ordered field, it is to within isomorphism the unique structure that does.” I leave it to you to make of that what you will. Another (at least to me) telling remark of Ehrlich’s can be found in another article “Universally extending Arithmetic Continua” where he entitles the section in which he defines the term “absolutely homogeneous universal” for a model ‘A’ “Maximal Models”. I would be interested in seeing how forcing creates new surreal numbers since Conway ‘constructs’ No from the notation {L|R} which seems to me at least independent of any axiomatization of set theory

    • Forcing can create new real numbers, and therefore also new surreal numbers. So different models of set theory can have different surreal numbers. (This is clear already from the fact that different models of set theory can have different ordinals.) The argument I gave in my comment above shows more: different models of ZFC necessarily have different No’s, since the surreal numbers code up the entire universe in which they are constructed. So the surreal numbers No are not absolute in the sense of being-the-same-in-all-models. What Ehrlich is talking about is the fact that we can prove in ZFC that No is the unique homogeneous and universal class linear order. This can be viewed in analogy with Cantor’s proof that the rational line $\mathbb{Q}$ is the unique homogeneous universal countable linear order.

      • Would the fact that in ZFC (though Ehrlich speaks of No as the absolute arithmetic continuum “modulo NBG” or by extension, modulo Ackermann Set Theory) No is the unique homogeneous and universal class linear order be sufficient to use it as the basis for generating, say, Cohen and/or Random reals to affix to models of set theory, therefore liberating forcing from countable, ‘toy’ models (since at least as I understand it, forcing needed to use countable models so that the extra sets of natural numbers not contained in the model in question could act as generic sets)? In fact does No contain all possible interpretations of No relative to models of ZFC?

        • The referece to NGB is due to two facts, first, the class universality claim is explicitly a second-order claim, which is not expressible except case-by-case in the first-order language; and second, one proves that No is universal for class linear orders in NGB, and the proof I know uses the global choice principle (which goes beyond ZFC) in order to guide the back-and-forth argument to find the embedding of a given class order into No. I don’t really see how to use No in the way that you suggest. The No of one model will not generally be universal for the linear orders that exist in another model of set theory.

  4. Pingback: 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 | Joel David Hamkins

  5. Pingback: Every countable model of set theory is isomorphic to a submodel of its own constructible universe, Barcelona, December, 2012 | Joel David Hamkins

  6. Pingback: A multiverse perspective on the axiom of constructiblity | Joel David Hamkins

  7. Pingback: The countable models of set theory are linearly pre-ordered by embeddability, Rutgers, November 2012 | Joel David Hamkins

  8. Pingback: Embeddability amongst the countable models of set theory, plenary talk for ASL / Joint Math Meetings in Baltimore, January 2014 | Joel David Hamkins

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>