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

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

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

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

Because {\displaystyle S} is well-ordered, there are only about {\displaystyle |S|+\aleph _{0}} choices for the second and third bullet points. All told, there are therefore only {\displaystyle |S|+\aleph _{0}\leq |A'|+|T|} possibilities for {\displaystyle \operatorname {tp} (a_{\lambda _{1}}\cdots a_{\lambda _{n}}/A')}.

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

Now suppose {\displaystyle T} is arbitary. We can find a theory {\displaystyle T'} expanding {\displaystyle T}, which does have Skolem functions. This can easily be done in such a way that {\displaystyle |T'|=|T|}. By the above argument one gets a model {\displaystyle M'} of {\displaystyle T'} of size {\displaystyle \kappa } with the property that for every subset {\displaystyle A} of {\displaystyle M'}, at most {\displaystyle |A|+|T|} types over {\displaystyle A} are realized in {\displaystyle M'}. Let {\displaystyle M} be the reduct of {\displaystyle M'} to the original language. Then {\displaystyle M\models T}. If {\displaystyle A\subset M}, and {\displaystyle a} and {\displaystyle b} have the same {\displaystyle T'}-type over {\displaystyle A}, then they certainly have the same {\displaystyle T}-type over {\displaystyle A} within {\displaystyle M}, because {\displaystyle T} has fewer definable sets and relations to work with than {\displaystyle T'}. So there are at most as many {\displaystyle T}-types over {\displaystyle A} as there are {\displaystyle T'}-types over {\displaystyle A}, which is at most {\displaystyle |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 {\displaystyle T} be a complete countable theory which is {\displaystyle \kappa }-categorical for some {\displaystyle \kappa \geq \aleph _{1}}. Then {\displaystyle T} is {\displaystyle \aleph _{0}}-stable (hence totally transcendental).

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

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