SATURATED MODELS FOR THE WORKING MODEL THEORIST

Abstract

We put in print a classical result that states that for most purposes, there is no harm in assuming the existence of saturated models in model theory. The presentation is aimed for model theorists with only basic knowledge of axiomatic set theory.

1 Introduction

Stop a random model theorist on the street and ask him “are saturated models important/useful?” and his answer will most likely be a strong yes. Nonetheless, the existence of such models (outside the realm of stable theories) will cause some model theorists to move awkwardly in their seats, fearing some set-theoretical obstacles. The purpose of this note is to alleviate these concerns.

There are several standard workarounds. One is, instead of full saturation, work in some $\kappa $ -saturated and $\kappa $ -strongly homogeneous model for some large enough cardinal $\kappa $ . Another is to consider an increasing chain of highly saturated models, i.e., special models and work there instead (see, e.g., [4, Section 10.4]). In fact, [4, Chapter 10] lists some other workarounds, e.g., resplendent models, recursively saturated models, and big models. A third option is to allow your saturated model to be a class instead of a set and work in some suitable conservative expansion of ZFC (see, e.g., [8, Appendix A]).

However, we find these workarounds cumbersome, as working with bona fide saturated models (as monster models or for checking the completeness of a theory, etc.) is more natural and seamless. Moreover, working with these alternatives may involve more technical issues. There are set theoretic techniques that allow us to work with saturated models and bypass these obstacles.

One such technique is to force the continuum hypothesis to hold at some large enough cardinal. Then, after realizing that the statement you wanted to prove was in fact absolute, conclude that it holds in your original model of ZFC as well. Forcing uses some heavy machinery from set theory, and, although this argument is sound, it may deter some model theorists.

In this short note we give a different argument, whose advantage is that it uses relatively elementary set theory (e.g., no forcing). It is certainly not new nor original: it is standard in axiomatic set theory and is known by many model theorists as well. However, we believe it has never been written down with model theorists in mind.

This approach relies on the simple observation that if in the statement one wishes to prove, i.e., a formula $\varphi $ in the language of sets, all quantifiers are bounded, then one can assume an abundance of saturated models.

More explicitly, let $\mathbb {V}$ be a model of ZFC and for an ordinal $\gamma $ , let $V_{\gamma }$ be the $\gamma $ th stage of the von Neumann hierarchy (all notions will be defined in Section 2).

Theorem (Corollary 2.5).

For any ordinal $\gamma $ there exists an inner model M satisfying:

1. (1) For some ordinal $\alpha _0$ , for every $\alpha \geq \alpha _0$ , $M\vDash 2^{\aleph _{\alpha }}=\aleph _{\alpha +1}$ .

2. (2) For any formula $\varphi $ with parameters in the language of set theory, with parameters and quantifiers bounded by elements of $V_{\gamma }$ ,

   $$\begin{align*}\mathbb{V}\vDash \varphi\iff M\vDash \varphi. \end{align*}$$

In particular, in M there are arbitrarily large saturated models for any first-order theory.

In Section 2 we give the necessary background from set theory and prove the existence of such inner models. In Section 3 we give some model theoretic examples and applications.

2 Set theory

We assume basic set theory, such as ordinals, cardinals, and the axioms of ZFC. Almost all references will be from Jech’s “Set Theory” [6].

We work in some model $(\mathbb {V},\in )$ of ZFC. All sets are elements of $\mathbb {V}$ and definable sets are classes. Every set is identified with the class of its members, and a class which cannot be identified with a set is called a proper class. We let $\operatorname {\mathrm {\mathbf {Ord}}}$ denote the class of all ordinals (recall that $\mathord {\in } \restriction \operatorname {\mathrm {\mathbf {Ord}}}^2$ is also denoted by $<$ , it is a well-order); it is a proper class.

