Comparing countable models of ZFC

Let us consider the class $\cal C$ of countable models of ZFC. For ${\mathfrak A}=(A,{\in}_A)$ and ${\mathfrak B}=(B,{\in}_B)$ in $\cal C$ I say that ${\mathfrak A}<{\mathfrak B}$ iff there is a injective map $i: A \to B$ such that $x {\in}_A y \Leftrightarrow i(x) {\in}_B i(y)$ (note that this is a much weaker requirement for $i$ than to be an elementary embedding). My two questions are :

(1) Is there a simple construction of two incomparable models ${\mathfrak A},{\mathfrak B}$ ? (i.e. neither ${\mathfrak A}<{\mathfrak B}$ nor ${\mathfrak B}<{\mathfrak A}$).

(2) Given two models ${\mathfrak A},{\mathfrak B}$ in $\cal C$, is there always a third model ${\mathfrak C}$ in $\cal C$ such that ${\mathfrak A}<{\mathfrak C}$ and ${\mathfrak B}<{\mathfrak C}$ ?

Solution 1:

Concerning question (1).

I became very interested in this question last year---obsessed with it, actually---when I found myself unable to prove that any of the natural-seeming examples were actually instances of incomparability (for example, none of the approaches suggested in the various comments actually work). After my numerous attacks on it failed, I began seriously to doubt the strong intuition underlying the question, that there should be incomparable models. Eventually, I was a able to show that indeed, any two countable models are comparable by embeddability. My paper is available at:

• J. D. Hamkins, "Every countable model of set theory embeds into its own constructible universe", also at the math arχiv.

The main theorems are:

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$. Thus, 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.

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, which answers question (1). Version 2 on the archive, which will become visible in a few days, cites this question and Ewan Delanoy.

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 embedability 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.

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 article closes with a number of questions, which you may find on my blog post about the article. I plan to make some mathoverflow questions about them in the near future.

Solution 2:

(2) seems true. Choose models with universes $\lbrace m_j\vert j<\omega\rbrace$, $\lbrace n_j\vert j<\omega\rbrace$ Consider language $L=\lbrace \in, a_i,b_i\vert i<\omega\rbrace$, and the theory $T=ZFC\cup\lbrace a_i\neq a_j\vert i,j\in\omega, m_i\neq m_j\rbrace\cup \lbrace a_i\in a_j\vert i,j\in\omega, m_i\in^{M_1} m_j\rbrace \cup \ldots$

It is clear that if $T$ is consistent, we can obtain the countable model in which $M_1,M_2$ embed monomorphically by downward Skolem.

Choose a finite fragment of $T$. The formulas of $T$ don't relate $a$ and $b$ in any way, so it is effectively a fragment of ZFC plus two finite (well-founded and consistent) membership+non-membership graphs. But any such graph can be realized by a finite set in any model of ZFC, so by compactness $T$ is consistent.

For (1) i think you can try to look at models which realize different subtrees of the Cantor tree (as subgraphs of their membership graphs). For example, one of them could have infinite descending sequence and other might not. It should be doable by omitting types theorem.