Omitting Types Theorem

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal{L}$ be a countable language.

Let $T$ be an $\mathcal{L}$-theory.

Let $\{p_i : i \in \N \}$ be a countable set of non-isolated $n$-types of $T$.


There is a countable $\mathcal{L}$-structure $\mathcal{M}$ such that $\mathcal{M}\models T$ and $\mathcal{M}$ omits each $p_i$.


Proof

This proof is done by constructing a model using a method known as a Henkin construction, which results in a model all of whose elements are the interpretations of constant symbols from some language. The construction for this proof in particular is done so that the theory this model satisfies asserts that each tuple of constants fails to satisfy at least one $\phi$ from each type $p_i$. As a result, the model we construct will not realize any of the types.


We will prove the theorem for the special case where we only omit one type. That is, assume $\{p_i : i \in \N\}$ is $\{p\}$ for some $p$.

Comments on the general case will be made after the proof.


Our goal is to eventually be able to apply Maximal Finitely Satisfiable Theory with Witness Property is Satisfiable to a suitable $\mathcal{L}^*$-theory $T^*$, where $\mathcal{L}^*$ contains $\mathcal{L}$ and $T^*$ contains $T$.

Let $\mathcal{L}^*$ be $\mathcal{L} \cup \{c_i : i \in \N\}$ where each $c_i$ is a new constant symbol. Note that $\mathcal{L}^*$ is still countable.

We will recursively construct $T^*$ by adding a sentence $\theta_k$ at each stage. In order to ensure that it has the necessary properties, we will construct it in stages, each of which has three steps. The goal of the first step of each stage is ensure that $T^*$ will be maximal upon completion of the definition. The goal of the second step of each stage is to ensure that $T^*$ will satisfy the witness property. The goal of the third step of each stage is to ensure that $p$ is not realized by any tuple of constants.


Since $\mathcal{L}^*$ is countable, the set of $\mathcal{L}$-formulas is countable, and hence in particular, the $\mathcal{L}^*$-sentences can be listed as $\phi_0, \phi_1, \dots$

Similarly, since $\mathcal{L}^*$ is countable, the set of $n$-tuples of its constant symbols can be listed as $\bar{d}_0, \bar{d}_1, \dots$


Recursive definition of $T^*$

We now recursively define sets $T_k$ whose union will be $T^*$.


  • Stage $k=0$:

Let $\theta_0$ be any $\mathcal{L}$-sentence which is a tautology; for example, $\forall x (x=x)$.

Let $T_0 = T\cup \{\theta_0\}$.

Note that $T_0$ is satisfiable since $T$ is satisfiable, and $T\models \theta_0$ trivially.


Suppose that $\theta_k$ and $T_k$ have been defined and $T_k$ is satisfiable. We now handle the three steps of the $k$-th stage as mentioned above.


  • Stage $k+1 = 3i + 1$:

In this step we ensure that $T^*$ will be maximal.

If $T_k \cup \{\phi_i\}$ is satisfiable, let $\theta_{k+1}$ be $\phi_i$.

Otherwise, since $T_k$ is satisfiable, $T_k \cup \{\neg\phi_i\}$ must be satisfiable, and in this case we let $\theta_{k+1}$ be $\neg\phi_i$.

Let $T_{k+1} = T_k \cup \{\theta_{k+1}\}$.


  • Stage $k+1 = 3i + 2$:

In this step we ensure that $T^*$ will have the witness property.

Suppose that $T_k \models \phi_j$ for some set of $j\leq i$, and that $\phi_j$ are each of the form $\exists v \psi_j (v)$.

Let $\theta_{k+1}$ be $\bigwedge \psi(c)$ where $c$ is a new constant which doesn't appear in $T_k$. This is possible since $T_k$ only has finitely many $\mathcal{L}^*$-sentences which are not $\mathcal{L}$-sentences.

Let $T_{k+1} = T_k \cup \{\theta_{k+1}\}$.

Since $T_k$ is satisfiable and $T_k \models \bigwedge \exists v \psi_j (v)$, any model $\mathcal{M}$ of $T_k$ has an element $a_j$ such that $\mathcal{M} \models \psi_j (a_j)$. By interpreting $c_j$ as $a_j$, we can view $\mathcal{M}$ as a model of $T_{k+1}$.

Thus $T_{k+1}$ is satisfiable.

If $T_k$ doesn't satisfy any existential statements $\phi_j$ for $j\leq i$, let $\theta_{k+1}$ be $\theta_k$ and let $T_{k+1}$ be $T_{k}$.


  • Stage $k+1 = 3i + 3$:

In this step we ensure that $p$ will be omitted by any model of $T^*$.

Let $(e_1,\dots,e_n)$ be the $i$-th $n$-tuple of constants $\bar{d}_i$. We will add a sentence to ensure that $\bar{d}_i$ fails to realize $p$.

Let $\psi$ be the $\mathcal{L}$-formula obtained from $\theta_0 \wedge \cdots \theta_k$ by

  1. replacing occurrences of the constants $e_1,\dots,e_n$ with variables $v_1,\dots,v_n$,
  2. replacing occurrences of $c_i$ besides $e_1,\dots,e_n$ by variables $v_{c_i}$ other than $v_1,\dots,v_n$, and finally
  3. adding an existential quantifier $\exists v_{c_i}$ for each of the $c_i$ that were replaced other than $e_1,\dots,e_n$.

This results in $\psi$ being an $\mathcal{L}$-formula with $n$ free variables. The free variables are those that correspond to the $e_i$.

