In this chapter, we will introduce some classical results on Model Theory. More specifically, it’s about finding structures satisfying a type or not. The book I mainly refer to is モデルの理論 written by 坪井つぼい明人あきと and Class Note written by C. Ward Henson.

In this chapter, two methods will be reused, which are the method of ultraproduct and the method of Henkin Theory. They are quite important, and I hope this chapter will be a closure of the previous chapters and classical model theory.

Saturation

Once we talk about formulas, there is immediately a question: is it solvable? And the model-theoretic version is what is called $\kappa$-saturation.

We first recall the idea of types, and clarify its definition.

Let $\mathfrak{M}$ be an $L$-structure, and let $A\subset M$. A set $p(\bar x)$ of $L(A)$-formulas with free variables $\bar x$ is called a type if

1. (finitely satisfiable) for every finite subset $\{\varphi_i(\bar x)\}\subseteq p(\bar x)$, there is a common solution in $M$,
2. (maximal) for every $L(A)$-formula $\varphi(\bar x)$, either $\varphi(\bar x)\in p(\bar x)$ or $\neg\varphi(\bar x)\in p(\bar x)$.

We call the set $A$ the domain of $p(\bar x)$, denoted $\mathrm{dom}(p)$.

Given $\operatorname{tp}(\bar a/A)=\{\varphi(\bar x);\ \varphi(\bar x)\text{ is an }L(A)\text{-formula and }\mathfrak{M}\models\varphi(\bar a)\}$, it satisfies the definition above, therefore it is a type. But one should realize that this is only a part of types, since it requires a common solution for all formulas in the type, which is a much stronger requirement.

Definition

With this idea, we can introduce a property of a structure $\mathfrak{M}$. Given an infinite cardinal $\kappa$, if for all types $p(\bar x)$ whose domain is in $M$, and $|\mathrm{dom}(p)|<\kappa$, there is a solution to $p(\bar x)$ in $M$, we say the structure $\mathfrak{M}$ is $\kappa$-saturated.

This definition is actually equivalent to the one defined on $1$-types: the structure $\mathfrak{M}$ is $\kappa$-saturated if any $1$-type $p(x)$ whose domain is in $M$ and whose domain has cardinality less than $\kappa$ has a common solution.

We show this by generating a solution for a $2$-type via its definition, and this method can be generalized to any number. Let $q(x,y)$ be a $2$-type with the property in the definition, $q^*(y):\{\exists x\,\varphi(x,y);\ \varphi(x,y)\in q(x,y)\}$ can be extended to a $1$-type, hence a solution $b\in M$ exists. Now $q(x,b)$ becomes a $1$-type in $\mathrm{dom}(q)\cup\{b\}$ and satisfies the property we want, hence a solution $a$ exists. As what a human with a healthy brain would see, $(a,b)$ is a solution to $q(x,y)$.

One might see from the definition that a structure can only be saturated for cardinals smaller than the cardinality of its universe. Therefore, we simply call a structure $\mathfrak{M}$ saturated if it is $|M|$-saturated.

Existence

Every structure has an elementary extension where all $1$-types on it are realized. To prove this, let’s construct one for a given structure $\mathfrak{M}$. Choose $J$ to be a set whose cardinality is equal to that of all $L(M)$-formulas. Let $I$ be the set of all finite subsets of $J$ ($I\subset\mathcal{P}(J)$). Now, construct an ultrafilter $U$ on $I$ such that for every $j\in J$, $U$ contains the set $\{i\in I:\ j\in i\}$ as an element.

Let $\mathfrak{F}$ be the ultrapower of $\mathfrak{M}$. One might recall the concept of ultraproduct we have shown in chapter two. Technically, we construct the Cartesian product $M^I=\prod_{i\in I}M$. There is an equivalence relation on $M^I$ such that $(a_i)_{i\in I}\sim(b_i)_{i\in I}$ if and only if

$$\{i\in I:\ a_i=b_i\}\in U.$$

$F$ is the quotient set of $M^I$ by the equivalence relation, also denoted as $M^I/U$. And by the following definition, $\mathfrak{F}$ becomes an elementary extension of $\mathfrak{M}$.

Actually, the definition of such structure is

1. for constant $c$, $c^\mathfrak{F}=[(c^\mathfrak{M})_{i\in I}]$,
2. for function $f$ and elements $[(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}]$, $f^\mathfrak{F}([(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}])=[(f^{\mathfrak{M}}(a^1_i,\cdots,a^n_i))_{i\in I}]$,
3. for relation $R$ and elements $[(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}]$, $R^\mathfrak{F}([(a^1_i)_{i\in I}],\cdots,[(a^n_i)_{i\in I}])\Leftrightarrow\{i\in I:\ R^\mathfrak{M}(a^1_i,\cdots,a^n_i)\}\in U$.

The diagonal embedding $\delta:M\rightarrow F$ is defined as $\delta(a)=[(a)_{i\in I}]$, which is obviously an elementary embedding. We denote $\mathfrak{F}$ also as $\mathfrak{M}^I/U$.

