Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable"

Question

Show that "$\Gamma \models S \Rightarrow \Gamma \vdash S$" entails "if $\Gamma \nvdash P \And \sim P$ then $\Gamma$ is satisfiable"

I'm primarily confused with the notation being used here. In particular, I understand that "satisfiable" means there is at least one interpretation that makes $\Gamma$ true, but I'm not sure what $\vdash$ means nor what the statement $\Gamma \models S \Rightarrow \Gamma \vdash S$ means. The first part tells me that $\Gamma$ "makes true" $S$, or that there is no interpretation which makes $\Gamma$ true and $S$ false, but I don't understand how to interpret what comes after this (the "$\Rightarrow \Gamma \vdash S$" part). I'd really appreciate if someone could clear up this notation for me.

Answer 1

So I think this is what we may want to do. Suppose for contradiction that $\Gamma$ is not satisfiable. This means that $\Gamma$ has no models. Now, fix some sentence $P$ and let $S \equiv P \wedge \neg P$. Now, $\Gamma \models S$ will be vacuously true since there are no models of $\Gamma$, (i.e. any model of $\Gamma$ will satisfy $S$). So by the hypothesis, we have that $\Gamma \vdash S$. But this means $\Gamma \vdash P \wedge \neg P$ contradicting the hypothesis that this does not happen.

Answer 2

$\Gamma \models S$ means 'Every model of $\Gamma$ satisfies wff $S$ ' So given statement can be written as follows:

For all wff $S$ on the language of $\Gamma$, if every model of $\Gamma$ satisfies $S$ then $\Gamma$ proves $S$.

Formally, this statement is written as $\forall S[ (\forall \mathcal{M} :\mathcal{M}\models \Gamma \implies \mathcal{M}\models S)\implies \Gamma\vdash S]$. Take contraposition of this statement then we get

For all wff $S$ on the language of $\Gamma$, if $\Gamma$ does not prove $S$ then there is a model of $\Gamma$ that does not satisfy $S$.

(Formally it is written as $\forall S [\Gamma \nvdash S \implies (\exists \mathcal{M} :\mathcal{M}\models\Gamma \,\&\, \mathcal{M}\not\models S)]$.)

Note that if $\mathcal{M}\not\models S$ then $\mathcal{M}\models(\lnot S)$. Take $S=P\land \lnot P$ then you get desired proposition.

Answer 3

The symbol :

$\Gamma \vDash S$

means that the sentence $S$ is a logical consequence of the set of sentences $\Gamma$.

This means, as said in the above comments :

every interpretation that satisfies all sentences $\varphi \in \Gamma$ (i.e. is a model of $\Gamma$), satisfies also $S$.

The symbol :

$\Gamma \vdash S$

means that the sentence $S$ is provable from the set of assumptions $\Gamma$.

This means that the problem implicitly assume that we have in place a proof system, made of (one or more) rules of inference and (zero o more) axioms and a definition of derivation; in this way, the symbol above is defined (as in the comment) as :

there is a finite set of sentences $\sigma_1, … ,\sigma_n$, where either: (i) $\sigma_i \in \Gamma$, or (ii) $\sigma_i$ is a logical axiom or (iii) $\sigma_i$ follows by a rule of inference from some (one or more) $\sigma_k$, where $1 \le k < i$ and $\sigma_n = S$.

Finally, the symbol :

$\Gamma \nvdash P \land \lnot P$

means that form $\Gamma$, with the proof system above, we can derive a contradiction, i.e. $\Gamma$ is inconsistent. So, we say that $\Gamma$ is consistent when it is not inconsistent (i.e.when we cannot derive a contradiction from it).

The statement of the problem boils down to :

show that if $\Gamma$ is consistent, then it is satisfiable.

Now, in order to prove it, procede as suggested by @Ryan Sullivant, i.e. by contradiction, and suppose that $\Gamma$ is not satisfiable. This means that $\Gamma$ has no models.

Now re-read the relation of logical consequence explained above : $\Gamma \vDash \varphi$ iff every model of $\Gamma$ is also a model of $\varphi$.

But we assumed that $\Gamma$ has no models; so the last condition is vacuosly satisfied for every $\varphi$, and also for $P \land \lnot P$.

This means that, if $\Gamma$ is not satisfiable, i.e. if it has no models, than :

$\Gamma \vDash P \land \lnot P$.

At this point, we need the theorem mentioned in the hypotheses of the problem :

if $\Gamma \vDash S$, then $\Gamma \vdash S$

(if $S$ is a logical conseuqnce of $\Gamma$, then $S$ is provable from $\Gamma$; we say that the proof system is complete).

Having proved, form the assumption that $\Gamma$ is unstaisfiable, that $P \land \lnot P$ is a logical consequence of $\Gamma$, we use the above theorem to conclude that $P \land \lnot P$ is provable form $\Gamma$.

In conclusion :

if $\Gamma$ is unsatisfiable, then $\Gamma$ is inconsistent.