FANDOM


The Ehrenfeucht-Mostowski construction is a construction which produces models in which few types are realized.

Theorem. Let $ T $ be a complete theory with infinite models. Then for any $ \kappa \ge |T| $, there is a model $ M \models T $ of cardinality $ \kappa $ such that if $ A \subset M $, then at most $ |A| + |T| $ types over $ A $ are realized.

Proof. First suppose that $ T $ has definable Skolem functions. Let $ \{a_\lambda\}_{\lambda < \kappa} $ be a non-constant indiscernible sequence of length $ \kappa $ in some model $ M_0 $. We can find such an indiscernible sequence by extracting an indiscernible sequence from a non-constant sequence in an infinite model. Let $ M $ be $ \operatorname{dcl}(\{a_\lambda : \lambda < \kappa\}) $. Because $ T $ has definable Skolem functions, $ M \preceq M_0 $, so $ M \models T $ and $ \{a_\lambda\}_{\lambda < \kappa} $ is still indiscernible within $ M $. The set $ \{a_\lambda\} $ is called the spine. Let $ A $ be a subset of $ M $. Each element of $ A $ is in the definable closure of some finite subset of the spine, so we can find some $ A' $ contained in the spine, with $ A \subset \operatorname{dcl}(A') $, and $ |A'| \le |A| + |T| $. An element’s type over $ A $ is determined by its type over $ A' $, because $ A \subset \operatorname{dcl}(A') $. So it suffices to show that at most $ |A'| + |T| = |A| + |T| $ types over $ A' $ are realized.

First we check that at most $ |A'| $ types are realized by tuples from the spine. We can write $ A' $ as $ \{a_\lambda : \lambda \in S\} $ for some $ S \subset \kappa $ with $ |S| = |A'| $. The indiscernibility of the spine implies that $ \operatorname{tp}(a_{\lambda_1}a_{\lambda_2}\cdots a_{\lambda_n}/A') $ is entirely determined by how the $ \lambda_i $ relate to each other and how they relate to elements of $ S $. That is, $ \operatorname{tp}(a_{\lambda_1} \cdots a_{\lambda_n}/A') $ is entirely determined by the following pieces of data:

  • Whether $ \lambda_i \le \lambda_j $ for each $ i, j $.
  • The set $ \{x \in S : x \le \lambda_i\} $ for each $ i $.
  • The set $ \{x \in S : x < \lambda_i\} $ for each $ i $.

Because $ S $ is well-ordered, there are only about $ |S| + \aleph_0 $ choices for the second and third bullet points. All told, there are therefore only $ |S| + \aleph_0 \le |A'| + |T| $ possibilities for $ \operatorname{tp}(a_{\lambda_1}\cdots a_{\lambda_n}/A') $.

Now if $ f(x_1,\ldots,x_n) $ is a 0-definable function, then $ \operatorname{tp}(f(a_{\lambda_1},\ldots,a_{\lambda_n})/A') $ depends only on $ \operatorname{tp}(a_{\lambda_1},\ldots,a_{\lambda_n}/A') $, so there are at most $ |A'| + |T| $ types over $ A' $ realized by elements of the form $ f(a_{\lambda_1},\ldots,a_{\lambda_n}) $. But all of $ M $ is in the definable closure of the spine, so every element of $ M $ is of this form. Since there are only $ |T| $-many 0-definable functions, the total number of types over $ A' $ realized in $ M $ is at most $ (|A'| + |T|) \times |T| = |A'| + |T|. $ So at most $ |A'| + |T| $ types over $ A' $ are realized, completing the proof (in the case where we had definable Skolem functions).

Now suppose $ T $ is arbitary. We can find a theory $ T' $ expanding $ T $, which does have Skolem functions. This can easily be done in such a way that $ |T'| = |T| $. By the above argument one gets a model $ M' $ of $ T' $ of size $ \kappa $ with the property that for every subset $ A $ of $ M' $, at most $ |A| + |T| $ types over $ A $ are realized in $ M' $. Let $ M $ be the reduct of $ M' $ to the original language. Then $ M \models T $. If $ A \subset M $, and $ a $ and $ b $ have the same $ T' $-type over $ A $, then they certainly have the same $ T $-type over $ A $ within $ M $, because $ T $ has fewer definable sets and relations to work with than $ T' $. So there are at most as many $ T $-types over $ A $ as there are $ T' $-types over $ A $, which is at most $ |A| + |T| $. QED

An important consequence of this result is the following, which is the first step of the proof of Morley’s Theorem.

Corollary. Let $ T $ be a complete countable theory which is $ \kappa $-categorical for some $ \kappa \ge \aleph_1 $. Then $ T $ is $ \aleph_0 $-stable (hence totally transcendental).

Proof. Let $ \mathbb{U} $ be the monster model of $ T $. Suppose $ T $ is not $ \aleph_0 $-stable. Then we can find a countable set $ A $ over which there are uncountably many types. Realize $ \aleph_1 $ of these types and let $ B $ be the set of these realizations. Then $ |A \cup B| \le \aleph_1 \le \kappa $, so by Löwenheim-Skolem we can find a model $ M $ of cardinality $ \kappa $ containing $ A \cup B $. By the Ehrenfeucht-Mostowski construction, we can find a model $ M' $ of cardinality $ \kappa $ in which at most countably many types are realized over countable sets. By $ \kappa $-categoricity, $ M \cong M' $. So $ M $ also has the property that over countable sets, countably many types are realized. But over the countable set $ A \subset M $, uncountably many types are realized in $ B \subset M $, a contradiction.

(It is a general fact that $ \aleph_0 $-stable theories are totally transcendental. The proof goes as follows: if $ T $ failed to be totally transcendental, then $ RM(D) = \infty $ for some set $ D $. Then one inductively builds a tree $ D, D_0, D_1, D_{00}, D_{01}, D_{10}, \ldots $ of non-empty $ \mathbb{U} $-definable sets such that $ D_w $ is the disjoint union of $ D_{w0} $ and $ D_{w1} $ for every $ w \in \{0,1\}^{< \omega} $, and such that each $ D_w $ has Morley rank $ \infty $. This is the same construction used to prove that perfect sets in Polish spaces have cardinality $ 2^{\aleph_0} $. At any rate, there are countably many $ D_w $’s, so the $ D_w $’s are all definable over some countable set $ A $. Now each path through the tree yields a different type over $ A $, so that there are uncountably many types over $ A $, contradicting $ \omega $-stability.) QED