Now, choose arbitrary $1$-type $\Gamma(x)$ in $L(X)$ where $X\subset M$. Since $J$ and all $L(X)$-formulas share the same cardinality, there is a surjective map $g:J\rightarrow \Gamma(x)$. For each $i\in I$, choose $a_i\in M$ such that $\{g(j):\ j\in i\}\subset\Gamma(x)$ and $a_i$ satisfies all formulas in this finite set. This is always possible since the type is finitely satisfiable. Then the element $[(a_i)_{i\in I}]\in \mathfrak{F}$ realizes $\Gamma(x)$, by Łoś’s Theorem. If you forget it, review chapter 2.

Hence, all types in $L(M)$ are realized.

However, the structure $\mathfrak{F}$ is not $|M|$-saturated, because there are more elements than the image of elements in $M$, and formulas containing them may not be satisfied. Hence, we need a way to generate a $\kappa$-saturated elementary extension for a given structure $\mathfrak{M}$, and here is the construction.

We write $\kappa^+$ for the smallest cardinal greater than $\kappa$, and it is a set with linear order $<$ for ordinals less than $\kappa^+$ by von Neumann theory. Now, we construct a chain of structures inductively by

1. let $\mathfrak{A}_0=\mathfrak{M}$,
2. for $\alpha$ a successor ordinal $\mathrm{S}(\beta)$, let $\mathfrak{A}_\alpha$ be the elementary extension of $\mathfrak{A}_\beta$ as defined above,
3. for $\alpha$ a limit ordinal, let $\mathfrak{A}_\alpha=\bigcup_{\beta<\alpha}\mathfrak{A}_\beta$.

Now, let $\mathfrak{S}=\bigcup_{\alpha<\kappa^+}\mathfrak{A}_\alpha$ (for those who are not familiar with the font, this is “S”). It remains to show that such structure is what we want.

By Tarski’s Chain Lemma, $\mathfrak{S}$ is an elementary extension of $\mathfrak{M}$ (actually of any structure in this chain). Now for any subset $X\subset S$ whose cardinality $\le\kappa^+$, there is some $\alpha<\kappa^+$ such that $X\subset A_\alpha$. This does not necessarily hold for arbitrary cardinality by analysis of cofinality; if the reader wants more context, Lemma 10.37 of Set Theory written by Kunen is helpful.

One will immediately find that any $1$-type in $L(X)$ is satisfied in $\mathfrak{A}_{\alpha+1}$, and naturally satisfied by $\mathfrak{S}$. Hence, $\mathfrak{S}$ is $\kappa^+$-saturated, and is $\kappa$-saturated vacuously.

This is slightly more than what we actually want, but it’s still true. There are some other proofs, and they may get better results, but I’m not going to show those here.

It’s obviously true that every theory has a $\kappa$-saturated model.

Properties

Given an $L$-theory $T$, and a $\kappa$-saturated model $\mathfrak{M}$ of $T$. Then for any model $\mathfrak{N}$ of $T$ whose cardinality $\lambda\le\kappa$, there is an elementary embedding $f:\mathfrak{N}\rightarrow\mathfrak{M}$.

We enumerate the model $\mathfrak{N}$ of cardinality $\lambda$ as $\{a_i\}_{i<\lambda}$, and let $N_\alpha:=\{a_i\}_{i<\alpha}$. Now we construct the embedding inductively.

1. $N_0=\emptyset$ and $f_0$ is the empty map.
2. For $\beta=\alpha+1$ a successor ordinal and $f_\alpha$ already constructed, consider a set of $L(N_\alpha)$-formulas $\Gamma(x)=\{\varphi(x,\bar{b});\ \mathfrak{N}\models\varphi(a_\alpha,\bar{b}),\ \bar{b}\in N_\alpha\}$. This is an $n$-type in $\mathfrak{N}$, and then by $f_\alpha$, this can be mapped to be an $L(f_\alpha(N_\alpha))$-type in $\mathfrak{M}$. By the saturatedness of $\mathfrak{M}$, there is a $b\in M$ satisfying it, and we let $f_\beta(a_\alpha)=b$. (The index is a little bit complicated and some mistakes may happen, but the idea is clear.)
3. For $\beta$ a limit ordinal, let $f_\beta=\bigcup_{\alpha<\beta}f_\alpha$.

Finally, we let $f=\bigcup_\beta f_\beta$, and this is an elementary embedding.

By this discussion, for a theory $T$, there is always a saturated model for some huge enough cardinal $\kappa^*$. Therefore we can technically choose a very very huuuuuge cardinal that will never be exceeded and denote the corresponding saturated model by $\mathcal{M}$. This is only for the convenience of discussion later and this is exactly what we call a monster model. By the way, since we do not concern the details of such a structure, the universe of it will always be denoted as $\mathcal{M}$.

Omitting types

