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?

  • 2
    $\begingroup$ What is $S_1^\mathcal{N}(A)$? $\endgroup$
    – R. Burton
    Sep 8 '20 at 3:53
  • $\begingroup$ @R.Burton Thank you for your comment -- I have updated the question to explain the notation. $\endgroup$ Sep 8 '20 at 4:06

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:

  • Model Theory by Chang and Keisler: section 3.3, in particular Corollary 3.3.14.
  • A Course in Model Theory by Tent and Ziegler: section 5.1, in particular Corollary 5.1.9.
  • Model Theory: An Introduction by Marker: section 5.2, in particular Theorem 5.2.9.

There is also an online version of the argument on the Model Theory wiki.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.