Incomparable $\omega_1$-like models of set theory

PDF   Bibtex   Arχiv

G. Fuchs, V. Gitman, and J. D. Hamkins, “Incomparable $\omega_1$-like models of set theory,” MLQ Math. Log. Q., vol. 63, no. 1-2, pp. 66–76, 2017.

We should like to consider the question of whether the embedding theorems of Hamkins [1], recently proved for the countable models of set theory, might extend to the realm of uncountable models. Specifically, Hamkins proved that (1) any two countable models of set theory are comparable by embeddability; indeed, (2) one countable model of set theory embeds into another just in case the ordinals of the first order-embed into the ordinals of the second; consequently, (3) every countable model of set theory embeds into its own constructible universe; and furthermore, (4) every countable model of set theory embeds into the hereditarily finite sets $\langle{\rm HF},\in\rangle^M$ of any nonstandard model of arithmetic $M\models{\rm PA}$. The question we consider here is, do the analogous results hold for uncountable models? Our answer is that they do not. Indeed, we shall prove that the corresponding statements do not hold even in the special case of $\omega_1$-like models of set theory, which otherwise among uncountable models often exhibit a special affinity with the countable models. Specifically, we shall construct large families of pairwise incomparable $\omega_1$-like models of set theory, even though they all have the same ordinals; we shall construct $\omega_1$-like models of set theory that do not embed into their own $L$; and we shall construct $\omega_1$-like models of ${\rm PA}$ that are not universal for all $\omega_1$-like models of set theory.

An embedding of one model $\langle M,\in^M\rangle$ of set theory into another $\langle N,{\in^N}\rangle$ is simply a function $j:M\to N$ for which $x\in^M y\longleftrightarrow j(x)\in^N j(y)$, for all $x,y\in M$. Note that we don't require injectivity because it follows from extensionality. Thus, an embedding is simply an isomorphism of $\langle M,\in^M\rangle$ with its range, which is a submodel of $\langle N,\in^N\rangle$. fig Although this is the usual model-theoretic embedding concept for relational structures, the reader should note that it is a considerably weaker embedding concept than commonly encountered in set theory, because this kind of embedding need not be elementary nor even $\Delta_0$-elementary, although clearly every embedding as just defined is elementary at least for quantifier-free assertions. One can begin to get an appreciation for the difference in embedding concepts by observing that ${\rm ZFC}$ proves that there is a nontrivial embedding $j:V\to V$, namely, the embedding recursively defined as follows $$j(y)=\bigl\{\ j(x)\ \mid\ x\in y\ \bigr\}\cup\bigl\{\{\emptyset,y\}\bigr\}.$$ (This is because every $j(y)$ is nonempty and also $\emptyset\notin j(y)$; it follows that inside $j(y)$ we may identify the pair $\{\emptyset,y\}\in j(y)$. Using this, we argue that the only way to have $j(x)\in j(y)$ is from $x\in y$.) Contrast this situation with the well-known Kunen inconsistency [bibcite key=kunen:inconsistency], which asserts that there can be no nontrivial $\Sigma_1$-elementary embedding $j:V\to V$. Similarly, the same recursive definition applied in $L$ leads to nontrivial embeddings $j:L\to L$, regardless of whether $0^\sharp$ exists. But again, the point is that embeddings are not necessarily even $\Delta_0$-elementary, and the familiar equivalence of the existence of $0^\sharp$ with a nontrivial "embedding" $j:L\to L$ actually requires a $\Delta_0$-elementary embedding.

We find it interesting to note in contrast to Hamkins' embedding theorems that there is no such embedding phenomenon in the the context of the countable models of Peano arithmetic (where an embedding of models of arithmetic is a function preserving all atomic formulas in the language of arithmetic). Perhaps the main reason for this is that embeddings between models of ${\rm PA}$ are automatically $\Delta_0$-elementary, as a consequence of the MRDP theorem (every $\Sigma_1$-formula is equivalent to a formula with a single existential quantifier, which famously shows that a set is Diaphantine if and only if it is computably enumerable), whereas this is not true for models of set theory, as the example above of the recursively defined embedding $j:V\to V$ shows, since this is an embedding, but it is not $\Delta_0$-elementary, in light of $j(\emptyset)\neq\emptyset$. For countable models of arithmetic $M,N\models{\rm PA}$, one can show that there is an embedding $j:M\to N$ if and only if $N$ satisfies the $\Sigma_1$-theory of $M$ and the standard system of $M$ is contained in the standard system of $N$. It follows that there are many instances of incomparability.

Main Theorems:

  1. If $\diamondsuit$ holds and ${\rm ZFC}$ is consistent, then there is a family $\mathcal C$ of $2^{\omega_1}$ many pairwise incomparable $\omega_1$-like models of ${\rm ZFC}$, meaning that there is no embedding between any two distinct models in $\mathcal C$.
  2. The models in statement (1) can be constructed so that their ordinals order-embed into each other and indeed, so that the ordinals of each model is a universal $\omega_1$-like linear order. If ${\rm ZFC}$ has an $\omega$-model, then the models of statement (1) can be constructed so as to have precisely the same ordinals.
  3. If $\diamondsuit$ holds and ${\rm ZFC}$ is consistent, then there is an $\omega_1$-like model $M\models{\rm ZFC}$ and an $\omega_1$-like model $N\models{\rm PA}$ such that $M$ does not embed into $\langle{\rm HF},\in\rangle^N$.
  4. If there is a Mahlo cardinal, then in a forcing extension of $L$, there is a transitive $\omega_1$-like model $M\models{\rm ZFC}$ that does not embed into its own constructible universe $L^M$.

References

  1. J. D. Hamkins, “Every countable model of set theory embeds into its own constructible universe,” J. Math. Log., vol. 13, no. 2, pp. 1350006, 27, 2013.