The Ehrenfeucht-Mostowski construction is a construction which produces models in which few types are realized.
Theorem. Let be a complete theory with infinite models. Then for any , there is a model of cardinality such that if , then at most types over are realized.
Proof. First suppose that has definable Skolem functions. Let be a non-constant indiscernible sequence of length in some model . We can find such an indiscernible sequence by extracting an indiscernible sequence from a non-constant sequence in an infinite model. Let be . Because has definable Skolem functions, , so and is still indiscernible within . The set is called the spine. Let be a subset of . Each element of is in the definable closure of some finite subset of the spine, so we can find some contained in the spine, with , and . An element’s type over is determined by its type over , because . So it suffices to show that at most types over are realized.
First we check that at most types are realized by tuples from the spine. We can write as for some with . The indiscernibility of the spine implies that is entirely determined by how the relate to each other and how they relate to elements of . That is, is entirely determined by the following pieces of data:
Because is well-ordered, there are only about choices for the second and third bullet points. All told, there are therefore only possibilities for .
Now if is a 0-definable function, then depends only on , so there are at most types over realized by elements of the form . But all of is in the definable closure of the spine, so every element of is of this form. Since there are only -many 0-definable functions, the total number of types over realized in is at most So at most types over are realized, completing the proof (in the case where we had definable Skolem functions).
Now suppose is arbitary. We can find a theory expanding , which does have Skolem functions. This can easily be done in such a way that . By the above argument one gets a model of of size with the property that for every subset of , at most types over are realized in . Let be the reduct of to the original language. Then . If , and and have the same -type over , then they certainly have the same -type over within , because has fewer definable sets and relations to work with than . So there are at most as many -types over as there are -types over , which is at most . QED
An important consequence of this result is the following, which is the first step of the proof of Morley’s Theorem.
Corollary. Let be a complete countable theory which is -categorical for some . Then is -stable (hence totally transcendental).
Proof. Let be the monster model of . Suppose is not -stable. Then we can find a countable set over which there are uncountably many types. Realize of these types and let be the set of these realizations. Then , so by Löwenheim-Skolem we can find a model of cardinality containing . By the Ehrenfeucht-Mostowski construction, we can find a model of cardinality in which at most countably many types are realized over countable sets. By -categoricity, . So also has the property that over countable sets, countably many types are realized. But over the countable set , uncountably many types are realized in , a contradiction.
(It is a general fact that -stable theories are totally transcendental. The proof goes as follows: if failed to be totally transcendental, then for some set . Then one inductively builds a tree of non-empty -definable sets such that is the disjoint union of and for every , and such that each has Morley rank . This is the same construction used to prove that perfect sets in Polish spaces have cardinality . At any rate, there are countably many ’s, so the ’s are all definable over some countable set . Now each path through the tree yields a different type over , so that there are uncountably many types over , contradicting -stability.) QED