Henkin's Theorem

At this point, then, our task has reduced to that of establishing 4.1. Our strategy will be to show, first, that every set having the two properties

• being maximally consistent; and
• containing witnesses

is satisfiable. The second part of the strategy is to show that every consistent set can be augmented to become a set having these two properties.

So, what is maximally consistency? The concept is the same here as it was in our chapter on propositional languages: a set $\Gamma^\star$ is maximally consistent iff it's consistent, and every formula $\phi$ consistent with $\Gamma^\star$ is in $\Gamma^\star$. The concept of containing witnesses, however, is new. Here is the definition.

Definition 4.8   A set $\Gamma$ contains witnesses iff for every formula of the form $\exists x \phi$ there exists a term t such that

$$(\exists x \phi \rightarrow \phi^t_x) \in \Gamma,$$

where $\phi^t_x$ is the result of replacing the variable x in $\phi$ with t.

Now here is a lemma (currently left as an exercise for the reader) that will prove indispensable.

Lemma 4.1   Let $\Gamma^\star_w$ be maximally consistent and contain witnesses. Then, for $\phi$ and $\psi$:

(a)

If $\Gamma^\star_w \vdash \phi$, then $\phi \in \Gamma^\star_w$.

(b)

Either $\phi \in \Gamma^\star_w$ or $\neg\phi \in \Gamma^\star_w$.

(c)

$(\phi \vee \psi) \in \Gamma^\star_w$ iff $\phi \in \Gamma^\star_w$ or $\psi \in \Gamma^\star_w$

(d)

If $(\phi \rightarrow \psi) \in \Gamma^\star_w$ and $\phi \in \Gamma^\star_w$, then $\psi \in \Gamma^\star_w$.

(e)

$\exists x \phi \in \Gamma^\star_w$ iff there is a term t such that $\phi^t_x \in \Gamma^\star_w$.

Now we proceed to define a Henkin interpretation $\cal I$$^\star_w$ = $(\mbox{$\cal U$ }^\star_w, \varphi^\star_w)$, which will have the property that

$$\mbox{$\cal I$}^\star_w \models \phi \mbox{ iff } \phi \in \Gamma^\star_w.$$

Our first step is to introduce a binary relation $\sim$ on the set of all terms T^S that can be generated from a given symbol set S:

$$t_1 \sim t_2 \mbox{ iff } t_1 = t_2 \in \Gamma^\star_w.$$

It is relatively easy to prove

Lemma 4.2  

(a)

$\sim$ is an equivalence relation.

(b)

If

$$t_1 \sim t_1', \ldots, t_n \sim t_n'$$

then for n-ary $f \in S$,

$$f(t_1, \ldots, t_n) \sim f(t_1', \ldots, t_n'),$$

and for n-ary $R \in S$,

$$Rt_1 \ldots t_n \in \Gamma^\star_w \mbox{ iff } Rt_1' \ldots t_n' \in \Gamma^\star_w.$$

We denote the equivalence class of term t by $\bar{t}$, where

$$\bar{t} = \{ t' \in T^S : t \sim t' \}.$$

And let the domain $T^\star_w$ of $\cal I$$^\star_w$ be the set of all equivalence classes, i.e.,

$$T^\star_w = \{ \bar{t} : t \in T^S \}.$$

The structure $\cal U$$^\star_w$ is defined on $T^\star_w$ as follows.

$$\mbox{For } n{\mbox -ary } \; R \in S, \; R^{\mbox{$\cal U$ ... ...ots \bar{t_n} \mbox{ iff } Rt_1 \ldots t_n \in \Gamma^\star_w$$ (4.3)

$$\mbox{For } n{\mbox -ary } \; f \in S, \; f^{\mbox{$\cal U$ ... ..._w}(\bar{t_1} \ldots \bar{t_n}) = \overline{f(t_1 \ldots t_n)}$$ (4.4)

$$c^{\mbox{$\cal U$ }^\star_w} = \bar{c}$$ (4.5)

$$\beta^{\mbox{$\cal U$ }^\star_w}(x) = \bar{x}$$ (4.6)

Lemma 4.3  

(a)

For all t, $\cal I$ $^\star_w(t) = \bar{t}$.

(b)

For every atomic formula $\phi$,

$$\mbox{$\cal I$}^\star_w \models \phi \mbox{ iff } \phi \in \Gamma^\star_w.$$

Theorem 4.2 (Henkin's Theorem)   Let $\Gamma^\star_w$ be a maximally consistent set containing witnesses. Then for all $\phi$,

$$\mbox{$\cal I$}^\star_w \models \phi \mbox{ iff } \phi \in \Gamma^\star_w.$$

Proof. The proof is by induction on the rank of $\phi$.^4.3 If rank($\phi$) = 0, then $\phi$ is atomic, and the theorem holds by Lemma 4.3. The induction step divides into three separate cases.

1.

$\phi = \neg \psi$. In this case

$$\mbox{$\cal I$}^\star_w \models \neg\psi \mbox{ iff not } \mbox{$\cal I$}^\star_w \models \psi.$$

By the induction hypothesis we get

$$\mbox{ iff } \psi \not\in \Gamma^\star_w.$$

But then (why?) we have

$$\mbox{ iff } \neg\psi \in \Gamma^\star_w.$$

2.

$\phi = (\phi \vee \chi)$. (For now, omited.)

3.

$\phi = \exists x \psi$. (For now, omited.)

Corollary 4.1   $\cal I$ $^\star_w \models \Gamma^\star_w$. Hence $\Gamma^\star_w$ is satisfiable.