The universe $\mathbb {V}$ can be partitioned by the so-called von Neumann hierarchy of sets: $V_0=\emptyset $ , for every $\beta \in \operatorname {\mathrm {\mathbf {Ord}}}$ if $\beta $ is a limit ordinal $V_{\beta }=\bigcup _{\alpha <\beta } V_{\alpha }$ and if $\beta =\alpha +1$ then $V_{\beta }=P(V_{\alpha })$ . Each $V_{\alpha }$ is a set, but $\mathbb {V}$ itself is a proper class. In fact, it follows from the axioms that $\mathbb {V}=\bigcup _{\alpha \in \operatorname {\mathrm {\mathbf {Ord}}}} V_{\alpha }$ .

An inner model of ZFC is a class M such that $(M,\mathord {\in })\vDash \text {ZFC}$ , M is transitive ( $x \in y \in M$ implies $x\in M$ ), and M contains all ordinals.

An important family of inner models are the universes of sets constructible relative to a set: for any set A, we let

$$\begin{align*}L_0[A]=\emptyset,\, L_{\beta}=\bigcup_{\alpha<\beta} L_{\beta}[A] \text{ if } \beta \text{ is a limit ordinal and} \end{align*}$$

$$\begin{align*}L_{\beta+1}[A]=\{X\subseteq L_{\beta}[A]: X \text{ is definable in } (L_{\beta}[A],\mathord{\in}, A\cap L_{\beta}[A])\}, \end{align*}$$

$$\begin{align*}\mathbb{L} [A]=\bigcup_{\beta\in \operatorname{\mathrm{\mathbf{Ord}}}}L_{\beta}[A], \end{align*}$$

where $(L_{\beta }[A],\in , A\cap L_{\beta }[A])$ is the structure $(L_{\beta }[A],\in )$ with a predicate for $A\cap L_{\beta }[A]$ . Each $L_{\beta }[A]$ is a set, but $\mathbb {L}[A]$ itself is a proper class. It is an inner model of ZFC and it satisfies the continuum hypothesis for large enough cardinals, i.e., there exists $\alpha _0$ such that for all $\alpha \geq \alpha _0$ , $\mathbb {L} [A]\vDash 2^{\aleph _{\alpha }}=\aleph _{\alpha +1}$ , see [6, Theorem 13.22] and [2, p. 103, 2B] for more.

The last tool we will need is the following:

Fact 2.1 (Mostowski’s collapse).

[6, Theorem 6.15] Assume that P is a class and E is a binary relation on P satisfying:

1. (1) E is well-founded:

   1. (a) Any nonempty set $x\subseteq P$ , has an E-minimal element: an element $z\in x$ such that for no $y \in x$ is it the case that $y \mathrel {E} z$ .

   2. (b) For any $x\in P$ , $\{z\in P: z\mathrel {E} x\}$ is a set.

2. (2) For any distinct $x,y \in P$ , $\{z\in P: z\mathrel {E} x\}\neq \{z\in P: z\mathrel {E} y\}$ .

Then there is a transitive class N and an isomorphism $\pi $ between $(P,E)$ and $(N,\in )$ . Moreover, N and $\pi $ are unique.

By the axioms of ZFC, applying Mostowski’s collapse to a set produces a transitive set.

Theorem 2.2. For any ordinal $\gamma $ there exists an inner model $M\vDash $ ZFC satisfying:

1. (1) $V_{\gamma }\in M$ .

2. (2) There exists $\alpha _0$ such that for all $\alpha \geq \alpha _0$ , $M\vDash 2^{\aleph _{\alpha }}=\aleph _{\alpha +1}$ .

Remark 2.3. By [6, Theorem 13.27.i], $V_{\alpha }^M=V_{\alpha }$ for any $\alpha \leq \gamma $ , where $V_{\alpha }^M$ is the $\alpha $ th stage of the hierarchy as defined in M.

Proof Let $f:\mu \to V_{\gamma }$ be a bijection between $V_{\gamma }$ and some cardinal $\mu $ and let $R=f^{-1}(\mathord {\in }\restriction V_{\gamma }^2)\subseteq \mu \times \mu $ . Note that R is a set (as a subclass of a set).