Since $p$ is not isolated, there must be some $\phi \in p$ such that $T\not\models \forall \bar v (\psi (\bar v) \to \phi (\bar v))$

Thus $T \models \exists \bar v (\psi(\bar v) \wedge \neg \phi(\bar v))$.

Let $\theta_{k+1}$ be $\neg \phi (\bar{d}_i)$.

Let $T_{k+1} = T_k \cup \{\theta_{k+1}\}$.

Since $T$ is satisfiable, it has a model $\mathcal{M}$. By the above, $\mathcal{M} \models \exists \bar v (\psi(\bar v) \wedge \neg \phi(\bar v))$. Hence, there is some tuple $\bar a$ in $\mathcal{M}$ such that $\mathcal{M} \models \psi(\bar a) \wedge \neg \phi(\bar a)$. By interpreting the constants $e_1,\dots, e_n$ as the constants in the tuple $\bar a$ and interpreting the constants $c_i$ other than $e_1,\dots,e_n$ as the elements from $\mathcal{M}$ which satisfy the existential quantifiers in $\psi(\bar a)$, we have that $\mathcal{M}$ can be viewed as a model of $\theta_0 \wedge \cdots \wedge \theta_k \wedge \neg\phi(\bar{d}_i)$ as well.

Thus $T_{k+1}$ is satisfiable.


Verification of properties of $T^*$

Now, let $\displaystyle T^* = \bigcup_{k \in \N} T_k$, or equivalently $T^* = T\cup \{\theta_k : k \in \N\}$.

We verify that $T^*$ is a maximal finitely satisfiable theory with the witness property so that we may apply the theorem that will construct our desired model.


  • $T^*$ is finitely satisfiable.

If $\Delta$ is a finite subset of $T^*$, then $\Delta$ is contained in one of the $T_k$, but by construction each $T_k$ was satisfiable, and hence by compactness $\Delta$ is satisfiable.


  • $T^*$ is a maximal theory.

If $\phi$ is an $\mathcal{L}^*$-sentence, then it is some $\phi_i$, and hence either $\phi$ or $\neg\phi$ is contained in $T_{3i + 1}$.


  • $T^*$ has the witness property.

Let $\psi(v)$ be an $\mathcal{L}^*$-formula with one free variable. Then $\exists v \psi (v)$ is an $\mathcal{L}^*$-sentence and hence is some $\phi_j$.

Suppose $T^*\models \exists v \psi(v)$.

There must be a finite subset $\Delta$ of $T^*$ such that $\Delta \models \exists v \psi(v)$, else by compactness, since $\Delta\cup \{\neg\exists v \psi(v)\}$ is always satisfiable, $T^* \cup \{\neg\exists v \psi(v)\}$ is satisfiable.

Since such a $\Delta$ must be contained in one of the $T_k$, there is some $T_k$ such that $T_k \models \exists v \psi(v)$.

Since each $T_k$ is contained in $T_{k+1}$, we can assume that $k$ is $3i+2$ for some $i\leq j$.

But, $T_{3i + 2}$ contains $\psi(c)$ for some constant $c$ since $j\leq i$ and $T_{3i+2}\models \phi_j$.


Verification that the constructed model omits $p$

Recall that $\mathcal{L}$ was assumed to be countable, and so $\mathcal{L}^*$ is countable as well.

Thus, by Maximal Finitely Satisfiable Theory with Witness Property is Satisfiable applied to $T^*$, there is an $\mathcal{L}^*$-structure $\mathcal{M}$ such that $\mathcal{M} \models T^*$, every element of $\mathcal{M}$ is the interpretation of one of the constant symbols from $\mathcal{L}^*$, and consequently $\mathcal{M}$ is at most countable.


We verify that $\mathcal{M}$ omits $p$. That is, every $n$-tuple of elements in $\mathcal{M}$ fails some sentence in $p$.


Let $(a_1,\dots,a_n)$ be an $n$-tuple of elements from $\mathcal{M}$.

Then each of $a_1,\dots,a_n$ is the interpretation of constant symbol $e_1,\dots,e_n$ respectively from $\mathcal{L}^*$. In turn, $(e_1,\dots,e_n)$ is one of the $\bar{d}_i$.

But, $T_{3i+3} \models \neg\phi(\bar{d}_i)$ for some $\phi \in p$.

Thus, $\mathcal{M}\models \neg \phi(a_1,\dots,a_n)$ for some $\phi \in p$.


Hence, $\mathcal{M}$ omits $p$.


Generalization to countable set of non-isolated types

The above proof can be generalized by extending stage $k+1 = 3i + 3$. As it is written above, we force $\bar{d}_i$ to fail to satisfy some $\phi$ in a single type $p$. But, if we list the pairs $\{(\bar{d}_\alpha, p_\beta) : \alpha,\beta \in \N\}$ as a set $\{\pi_i : i \in \N\}$ (which is possible since the set of such pairs is countable), then at stage $3i+3$, where $\pi_i = (\bar{d}_\alpha, p_\beta)$, we can force $\bar{d}_\alpha$ to fail to satisfy some $\phi$ in $p_\beta$, analogously to how it is done in the above proof. This ensures that for each $\bar{d}_\alpha$ with $\alpha\in\N$, and for each $p_\beta$, eventually some $T_k$ includes a sentence $\neg\phi(\bar{d}_\alpha)$ for some $\phi\in p_\beta$. That is, eventually some $T_k$ ensures that $\bar{d}_\alpha$ does not realize $p_\beta$.


$\blacksquare$