6
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry I don't quite understand what you meant in your first 2 paragraphs...would you mind elaborating a bit please? Are you saying that, since $\psi_0 \not\in \Gamma$ and $\psi_1 \not\in \Gamma$, and $\Gamma$ is defined without the maximal property (ie. not specified that either $\psi$ or $\lnot\psi$ must be in $\Gamma$), in your example it is possible that $\Gamma$ is unsatisfiable? $\endgroup$ – Daniel Mak Aug 15 '18 at 5:35
  • $\begingroup$ @DanielMak No. What I'm saying is this: the process the OP describes, for building $\nu$ in terms of $\Gamma$, is flawed since it may be the case that $\nu$ does not in fact make $\Gamma$ true (the whole goal is for $\nu$ to witness that $\Gamma$ is satisfiable). It's not that $\Gamma$ might be unsatisfiable, it's that $\nu$ itself might (indeed, in my example does) fail to satisfy $\Gamma$. (Do you see why $\nu$ - built from $\Gamma$ as the OP describes - makes both $\psi_0$ and $\psi_1$ false, and hence does not make $\Gamma$ true?) $\endgroup$ – Noah Schweber Aug 16 '18 at 17:54
0
$\begingroup$

I usually think about this theorem in terms of the contrapositive. The completeness is equivalent to:

$$ \Gamma \not\vdash \varphi \Longrightarrow \Gamma \not\vDash \varphi$$

So $\Gamma$ doesn't need to be consistent, but rather non-trivial with respect to $\varphi$ - that is, you can just assume it not to derive $\varphi$. This is a standard argument in non-classical logics dealing with contradictory yet non-trivial systems.

Then you strive to prove that such $\Gamma$ can be maximally extended to some $\Gamma'$ such that also $\Gamma' \not \vdash \varphi$ and expect to be able to obtain a model of $\Gamma'$, which will be a model of $\Gamma$ also. By the maximality of $\Gamma'$, $\varphi$ cannot be satisfied by this model.

You can think of the maximality of $\Gamma'$ as both a way to set the truth of all sentences (there cannot be room for ambiguities in any model) and to enforce the model obtained not to satisfy $\varphi$, as this would imply that $\Gamma' \vdash \varphi$.

I'm being vague on purpose, as this argument can be used also for non-classical logics and the exactly nature of model and satisfaction would vary.

$\endgroup$

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.