Let $M=\mathbb {L}[R]$ be the constructible universe relative to R. It is an inner model of ZFC and satisfies (2), so we need to show that it satisfies (1) as well.

Since M is an inner model, not only $\mu \in M$ but also $\mu \times \mu \in M$ . Note that the construction of the product $\mu \times \mu $ is exactly the same in M and in $\mathbb {V}$ . Assume that $\mu \times \mu \in L_{\beta }[R]$ for some $\beta \in \operatorname {\mathrm {\mathbf {Ord}}}$ . By transitivity $R\subseteq L_{\beta }[R]$ , which means, by definition, that $R\in L_{\beta +1}[R]\subseteq M$ .

Consider the structure $(\mu ,R)$ . It clearly satisfies the requirements of Mostowski’s collapse in $\mathbb {V}$ since $f(R)=\mathord {\in }$ , and hence also in M (by transitivity). By uniqueness, in $\mathbb {V}$ , the collapse is witnessed by $V_{\gamma }$ and f.

Applying Mostowski’s collapse in M, we get a pair $\pi $ and $(N,\in )$ . By transitivity, $\pi $ is an isomorphism from $(\mu ,R)$ to $(N,\in )$ also in $\mathbb {V}$ . Uniqueness (in $\mathbb {V}$ ) implies that $\pi =f$ and $N=V_{\gamma }$ , guaranteeing that $V_{\gamma }\in M$ .

Definition 2.4. For an ordinal $\gamma $ , a formula over $V_{\gamma }$ is bounded by $V_{\gamma }$ (or $V_{\gamma }$ -bounded) if all its quantifiers are of the form $(\operatorname {Q} x\in a)$ where $\operatorname {Q} \in \{\forall ,\exists \}$ and $a\in V_{\gamma }$ .

Corollary 2.5. For any ordinal $\gamma $ there exists an inner model $M\vDash $ ZFC such that $V_{\gamma }\in M$ and:

1. (1) There exists $\alpha _0$ such that for all $\alpha \geq \alpha _0$ , $M\vDash 2^{\aleph _{\alpha }}=\aleph _{\alpha +1}$ .

2. (2) For any $V_{\gamma }$ -bounded formula $\varphi $ , $\mathbb {V}\vDash \varphi $ if and only if $M\vDash \varphi $ .

In particular, in M there are arbitrarily large saturated models for any first-order theory.

Proof Follows from Theorem 2.2 since M and $V_{\gamma }$ are transitive: $\mathbb {V}\vDash \varphi $ if and only if $V_{\gamma } \vDash \varphi $ if and only if $M\vDash \varphi $ . (These equivalences follow from an easy inductive argument, this is absoluteness for bounded formulas [6, Lemma 12.9].)

The existence of saturated models follows by, e.g., [8, Lemma 6.1.2].

3 Model theory

The aim of this section is to give some examples of applications of Corollary 2.5 to “real-life” model-theoretic statements. One can summarize it in one slogan:

If the statement you wish to prove is equivalent to a $V_{\gamma }$ -bounded formula (with parameters) in any inner model containing $V_{\gamma }$ then you may assume that you have arbitrarily large saturated models.

Remark 3.1.

1. (1) The point that the equivalence is with respect to any inner model containing $V_{\gamma }$ is crucial because of the reflection principle (see [6, Theorem 12.14]) which says that for every formula with parameters $\varphi $ there is an ordinal $\gamma $ and a $V_{\gamma }$ -bounded formula $\psi $ such that $\mathbb {V}\vDash \varphi \leftrightarrow \psi $ (see [6, Theorem 12.14]).

2. (2) Assuming large cardinals, there are models of ZFC in which, e.g., $\operatorname {\mathrm {Th}}(\mathbb {Q},<)$ has no uncountable saturated models, see the non-example below.

