7
$\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$

2 Answers 2

9
$\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$
7
  • $\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$ Aug 15, 2018 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$ Aug 16, 2018 at 17:54
  • $\begingroup$ If a theory proves or disproves every atom, then is its deductive closure complete? If true that also may give some intuition. $\endgroup$ Apr 16, 2022 at 12:01
  • $\begingroup$ @VoiletFlame Yes, that's true. $\endgroup$ Apr 16, 2022 at 12:28
  • $\begingroup$ I suppose my question is: What is the intuition in using complete/maximally consistent sets in the henkin proof of completeness. $\endgroup$ Apr 16, 2022 at 14:05
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .