In this article, "type" will by default mean "complete type," rather than "partial type." Also, types will be finitary (n-types) rather than finitary, by default.
Roughly speaking, a structure is saturated if all types over it are realized. This is practically impossible, so instead we only consider types over small sets. If $ \kappa $ is an infinite cardinal, a structure M is said to be $ \kappa $-saturated if every type over a subset A ⊆ M with $ |A| \le \kappa $ is realized in M. It turns out that an equivalent condition is that every 1-type over a subset of size less than $ \kappa $ is realized.
The structure M is said to be saturated if it is |M|-saturated: every type over a subset of smaller cardinality than M is realized.
A closely related concept is strong homogeneity. A structure M is said to be $ \kappa $-strongly homogeneous if whenever a and b are possibly infinite tuples from M having the same type over the empty set Ø, and a and b have length less than $ \kappa $, then some automorphism $ \sigma $ of M sends a to b. Equivalently, every partial elementary map on M of size less than $ \kappa $ can be extended to an automorphism of M. Warning: Some authors use the term "$ \kappa $-homogeneous" rather than "$ \kappa $-strongly homogeneous."
In stability theory, one frequently works with a "monster model", by which one means a $ \kappa $-saturated and $ \kappa $-strongly homogeneous model of the theory for some cardinal $ \kappa $ much bigger than any cardinals we expect to run into.
Saturation as a kind of CompactnessEdit
Saturation can be viewed as an analogue of compactness:
Theorem: Let M be $ \kappa $-saturated. Let D be some definable subset of M (or of a power of M). Let $ \{E_i\}_{i \in I} $ be some infinite family of definable sets, with
- $ D \subseteq \bigcup_{i \in I} E_i $
If the family has size less than $ \kappa $, i.e., if $ |I| < \kappa $, then D is covered by some finite collection of the E_{i}'s.
Proof: Let $ \Sigma(x) $ be the partial type over M asserting that x is in D but in none of the $ E_i $'s. Then $ \Sigma(x) $ consists of fewer than $ \kappa $ formulas, so it is a partial type over a subset $ A \subseteq M $ with $ |A| < \kappa $. If $ \Sigma(x) $ is inconsistent, then it is finitely inconsistent. Therefore there exists $ i_1, \ldots, i_n $ such that
- $ M \models \forall x : (x \in D) \rightarrow \left( \bigvee_{j = 1}^n x \in E_{i_j} \right) $
or equivalently
- $ D \subseteq \bigcup_{j = 1}^n E_{i_j} $. Then we are done.
Otherwise, $ \Sigma(x) $ is consistent. Let p(x) be a complete type over A extending $ \Sigma(x) $. By saturation, p(x) is realized in M, hence so is $ \Sigma(x) $. But a realization of $ \Sigma(x) $ is a point which is in D but in no E_{i}, contradicting the hypotheses.
QED.
Existence of saturated and strongly homogeneous modelsEdit
A basic fact about $ \kappa $-saturated and $ \kappa $-strongly homogeneous structures is that enough of them exist:
- Every consistent theory T has a model which is both $ \kappa $-saturated and $ \kappa $-strongly homogeneous.
- In fact, if M is any structure and $ \kappa $ is any infinite cardinal, then M has an elementary extension which is $ \kappa $-saturated and $ \kappa $-strongly homogeneous.
Unfortunately it is hard to guarantee the existence of saturated models of set-size. Here are some results in these directions:
- Countable ultrapowers of countable structures in countable languages are always $ \aleph_1 $-saturated, and typically have cardinality $ 2^{|\aleph_0|} $. If the continuum hypothesis holds, it follows that countable theories have saturated models.
- More generally, if the generalized continuum hypothesis holds, there is some way to construct saturated models using ultrapowers, if I recall correctly.
- If M has size less than some inaccessible cardinal $ \kappa $, then M has a saturated elementary extension of size $ \kappa $. In particular, if there are a proper class of inaccessible cardinals, then every structure has a saturated elementary extension.
- Stable theories have saturated models. In particular, if a structure M is stable, then M has a saturated elementary extension.
An easy work around this problem is to take a conservative extension of ZFC. Take for example the BGC (Bernays-Goedel-Global Choice) were we have class-size elements. In that we can construct a monster model of class-size. For details see the Tent and Ziegler book. Now if one wants to realise global-types of this class size monster model in a bigger, one can construct a monster of size "class of all classes". But this has to be done in a conservative of BGC again.
ZFC cannot show that every consistent first-order theory has a saturated model (Hodges 1993 p.506)
Properties of Saturated ModelsEdit
Saturated models are strongly homogeneous:
Theorem: If M is saturated (i.e., |M|-saturated), then M is |M|-strongly homogeneous.
Saturated structures are determined up to isomorphism by their complete theory and cardinality:
Theorem: If T is a complete theory, any two saturated models of T of the same cardinality are isomorphic. Equivalently, if M and N are two elementarily equivalent saturated structures, of the same cardinality, then M and N are isomorphic.
Strongly Homogeneous StructuresEdit
The main use of strong homogeneity lies in the following basic facts:
Theorem: Let M be a $ \kappa $-strongly homogeneous structure. Let A ⊆ M have size less than $ \kappa $. Let a and b be two tuples of length less than $ \kappa $. Then $ a \equiv_A b $ (i.e., tp(a/A) = tp(b/A)) if and only if there is an automorphism $ \sigma \in \text{Aut}(M/A) $ sending a to b. Here $ \text{Aut}(M/A) $ is the group of automorphisms of M fixing A pointwise.
Proof: If some $ \sigma \in \text{Aut}(M/A) $ sends a to b, then for any formula $ \phi(x;c) $ over A, we certainly have
- $ M \models \phi(a;c) \iff M \models \phi(\sigma(b);\sigma(c)) \iff M \models \phi(b;c) $,
by symmetry. This does not require strong homogeneity.
Conversely, suppose $ a \equiv_A b $. Then $ Aa \equiv_\emptyset Ab $, where we are using the standard notation $ Aa $ to denote the concatenation of A and a. At any rate, there is then a partial elementary map f from $ A \cup a $ to $ A \cup b $ fixing A pointwise and sending a to b. By strong homogeneity, this can be extended to an automorphism in $ \text{Aut}(M/A) $.
QED.
Theorem: Let M be a $ \kappa $-saturated and $ \kappa $-strongly homogeneous structure. Let A ⊆ M be a subset of size less than $ \kappa $, and a be a finite tuple from M. Then a is in the definable closure of A if and only if a is fixed by Aut(M/A). Similarly, a is in the algebraic closure of A if and only if a has finite orbit under Aut(M/A).
See the article on definable and algebraic closure for the proof. One uses $ \kappa $-saturation to verify that
- a ∈ dcl(A) if and only if a is the unique realization of tp(a/A) in M.
- a ∈ acl(A) if and only if tp(a/A) has finitely many realizations in M.
Then one uses the previous Theorem to conclude that the set of realizations of tp(a/A) is exactly the orbit of a under Aut(M/A).
More generally, the definable closure part of this Theorem remains true without the assumption that a is finite, but merely that a has size less than $ \kappa $.
ProofsEdit
κ-Saturated Models ExistEdit
Lemma 1: Let M be a structure. Then there exists an elementary extension of M in which every type over M is realized.
Proof: Let T be the union of the elementary diagram together with the statements
- $ \{ \phi(c_p; a) | \phi(x;a) \in p, ~ p \in S_n(M), ~ n < \omega\} $
where we have added a new constant symbol c_{p} for each type p over M. If T_{0} is a finite subset of T, then M can be made into a model of T_{0} by choosing the c_{p} appropriately. Indeed, for each type p, the set of statements in T_{0} concerning c_{p} is a finite subset of p, and is therefore satisfiable in M.
So by compactness, T has a model N. Since T contains the elementary diagram of M, $ N \succeq M $. Also, for each type p over M, N contains an element c_{p} satisfying p, by choice of T. QED.
Theorem: Let M be a structure and $ \kappa $ be an infinite cardinal. Then M has a $ \kappa $-saturated elementary extension.
Proof: A $ \kappa^+ $-saturated elementary extension of M will certainly be $ \kappa $-saturated, so replacing $ \kappa $ with $ \kappa^+ $, we may assume that $ \kappa $ is regular.
Build an ascending chain $ \{M_\alpha\}_{\alpha < \kappa} $ of structures inductive as follows:
- M_{0} = M
- $ M_{\alpha+1} $ is an elementary extension of $ M_\alpha $ in which all types over $ M_\alpha $ are realized. We can find such an elementary extension by the Lemma.
- If $ \lambda $ is a limit ordinal, $ M_\lambda = \bigcup_{\alpha < \lambda} M_\alpha $.
On easily proves by induction on $ \alpha $ that $ M_\alpha \succeq M_\beta $ for all $ \beta < \alpha $, using the Tarski-Vaught Theorem at the limit ordinals. So this is an elementary chain of models. Let N be the union of this elementary chain. Again, by Tarski-Vaught, N is an elementary extension of every $ M_\alpha $. In particular, it is an elementary extension of M_{0} = M.
It suffices to show that N is $ \kappa $-saturated. Let A be a subset of N of size less than $ \kappa $. Because $ \kappa $ is regular, $ A \subset M_\alpha $ for some $ \alpha < \kappa $. Now every type over A can be extended to a (complete) type over $ M_\alpha $. Since every type over $ M_\alpha $ is realized in $ M_{\alpha+1} $, so is every type over A. Consequently, every type over A is realized in N. Thus 'N is $ \kappa $-saturated. QED
Partial Elementary MapsEdit
Recall that if M, N are two structures, a partial elementary map from M to N is a map f : A -> N for some subset A ⊆ M with the property that for every tuple a from A and every formula $ \phi(x) $,
- $ M \models \phi(a) \iff N \models \phi(f(a)) $
Partial elementary maps are always injective (consider the case where $ \phi(x,y) $ is the formula x = y). The inverse of a partial elementary map is always a partial elementary map.
The notion of a partial elementary map is closely related to the notion of type. Specifically, if $ \alpha $ is an (infinite) tuple enumerating A, then f is a partial elementary map if and only if $ \alpha $ and $ f(\alpha) $ have the same type over the empty set, i.e.,
- $ \alpha \equiv_\emptyset f(\alpha) $.
In particular, if $ \alpha $ and $ \beta $ are tuples from M and N having the same type, then there is a partial elementary map mapping $ \alpha_i $ to $ \beta_i $ for each i in the index set.
If f : A -> B is a partial elementary map from A ⊆ M onto B ⊆ N, then we can push forward types from A to B. Specifically, let p be a type on A. The push-foward f*p(x) is the type on B given as follows:
- $ f^*p(x) = \{\phi(x;f(a)) | a \in A, ~ \phi(x;a) \in p(x)\} $
The fact that the type f*p is consistent follows from the fact that f is a partial elementary map. This definition even makes sense when p is an infinitary type.
Observation: Let a and b be possibly infinite tuples in M and N respectively, having the same type over the empty set. So there is an elementary map f sending a coordinatewise to b. If c is a (possibly infinite) tuple from M, and p = tp(c/a), then a tuple d from N realizes f*p if and only if
- $ ac \equiv_\emptyset bd $,
i.e., we can extend the partial elementary map f to a ∪ c by mapping c to d. (Here, we are using ac to denote the concatenation of a and c, and similarly for bd.)
Proof: This really follows by unwinding the definitions. The type p is the set
- $ \{\phi(x;a) | M \models \phi(c;a) \} $
So f*p is
- $ \{\phi(x;b) | M \models \phi(c;a) \} $
And in particular, d realizes f*p if
- $ M \models \phi(c;a) \implies N \models \phi(d;b) $
for all formulas $ \phi(x;y) $. Replacing $ \phi(x;y) $ with its negation, we get the implication in the other direction. So d realizes f*p if and only if
- $ M \models \phi(c;a) \iff N \models \phi(d;b) $
for all formulas $ \phi $. This is equivalent to
- $ ac \equiv_\emptyset bd $
QED.
From this, we conclude:
Lemma 2: Let M and N be structures, and f be a partial elementary map from a subset A ⊆ M onto a subset B ⊆ N. Suppose c is a singleton from A, and every 1-type over B is realized in N. Then we can extend f to a partial elementary map from A ∪ {c} to (some subset of) N.
Proof: Let p = tp(c/A). This is a 1-type because c is a singleton. The pushforward f*p is also a 1-type; by assumption it is realized by some d in N. Then by the Observation, we can extend f to A ∪ {c} by declaring f(c) = d.
QED.
From 1-types to n-types and infinitary typesEdit
Theorem: Let M be a structure, and $ \kappa $ be an infinite cardinal. The following are equivalent:
- For every subset A ⊆ M of size less than $ \kappa $, every 1-type over A is realized in M.
- For every subset A ⊆ M of size less than $ \kappa $, every n-type over A is realized in M, for all n.
- For every subset A ⊆ M of size less than $ \kappa $, and every (complete) infinitary type p(x) over A, with x a tuple of length at most $ \kappa $, p is realized in M.
Proof: Each successive condition is clearly stronger than the previous ones, so it suffices to prove the third condition from the first.
Assume that M has the first property, so every 1-type over a subset of M of size less than $ \kappa $ is realized in M. Let A ⊆ M have size less than $ \kappa $. Let p(x) be a finitary or infinitary type over A. We may assume that the tuple of variables x is indexed by some cardinal number $ \lambda \le \kappa $. Let N be an elementary extension of M in which p(x) is realized by some tuple c. We want to find a tuple d in M such that
- $ c \equiv_A d $
or equivalently
- $ Ac \equiv_\emptyset Ad $.
The identity map on A is a partial elementary map from a subset of N to M, and we basically want to extend the domain of this partial elementary map from A to Ac.
Let $ c_{< \alpha} $ denote the initial segment of the tuple $ c $ consisting of $ c_\beta $ for $ \beta < \alpha $.
Inductively build an increasing sequence of partial elementary maps
- $ f_\alpha : A c_{<\alpha} \to M $
as follows
- $ f_0 $ is the identity map from A to A
- Given $ f_\alpha $, apply Lemma 2 above to extend the domain of this map to the element $ c_\alpha $, yielding
- $ f_{\alpha+1} : A c_{<\alpha} c_\alpha \to M $
- Here we are using the fact that $ A c_{<\alpha} $ is a set of size less than $ \kappa $, so that every 1-type over $ f(A c_{<\alpha}) $ is realized in M, by assumption.
- If $ \alpha $ is a limit ordinal, let $ f_\alpha $ be the union of $ f_\beta $ for $ \beta < \alpha $. An easy exercise shows that this is a partial elementary map. (A function f is a partial elementary map if and only if its restriction to every finite set is a partial elementary map.)
The union of this increasing chain of partial elementary maps will itself be a partial elementary map $ f : Ac \to M $. Then
- $ Ac \equiv_\emptyset f(A)f(c) = Af(c) $
so that
- $ c \equiv_A f(c) $
In particular, tp(f(c)/A) = tp(c/A) = p. Since f mapped into M, we have realized the type p inside M.
QED.
Strongly Homogeneous ModelsEdit
Lemma 3: Let
- $ M_0 \preceq M_1 \preceq M_2 \preceq \cdots $
be an elementary chain of models, of length $ \omega $, and let N be the union of this chain. Suppose that for each i, M_{i+1} is |M_{i}|^{+}-saturated. Let f : A -> M_{0} be a partial elementary map for some A ⊆ M_{0}. Then there is an automorphism $ \sigma $ of N extending f.
Proof: We use a back-and-forth argument. First of all, by Tarski-Vaught, each M_{i} is an elementary substructure of N. So f is a partial elementary map even as a map on subsets of N (rather than M_{0}).
Claim: Let g be a partial elementary map from some subset of M_{i} to some subset of M_{i}. Then we can extend g to a partial elementary map whose domain is all of M_{i} and whose range is contained in M_{i+1}. Alternatively, we can extend g to a partial elementary map whose domain is contained in M_{i+1} and whose range is exactly M_{i}.
Proof: Let A be the domain of g. Let p(x) be the type of M_{i} over A. If $ \kappa = |M_i| $, then $ M_{i+1} $ is \kappa^+-saturated. Since $ |g(A)| < \kappa^+ $ and x is a tuple of length at most $ \kappa^+ $, by the Theorem above we have that the pushforward type g*p (an infinitary type over $ g(A) \subset M_i $) is realized in $ M_{i+1} $. If D realizes this, then
- $ A M_i \equiv_\emptyset g(A) D $.
In particular, the map sending $ M_i $ coordinatewise to D is a partial elementary map, extending g. This map has domain exactly $ M_i $ and has range contained in $ M_{i+1} $.
If we instead wanted the range to be exactly $ M_i $ and the domain to be contained in $ M_{i+1} $, apply the same argument to $ g^{-1} $. QED_{claim}.
Now build an increasing sequence of partial elementary maps
- $ f_0 \subset f_1 \subset f_2 \cdots $
with each $ f_i $ being a partial elementary map from some subset of $ M_i $ to some subset of $ M_i $. Do so as follows:
- $ f_0 $ is the original map f
- For n > 0 even, let $ f_n $ be a partial elementary map from $ M_{n-1} $ to a subset of $ M_n $ extending $ f_{n-1} $. This is doable by the Claim.
- For n > 0 odd, let $ f_n $ be a partial elementary map from a subset of $ M_n $ onto $ M_{n-1} $ extending $ f_{n-1} $. This is doable by the claim.
Let $ \sigma $ be the union of this increasing chain of partial elementary maps on subsets of N. Then $ \sigma $ is itself a partial elementary map. However, the even steps insure that the domain of $ \sigma $ is
- $ \bigcup_{k = 1}^\infty M_{2k - 1} = N $
while the odd steps insure that the range of $ \sigma $ is
- $ \bigcup_{k = 1}^\infty M_{2k} = N $.
In particular, $ \sigma $ is defined on all of N, and is surjective onto N. So $ \sigma $ is in fact an automorphism of N.
QED.
Lemma 4: Let M be a structure. We can find an elementary extension $ N \succeq M $ such that every type over M is realized in N, and every partial elementary map from a subset of M to M can be extended to an automorphism of N.
Proof: Build an increasing elementary chain of models
- $ M = M_0 \preceq M_1 \preceq M_2 \preceq \cdots $
by inductively choosing M_{i+1} to be an |M_{i}|^{+}-saturated elementary extension of M_{i}. The union of this chain is an elementary extension of M, by Tarski-Vaught. Every type over M is realized in M_{1}, hence in N. And by Lemma 3, every partial elementary map on subsets of M extends to N.
QED.
Theorem: Let M be a structure, and $ \kappa $ be an infinite cardinal. Then M has an elementary extension which is both $ \kappa $-saturated and $ \kappa $-strongly homogeneous.
Proof: As in the proof that $ \kappa $-saturated models exist, we may replace $ \kappa $ with $ \kappa^+ $ and assume that $ \kappa $ is a regular cardinal.
Build an elementary chain $ \{M_\alpha\}_{\alpha < \kappa} $ as follows.
- $ M_0 $ is M
- $ M_{\alpha+1} $ is an elementary extension of $ M_\alpha $ such that every type over $ M_\alpha $ is realized in $ M_{\alpha+1} $ and every partial elementary map from a subset of $ M_\alpha $ to $ M_\alpha $ extends to an automorphism of $ M_{\alpha+1} $. Such an elementary extension of $ M_\alpha $ exists by Lemma 4.
- If $ \alpha $ is a limit cardinal, take $ M_\alpha $ to be the union of the $ M_\beta $ for $ \beta < \alpha $.
Let N be the union of this chain. By Tarski-Vaught, the $ M_\alpha $ form an elementary chain and $ M_\alpha \preceq N $ for each $ \alpha $.
If A is a subset of N of size less than $ \kappa $, then by regularity of $ \kappa $, $ A \subset M_\alpha $ for some $ \alpha < \kappa $. Then every type over A is realized in $ M_{\alpha+1} $, hence in N. So N is $ \kappa $-saturated.
For $ \kappa $-strong homogeneity, let f be a partial elementary map from A to B (subsets of N), with $ |A| < \kappa $. By regularity of $ \kappa $, there is some $ \alpha < \kappa $ such that $ A \cup B \subset M_\alpha $. By choice of $ M_{\alpha + 1} $, there is an automorphism $ \sigma_{\alpha+1} $ of $ M_{\alpha+1} $ extending f.
Recursively define $ \sigma_\beta \in \text{Aut}(M_\beta) $ for $ \alpha < \beta \le \kappa $ (where $ M_\kappa = N $) as follows:
- $ \sigma_{\alpha+1} $ is an automorphism of $ M_{\alpha+1} $ extending f. This is doable by choice of $ M_{\alpha+1} $.
- For $ \beta > \alpha $, $ \sigma_{\beta+1} $ is an automorphism of $ M_{\beta+1} $ extending the automorphism $ \sigma_\beta $ of $ M_\beta $.
- For $ \lambda $ a limit ordinal, $ \sigma_\lambda $ is the union of the increasing chain of $ \sigma_\beta $ for $ \beta < \lambda $.
Then the $ \sigma_\beta $ form an increasing chain of automorphisms, each extending f, and $ \sigma_\kappa $ is an automorphism of N extending f.
QED.
Saturated ModelsEdit
Recall that M is saturated if M is |M|-saturated.
Theorem: Suppose M and N are two saturated models of the same size, which are elementarily equivalent. Then M and N are isomorphic.
Proof: The type over M over the empty set is consistent with N, because M and N are elementarily equivalent. (The assertion that M and N are elementarily equivalent is equivalent to assertion that the empty map between Ø ⊆ M and Ø ⊆ N is a partial elementary map. Push forward tp(M/Ø) along this map.) Since M is a tuple of length at most |N|, the type of M is realized in N. This means that there is an elementary embedding of M into N. Similarly, we can embed N into M. With a bit more work (a back-and-forth argument) we can obtain an isomorphism between M and N. This is done as follows:
Let $ \kappa = |M| = |N| $. Choose enumerations $ \{m_\alpha\}_{\alpha < \kappa} $ and $ \{n_\alpha\}_{\alpha < \kappa} $ of M and N, respectively. Build up by induction on $ \alpha $ a sequence $ \{f_\alpha\}_{\alpha < \kappa} $ of partial elementary maps from subsets of M to subsets of N. The $ f_\alpha $'s will form an increasing chain, and $ f_\alpha $ will have domain and range of cardinality at most $ \aleph_0 + |\alpha| $. Proceed as follows:
- $ f_0 $ will be the empty map. This is a partial elementary map because $ M \equiv N $.
- If $ \lambda $ is a limit ordinal, define $ f_\lambda $ to be the union of the $ f_\alpha $ for $ \alpha < \lambda $. This will be a partial elementary map because its restriction to any finite subset is a partial elementary map. Its domain and range will have size at most $ |\lambda|^2 = |\lambda| $, because the domain of $ f_\alpha $ is a union of $ \lambda $-many sets of size at most $ |\lambda| $.
- Given $ f_\alpha $, define $ f_{\alpha + 1} $ as follows. Since $ \alpha < \kappa $, the domain and range of $ f_\alpha $ have size at most $ |\alpha| < \kappa $, and therefore must not be all of $ M $ or $ N $, respectively. In particular, every 1-type over the range of $ f_\alpha $ is realized in N. Hence, by Lemma 2, we can extend $ f_\alpha $ to a partial elementary map on $ \text{dom}(f_\alpha) \cup \{m_\alpha\} $. Calling the resulting map $ g_\alpha $, we now run the same argument on $ g_\alpha^{-1} $ to extend $ g_\alpha $ to a partial elementary map whose range includes $ n_\alpha $. Let $ f_{\alpha+1} $ be this new partial elementary map. The domain and range of $ f_{\alpha+1} $ are bigger than the domain and range of $ f_\alpha $ by at most two, so the condition on the cardinalities of the domain and range of $ f_{\alpha+1} $ are satisfied.
Let f be the union of all the $ f_\alpha $. This is a partial elementary map from some subset of M to some subset of N. By the construction, $ m_\alpha $ is in the domain of $ f_\alpha $ and hence in the domain of f, for every $ \alpha $. In particular, the domain of f contains all of M. Similarly, the range of f contains all of N. As a partial elementary map, f is an injection, so f is a bijection from M to N. Then f is an isomorphism from M to N.
QED.
Corollary: Let T be a complete theory. Then T has at most one saturated model, up to isomorphism, of each cardinality.
Corollary: Let M be a saturated structure. Then M is |M|-strongly homogeneous.
Proof: Let f : A -> B be a partial elementary map between two subsets of M of cardinality less than |M|. Let L be the language/signature of M, and let L(A) be the language obtained by adding a constant c_{a} for every element a ∈ A. There is a tautological way to view M as an L(A)-structure, by interpreting c_{a}. Let M_{1} denote this expansion of M to the language L(A).
We claim that M_{1} is saturated. If S ⊆ M is a subset of size less than |M|, then S ∪ A also has size less than |M|. An L-formula over S ∪ A is the same thing as an L(A)-formula over S, so a 1-type over S ∪ A in M is equivalent to a 1-type over S in M_{1}. In particular, the fact that all 1-types over S ∪ A is realized in M implies that all 1-types over S are realized in M_{1}. So M_{1} is saturated.
We can also make M into an L(A)-structure in another way, by interpreting c_{a} as f(a). Call this expansion M_{2}. By the same argument, M_{2} is saturated.
Moreover, M_{1} and M_{2} are elementarily equivalent, essentially because f is a partial elementary map. Indeed, for any L-formula $ \phi(x_1,\ldots,x_n) $,
- $ M_1 \models \phi(c_{a_1},\ldots,c_{a_n}) \iff M \models \phi(a_1,\ldots,a_n) \iff M \models \phi(f(a_1),\ldots,f(a_n)) \iff M_2 \models \phi(c_{a_1},\ldots,c_{a_n}) $
where the middle equivalence follows from the fact that f is an elementary map.
So M_{1} and M_{2} are elementarily equivalent saturated structures of the same size (since they have the same underlying set). By the Theorem, they must be isomorphic. Let $ \sigma : M_1 \to M_2 $ be an isomorphism witnessing this. Then $ \sigma $ induces an isomorphism of the reducts to L, which are both M. So $ \sigma $ induces an automorphism of M. Moreover, to be a morphism of L(A)-structures, $ \sigma $ must send the interpretation of c_{a} in M_{1} to the interpretation of c_{a} in M_{2}. In other words, $ \sigma $ must send a to f(a). So $ \sigma $ extends f.
QED.
Criteria for the Existence of Saturated ModelsEdit
Theorem: Let $ \{M_i : i < \omega\} $ be a countable list of structures in some countable language L. Let $ \mathcal{U} $ be a non-principal ultrafilter on $ \omega $. Then the ultraproduct $ M = \prod_{i < \omega} M_i / \mathcal{U} $ is $ \aleph_1 $-saturated.
Proof: Since the language is countable, any type over a countable subset of M must consist of countably many formulas. So it suffices to show that any countable consistent partial type over M is realized in M. A countable partial type can be enumerated as $ \{\phi_i(x;a_i) : i < \omega\} $. Each $ a_i $ can be represented by some element
- $ (a_{i,1}, a_{i,2}, \ldots) \in \prod_{j < \omega} M_j $,
where each $ a_{i,j} $ is a tuple in $ M_j $ of the same length and sort as $ a_i $ in $ M $.
The fact that this partial type is consistent means that for each n,
- $ M \models \exists x : \bigwedge_{i < n} \phi_i(x;a_i) $
In particular, by Łoś's theorem, for "most" values of j,
- $ M_j \models \exists x : \bigwedge_{i < n} \phi_i(x;a_{i,j}) $.
Let
- $ S_n = \{j : M_j \models \exists x : \bigwedge_{i < n} \phi_i(x;a_{i,j}) \} $
Then
- $ S_0 \supseteq S_1 \supseteq S_2 \supseteq S_3 \cdots $
and each $ S_n \in \mathcal{U} $ (by Łoś's theorem). Let
- $ T_n = S_n \cap \{n, n+1, n+2, \ldots\} $,
and let $ T_{-1} = \mathbb{N} $. Then $ T_n \in \mathcal{U} $, because both $ S_n $ and $ \{n,n+1,n+2,\ldots\} $ are in $ \mathcal{U} $ (the latter because $ \mathcal{U} $ is non-principal). Also, the $ T_n $ form a descending sequence:
- $ T_{-1} \supseteq T_0 \supseteq T_1 \supseteq T_2 \supseteq \cdots $
For each j, let n(j) be the largest n such that $ j \in T_n $. A largest such n exists because if $ j \in T_n $, then $ j \ge n $. Choose a singleton $ c_j \in M_j $ as follows:
- If n(j) = -1, choose $ c_j $ randomly.
- Otherwise, $ j \in T_{n(j)} \subset S_{n(j)} $, so
- $ M_j \models \exists x : \bigwedge_{i < n(j)} \phi_i(x;a_{i,j}) $
- Let $ c_j $ be an $ x \in M_j $ witnessing this. So
- $ M_j \models \bigwedge_{i < n(j)} \phi_i(c_j;a_{i,j}) $
Let c be the class of
- $ (c_0,c_1,c_2,\ldots) $
in the ultraproduct M.
Note that if $ j \in T_{m+1} $, then $ m < n(j) $, by definition of $ n(j) $. Then by choice of $ c_j $, we have
- $ M_j \models \bigwedge_{i < n(j)} \phi_i(c_j;a_{i,j}) $,
and in particular
- $ M_j \models \phi_m(c_j;a_{m,j}) $.
Consequently,
- $ \{j : M_j \models \phi_m(c_j;a_{m,j})\} \supseteq T_{m+1} $.
Since $ T_{m+1} $ is "big" with respect to the ultraproduct $ \mathcal{U} $, so is the even-bigger set
- $ \{j : M_j \models \phi_m(c_j;a_{m,j})\} $.
By Łoś's Theorem, it follows that
- $ M \models \phi_m(c;a_m) $.
This holds for each m, so c satisfies our original partial type $ \{\phi_i(x;a_i)\} $. In particular, the type is realized in M.
QED.
Corollary: Assume the continuum hypothesis. Then every consistent theory T in a countable language has a saturated model. Proof: Without loss of generality, T is complete. If the models of T are finite, then they are automatically $ \kappa $-saturated for all $ \kappa $, and there is nothing to show. So assume the models of T are infinite. Let M be some countable model. Let $ \mathcal{U} $ be a non-principal ultrafilter on $ \mathbb{N} $, and let $ N = M^\mathcal{U} $ be the corresponding ultrapower. Then by the Theorem, $ N $ is $ \aleph_1 $-saturated. But $ N $ is a quotient of $ M^\mathbb{N} $ which has size $ 2^{\aleph_0} $. By the continuum hypothesis, this is at most $ \aleph_1 $, so
- $ |N| \le \aleph_1 $
Therefore, N is |N|-saturated. Also, $ N \models T $ because N is an ultrapower of a model of T.
QED.
Some variant of these facts works in other cardinalities, though one has to be more careful about the choice of the ultrafilter. In particular, if one assumes the Generalized Continuum Hypothesis, one can show that every structure has a saturated elementary extension. (Somebody who knows about good ultrafilters should verify this.)
Lemma 5: Let M be a structure in a language L. Then there is an elementary extension $ N \succeq M $ such that every type over M is realized in N, and $ |N| \le 2^{|M| + |L|} $.
Proof: Let N_{0} be an elementary extension of M in which all types are realized (Lemma 1 above). A type p(x) over M is determined by which L(M) formulas $ \phi(x) $ are true of the variable x. There are only $ (|M| + |L|) $-many L(M)-formulas, so there are at most $ 2^{|M| + |L|} $ types over M. For each type over M, choose a realization in N_{0}. Let S be the set of all these realizations. Thus $ |S| \le 2^{|M| + |L|} $. By Downward Löwenheim–Skolem, we can find an elementary substructure $ N \preceq N_0 $ containing $ S \cup M $, of size $ |S \cup M| \le 2^{|M| + |L|} $. Then N is an elementary extension of M,
- $ |N| \le 2^{|M| + |L|} $
and every type over M is realized in S, hence in N.
QED.
Theorem: Assume there exists a proper class of strongly inaccessible cardinals. Then every structure M has an elementary extension which is saturated.
Proof: Let $ \kappa $ be an inaccessible cardinal greater than the size of M and greater than the size of the language. Build an increasing elementary chain $ \{M_\alpha\}_{\alpha < \kappa} $ as follows:
- $ M_0 = M $
- If $ \lambda $ is a limit ordinal, then
- $ M_\lambda = \bigcup_{\alpha < \lambda} M_\alpha $
- Given $ M_\alpha $, let $ M_{\alpha+1} $ be an elementary extension of $ M_\alpha $ in which all types over $ M_\alpha $ are realized, but $ |M_{\alpha+1}| \le 2^{|M_\alpha| + |T|} $. Such a model can be found by Lemma 5.
By induction on $ \alpha $, we see that $ |M_\alpha| < \kappa $. The base case is by choice of $ \kappa $. The limit ordinal case follows from the regularity of $ \kappa $. The successor ordinal step follows from the fact that $ \kappa $ is a strong limit cardinal:
- $ |M_{\alpha+1}| \le 2^{|M_\alpha| + |T|} < \kappa $,
because
- $ |M_\alpha| + |T| < \kappa $
by induction.
Let N be the limit structure. Then N is $ \kappa $-saturated, by the same arguments used in the theorems above (using the fact that $ \kappa $ is regular). Since N is the union of $ \kappa $-many structures of size less than $ \kappa $, N has size $ \kappa $ (or less). Therefore, N is |N|-saturated.
QED.
Theorem: Let T be a complete theory, and suppose T is stable. Then every model of T has a saturated elementary extension.
Proof: TODO. It's in Poizat's Model Theory book.