Consider a set $A\in\mathcal{M}$, a set $\Sigma(\bar{x})$ of $L(A)$-formulas is called isolated over $A$ if there is an $L(A)$-formula $\varphi(\bar{x})$ which can be satisfied by $\mathcal{M}$ such that for any $\psi(\bar{x})\in\Sigma(\bar x)$,

$$\mathcal{M}\models\forall\bar{x}[\varphi(\bar{x})\rightarrow\psi(\bar x)].$$

If $\Sigma(\bar x)$ is a type, then we call this type isolated, and we say the type is generated by $\varphi(\bar x)$.

A remark can be given here that in most textbooks, the monster model in this definition is replaced by $T$, which means they use a relation of formulas modulo $T$ and call it “locally” isolated. But here we choose a convenient version.

We can claim that every isolated type $p(\bar x)$ can be satisfied by any model which contains the domain of $p(\bar x)$. Since $p(\bar x)$ can be satisfied by $\mathcal{M}$, there is $\bar a\in \mathcal{M}$ that satisfies $\varphi(\bar x)$, where $\varphi(\bar x)$ generates the type. Then, $\mathcal{M}\models\exists\bar x\,\varphi(\bar x)$. By the elementarity of any arbitrary model $\mathfrak{M}$ containing $A$, $\mathfrak{M}\models\exists\bar x\,\varphi(\bar x)$. Therefore some $\bar a\in M$ exists such that $\mathfrak{M}\models\varphi(\bar a)$. Hence $\mathfrak{M}\models p(\bar a)$.

That is to say, isolated types will never be omitted by any models of $T$. But how about those that are not isolated? The following theorem gives us an answer.

(Omitting Types Theorem) If $T$ is a countable theory and if the type $p(\bar x)$ is not isolated in $T$, then $T$ has a model which omits $p(\bar x)$.

To prove this, we recall the method called Henkin Theory which we previously used to prove the Compactness Theorem. A theory $T^*$ is called a Henkin theory if for each $L(C)$ formula $\varphi(x)$ there exists a $c\in C$ such that $\exists x\,\varphi(x)\rightarrow \varphi(c)\in T^*$. This is a powerful method to generate a model with some properties, because every Henkin Theory has a model (one can refer to chapter 2). We only have to sneak in some extra assumptions.

Therefore, we want to extend theory $T$ to a theory $T^*$ with the following properties,

1. $T^*$ is a Henkin Theory with Henkin constants $C$.
2. For each $c\in C$, there is a $\sigma(x)\in p(x)$ such that $\neg\sigma(c)\in T^*$.

We can construct this extension inductively and realize each assumption respectively in the even and odd cases. Take a countable set $C$ of new constants and enumerate it as $\{c_i\}_{i<\omega}$. Let $\{\psi_i\}_{i<\omega}$ be an enumeration of $L(C)$-formulas.

Let $T_0=T$. There is always some constant $c\in C$ that doesn’t appear in $T_0\cup\{\psi_0(x)\}$. Let $T_1=T_0\cup\{\exists x\,\psi_0(x)\rightarrow\psi_0(c)\}$. We can see the formula $\exists x\,\psi_0(x)\rightarrow\psi_0(c)$ as the form $\delta(c_0,\bar c)$ where $\delta(x,\bar y)$ is an $L$-formula and $\bar c$ is a tuple in $C$ not containing $c_0$. Since $\exists\bar y\,\delta(x,\bar y)$ doesn’t isolate $p(x)$, there is always a $\sigma(x)\in p(x)$ such that $\exists\bar y\,\delta(x,\bar y)\land\sigma(x)$ is consistent with $T$. Thus let $T_2=T_1\cup\{\neg\sigma(c_0)\}$.

Keep doing this, we have the formal steps.

1. If $T_{2i}$ is constructed, choose a constant $c\in C$ that doesn’t appear in $T_{2i}\cup\{\psi_i(x)\}$ and let $T_{2i+1}=T_{2i}\cup\{\exists x\,\psi_i(x)\rightarrow\psi_i(c)\}$.
2. If $T_{2i+1}$ is constructed, then it must be of the form $T\cup\{\delta(c_i,\bar c)\}$ where $\delta(x,\bar y)$ is an $L$-formula and $\bar c$ is a tuple in $C$ not containing $c_i$. Since $\exists\bar y\,\delta(x,\bar y)$ doesn’t isolate $p(x)$, there is always a $\sigma(x)\in p(x)$ such that $\exists\bar y\,\delta(x,\bar y)\land\sigma(x)$ is consistent with $T$. Thus let $T_{2i+2}=T_{2i+1}\cup\{\neg\sigma(c_i)\}$.

Finally we take $T^*=\bigcup_{i<\omega}T_i$. This is a Henkin theory. Hence a model $\mathfrak{A}$ exists and it can be a model of $T$ by simply forgetting the Henkin constants. And by the even steps, $p(x)$ is omitted in $\mathfrak{A}$.