Many theorems in model theory fall into this category, and hence we may assume the existence of saturated models, and do not have to worry about the existence of monster models. We give two examples and one non-example.

3.1 Completeness

One way to show that a theory T in a language $\mathcal {L}$ is complete is by showing that any two saturated models of the same cardinality are isomorphic (assuming one exists).

We can easily write down a formula in the language of set theory saying that the theory T is complete. Pick an ordinal $\gamma $ large enough such that $V_{\gamma }$ contains, among other things, T, $\mathcal {L}$ , the set of all $\mathcal {L}$ -formulas and the set of all finite sequences of formulas (and in particular all deductions). Clearly the formula “T is complete” is equivalent to a $V_{\gamma }$ -bounded formula (and this remains true in any inner model containing $V_{\gamma }$ ). By Corollary 2.5, in order to prove that T is complete we may assume that we have a saturated model for T.

Another approach to writing “T is complete” in a formula is: for any model $M\vDash T$ whose universe is the cardinal $|T|$ if $M\vDash \phi $ then $\phi \in T$ . This is also easily seen to be a $V_{\gamma }$ -bounded for some $\gamma $ .

As a consequence, when showing quantifier elimination (i.e., substructure completeness) and model completeness one may assume the existence of saturated models.

3.2 Stably embedded definable sets

Let T be a theory. Recall the definition of a stably embedded definable set (see, e.g., [1, Appendix]): a formula $\xi (x)$ is stably embedded if for any formula $\varphi (x,y)$ there exists a formula $\psi (x,y)$ such that for any y-tuple b there exists a z-tuple d satisfying $\xi $ such $\forall x (\xi (x)\to (\varphi (x,b)\leftrightarrow \psi (x,d)))$ . Again, we can easily express this as a formula in the language of set theory with $V_{\gamma }$ -bounded quantifiers for some sufficiently large $\gamma $ .

If $M\vDash T$ is saturated then by [1, Lemma 1 and Appendix], a definable set $\xi (M)$ is stably embedded if and only if every automorphism of $\xi (M)$ (with the induced structure) extends to an automorphism of M. This is often a very convenient criterion to check.

For example, assume that D is stably embedded set in some saturated L-structure M, let P be a new predicate for a subset of D, and let $M_P$ be the expanded structure (in the language $L_P$ ). Then D is still stably embedded in $M_P$ . This can be proved quite easily using the automorphism argument above: Let $\sigma $ be an $L_P$ -automorphism of D. As $\sigma $ is also an L-automorphism it lifts to an automorphism of M; but now clearly it is also an automorphism of $M_P$ . This result can also be proved by syntactical means (see, e.g., [5, Proof of Proposition 2.5]).

3.3 Non-example

Assuming large cardinals, there is a model of ZFC and a theory T for which there is no ordinal $\gamma $ such that the statement “T has an uncountable saturated model” is equivalent to a $V_{\gamma }$ -bounded formula in all inner models.

Indeed, by [3], there are models of ZFC in which the generalized continuum hypothesis fails for every cardinal (assuming a supercompact cardinal). By restricting to $V_{\kappa }$ where $\kappa $ is the smallest inaccessible cardinal, we may assume that there are no inaccessible cardinals as well (see [6, Lemma 12.13]). In such a model, any non-stable theory T will not have any uncountable saturated models: if T had an uncountable saturated model of size $\lambda $ , then by [7, Theorem VIII.4.7], $\lambda =\lambda ^{<\lambda }$ , and hence $\lambda $ is regular. As $\lambda $ is uncountable and not inaccessible, it is a successor $\mu ^+$ . Together, we get $2^{\mu } \leq \lambda ^{\mu } = \lambda = \mu ^+ \leq 2^{\mu }$ , a contradiction. Consequently, if there was a $\gamma $ such that “T has an uncountable saturated model” is equivalent to a $V_{\gamma }$ -bounded formula (in all inner models) it would contradict Corollary 2.5.