Logic – Why Maximal Consistent Sets are Essential to Henkin-Proofs of Completeness

logic

As well-known, the Completeness theorem states that

$$\Gamma \vDash \varphi \Rightarrow \Gamma \vdash \varphi$$

The proof we find in didactic textbooks are usually called "Henkin-proofs". Let $\mathcal{L}$ be our referring language. A Henkin-proof (for propositional logic) goes more or less along the lines of

  1. Let $\Gamma$ be consistent.
  2. Extend $\Gamma$ to a maximal consistent set $\Delta$
  3. Show that $\Delta$ preserves consistency and that $\Gamma \subseteq \Delta$
  4. Define a valuation $v$ for $\Delta$ such that $v(\psi)=1$ iff $\psi \in \Delta$ for all atomic $\psi \in \mathcal{L}$

  5. Define $v$'s unique extension $\bar v$ as usual.

  6. Then $\bar v \vDash \Delta$ and, since $\Gamma \subseteq \Delta$,

  7. $\bar v \vDash \Gamma$.

Now my question is:

Why can't we just define $v$ using $\Gamma$ directly?

I'm obviously missing something, but why can't we simply forget the maximal consistent part? That is, for every atomic $\psi \in \mathcal{L}$, define:

$v(\psi) = \begin{cases}
1 & \text{if $\psi \in \Gamma$} \\
0 & \text{if $\psi \notin \Gamma$}
\end{cases}$

What is the problem with this definition? Is it that we don't know the elements of $\Gamma$? But if it is so, why wouldn't this apply to $\Delta$? In other words, what is the essential point of extending $\Gamma$ to a maximal consistent set?

Thanks in advance.

Best Answer

You give a method for producing a valuation, $\nu$, corresponding to a theory, $\Gamma$. This is well-defined, but $\nu$ might not make $\Gamma$ true! For instance: what happens if $\Gamma=\{\psi_0\iff\neg\psi_1\}$ for some atomic $\psi_0, \psi_1$? Then your valuation would make both $\psi_0$ and $\psi_1$ false, so $\Gamma$ would not hold!

Essentially, in the example above, we need to make a choice between making $\psi_0$ true and making $\psi_1$ true. The point of extending to a complete theory is exactly to make these sorts of choices.

In fact, if you prefer, we can phrase the argument in terms of making choices, instead of forming a completion. Given $\Gamma$, we list the atomic propositions as $\psi_0, \psi_1, . . .$; at stage $\alpha$, we have built a partial valuation $\nu_\alpha$ of the first $(\alpha-1)$-many atomic propositions. We then extent $\nu_\alpha$ to $\psi_\alpha$ as follows: $\nu_{\alpha+1}(\psi_\alpha)=1$ if for every finite subset $\Gamma_0$ of $\Gamma$, there is a valuation $\mu$ which makes $\Gamma_0$ true, extends $\nu_\alpha$ and such that $\mu(\psi_{\alpha})=1$; and we make $\nu_{\alpha+1}(\psi_\alpha)=0$ otherwise. If you unpack this, of course, this is really just forming a completion of $\Gamma$, but it might seem more intuitive.

Related Question