The following is a(nother) problem from an old qualifying exam in logic:
Let $T$ be a first-order theory in a countable language $\mathcal{L}$ admitting an infinite model. Show that for every cardinal $\kappa \geq \aleph_0$ there is a model $\mathcal{N} \models T$ of cardinality $\kappa$ such that, for every $A \subseteq N$, there are at most $\vert A \vert + \aleph_0$ types from $S^{\mathcal{N}}_1(A)$ realized in $\mathcal{N}$.
Here $S^{\mathcal{N}}_1(A)$ denotes the set of all complete $1$-types over $A$ in $\text{Th}(\mathcal{N})$ (so, a set $p$ of $\mathcal{L}_A$-formulas in one free variable belongs to $S^{\mathcal{N}}_1(A)$ if and only if $p \cup \text{Th}_A(\mathcal{N})$ is satisfiable and, for all $\mathcal{L}_A$-formulas $\phi$ in one free variable, either $\phi \in p$ or $\lnot \phi \in p$; this is a paraphrase of Marker's Definition 4.1.1).
My first instinct was to try, for each $\kappa \geq \aleph_0$, to find a model that is as "unsaturated" as possible. This led me to consider atomic models; however, I don't know of any existence theorems for uncountable atomic models that don't depend on specific assumptions about $T$. Further, because $T$ is not even assumed to be complete, I am doubtful whether this line of thinking is useful, since we usually don't talk about atomic or saturated models of non-complete theories.
Since the only other potentially relevant theorem I could think of was the omitting types theorem (and its generalization to higher cardinalities — the theorem called the $\alpha$-omitting types theorem by Chang and Keisler), I wondered if it might be possible to use this instead; perhaps we could ensure that, in some model of the right size, many types are omitted. However, the only omitting types theorems I know assume $A = \emptyset$.
Is either one of these two approaches useful? If not, what would be a hint in the right direction?
Best Answer
Such models can be constructed using indiscernible sequences and are called Ehrenfeucht-Mostowski models. Most books on model theory should contain a treatment of this construction. Here are a few popular references:
There is also an online version of the argument on the Model Theory wiki.