[bibtex key=Hamkins2013:EveryCountableModelOfSetTheoryEmbedsIntoItsOwnL]

In this article, I prove that every countable model of set theory ⟨𝑀, ∈𝑀⟩, including every well-founded model, is isomorphic to a submodel of its own constructible universe ⟨𝐿𝑀, ∈𝑀⟩. Another way to say this is that there is an embedding
𝑗:⟨𝑀,∈𝑀⟩→⟨𝐿𝑀,∈𝑀⟩
that is elementary for quantifier-free assertions in the language of set theory.

Main Theorem 1. Every countable model of set theory ⟨𝑀, ∈𝑀⟩ is isomorphic to a submodel of its own constructible universe ⟨𝐿𝑀, ∈𝑀⟩.

The proof uses universal digraph combinatorics, including an acyclic version of the countable random digraph, which I call the countable random ℚ-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 ⟨𝐿𝑀, ∈𝑀⟩ contains a submodel that is a universal acyclic digraph of rank Ord𝑀, and so in fact this model is universal for all countable acyclic binary relations of this rank. When 𝑀 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 ⟨𝑀, ∈𝑀⟩ and ⟨𝑁, ∈𝑁⟩, either 𝑀 is isomorphic to a submodel of 𝑁 or conversely. Indeed, the countable models of set theory are pre-well-ordered by embeddability in order type exactly 𝜔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 HF𝑀 coded in any nonstandard model 𝑀 of PA or even of 𝐼⁢Δ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 𝑀 is any nonstandard model of PA, then every countable model of set theory is isomorphic to a submodel of the hereditarily finite sets ⟨HF𝑀, ∈𝑀⟩ of 𝑀. Indeed, ⟨HF𝑀, ∈𝑀⟩ 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 ⟨HF𝑀, ∈𝑀⟩. 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 ℚ.  Thus, every countable acyclic digraph admits a ℚ-grading, an assignmment of rational numbers to nodes such that all edges point upwards. Next, one can build a countable homogeneous, universal, existentially closed ℚ-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 ℚ-graded digraph Γ.  If 𝑀 is any nonstandard model of finite set theory, then we may run this computable construction inside 𝑀 for a nonstandard number of steps.  The standard part of this nonstandard finite graph includes a copy of Γ.  Furthermore, since 𝑀 thinks it is finite and acyclic, it can perform a modified Mostowski collapse to realize the graph in the hereditary finite sets of 𝑀.  By looking at the sets corresponding to the nodes in the copy of Γ, we find a submodel of 𝑀 that is isomorphic to Γ, which is universal for all countable acyclic binary relations. So every model of ZFC isomorphic to a submodel of 𝑀.

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 𝑗 :𝑉 →𝐿 from the set-theoretic universe 𝑉 to the constructible universe 𝐿, when 𝑉 ≠𝐿?) Although the main theorem shows that every countable model of set theory embeds into its own constructible universe  𝑗:𝑀→𝐿𝑀, this embedding 𝑗 is constructed completely externally to 𝑀 and there is little reason to expect that 𝑗 could be a class in 𝑀 or otherwise amenable to 𝑀.  To what extent can we prove or refute the possibility that 𝑗 is a class in 𝑀? This amounts to considering the matter internally as a question about 𝑉. Surely it would seem strange to have a class embedding 𝑗 :𝑉 →𝐿 when 𝑉 ≠𝐿, 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 𝐿 back into 𝑉.

Question 1.  Can there be an embedding 𝑗 :𝑉 →𝐿 when 𝑉 ≠𝐿?

By embedding, I mean an isomorphism from ⟨𝑉, ∈⟩ to its range in ⟨𝐿, ∈⟩, which is the same as a quantifier-free-elementary map 𝑗 :𝑉 →𝐿. The question is most naturally formalized in Gödel-Bernays set theory, asking whether there can be a GB-class 𝑗 forming such an embedding.  If one wants 𝑗 :𝑉 →𝐿 to be a definable class, then this of course implies 𝑉 =HOD, since the definable 𝐿-order can be pulled back to 𝑉, via 𝑥 ≤𝑦 ⟺ 𝑗⁡(𝑠) ≤𝐿𝑗⁡(𝑦). More generally, if 𝑗 is merely a class in Gödel-Bernays set theory, then the existence of an embedding 𝑗 :𝑉 →𝐿 implies global choice, since from the class 𝑗 we can pull back the 𝐿-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♯ 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 𝑉 further away from 𝐿. For example, it is conceivable that the existence of 0♯ will enable one to construct the embedding, using the Silver indiscernibles to find a universal submodel of 𝐿; but it is also conceivable that the non-existence of 0♯, because of covering and the corresponding essential closeness of 𝑉 to 𝐿, may make it easier for such a 𝑗 to exist. Or perhaps it is simply refutable in any case. The first-order analogue of the question is:

Question 2.  Does every set 𝐴 admit an embedding 𝑗 :⟨𝐴, ∈⟩ →⟨𝐿, ∈⟩?  If not, which sets do admit such embeddings?

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

Question 3. Does ⟨𝑉𝜔+1, ∈⟩ embed into ⟨𝐿, ∈⟩? How about ⟨𝑃⁡(𝜔), ∈⟩ or ⟨HC, ∈⟩?

It is also natural to inquire about the nature of 𝑗 :𝑀 →𝐿𝑀 even when it is not a class in 𝑀. For example, can one find such an embedding for which 𝑗⁡(𝛼) is an ordinal whenever 𝛼 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 ⟨𝑀, ∈𝑀⟩ of set theory admit an embedding 𝑗 :𝑀 →𝐿𝑀 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 𝑗 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 𝑗 :𝑉 →𝐿, as in question , if that should be possible.

Question 5. Can there be a nontrivial embedding 𝑗 :𝑉 →𝐿 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 𝜔1-like models:

Question 6. Does every 𝜔1-like model of set theory ⟨𝑀, ∈𝑀⟩ admit an embedding 𝑗 :𝑀 →𝐿𝑀 into its own constructible universe? Are the 𝜔1-like models of set theory linearly pre-ordered by embeddability?