0
$\begingroup$

In Goldrei's "Propositional and Predicate Calculus" Pg. 106 (Theorem 3.10), he offers the following: (If $\Gamma \models\theta$, then $\Gamma \vdash \theta$) $\leftrightarrow$ (If $\Delta$ is consistent, then $\Delta$ is satisfiable)

In proving from left to right, he aims to prove the contrapositve of the right side and goes on to say:

Suppose that $\Delta$ is not satisfiable ... Take any formula $\theta$. Then every truth assignament which satisifies $\Delta$ also satisfies both $\theta$ and $\lnot\theta$!! (Well, you cannot find a truth assignment which gives a couterexample to this last statement, as there aren't any assignments which satisfy $\Delta$!) Thus we have

$\Delta \models\theta$ and $\Delta\models\lnot\theta$

So by (C) we have {EDITOR: (C) refers to the left half of theorem, which has been assumed}

$\Delta \vdash\theta$ and $\Delta\vdash\lnot\theta$

which means that $\Delta$ is inconsistent, as required.

Doesn't the unsatisfiable part ($\models$) essentially mean a contradiction? It's not so much that $\Delta$ satisfies both (it can't satisfy anything by definition!), but rather it is the principle of explosion?

But for the contrapositive proof to complete, we have to actually be able to derive contradictions. My question was whether such a thing is actually possible (AND satisfy them!).

Unfortunately in my first version of this question, I had attempted to provide an example where this might fail, but I gave {$C\rightarrow D,D$} $\vdash C$, because I was also curious whether an invalid argument that has a satisfiable antecedent was also derivable (I wrote the question over a few days and conflated my thoughts). It was correctly pointed out that "$\Delta$" was indeed satisfiable, and as such a poor example for what was being asked. In retrospect this additional concern seems foolish; I think I (ironically) attempted to affirm the consequent, i.e. simply because $\Delta$ is satisfiable does not mean that it will be consistent (i might have been muddled by the contrapositive inverting their positions).

So, in which case, there's no magic here because $\Delta \vdash\theta$ and $\Delta\vdash\lnot\theta$ is just a case of $\Delta = P\land\lnot P$, and Goldrei should have avoided any talk of satisfying "both $\theta$ and $\lnot\theta$"...?

$\endgroup$
9
  • 1
    $\begingroup$ $\{ C → D, D \}$ is obviously satisfiable; thus, we cannot derive $⊥$. $\endgroup$ May 28, 2017 at 19:46
  • $\begingroup$ He is trying to prove that (C) implies (D) : "We shall prove one half of this and leave the other half as an exercise for you." Thus, the assumption is: "if $Γ \Vdash φ$, then $Γ \vdash φ$" and he proves "if Δ is consistent, then Δ is satisfiable" proving its contrapositive. $\endgroup$ May 28, 2017 at 19:51
  • $\begingroup$ It is not true that $\{ C → D, D \} \vDash C$; try with $D$ true and $C$ false. Also $\{C → D, D \} \vDash ¬C$ does not hold: try with $C$ true and $D$ true. $\endgroup$ May 28, 2017 at 19:53
  • $\begingroup$ In the end, what is the question ? "Are there cases for $Γ⊭θ$, i.e. where not every model for $Γ$ satisfies $θ$ ?" Obviously YES. Consider as $Γ$ the set $\{ p,q,r \}$ and as $\theta$ a contradiction, like: $p \land \lnot p$. $\endgroup$ May 28, 2017 at 19:55
  • $\begingroup$ Maybe you have to check again Def page 74: "Let $Γ$ be a set of formulas and $φ$ a formula involving propositional variables in a set $P$. Then $φ$ is a logical consequence of $Γ$, when for all truth assignments $v$ on $P$, if $v(γ) = T$ for all $γ ∈ Γ$, then $v(φ) = T$." $\endgroup$ May 28, 2017 at 20:01

2 Answers 2

2
$\begingroup$

I'm a little confused: certainly the statement "$\{C\rightarrow D, D\}\vdash\perp$" is false in general (that is, depending on what $C$ and $D$ are). For instance, if $C$ and $D$ are each propositional atoms, then the truth assignment making $C$ and $D$ both true is a truth assignment satisfying $\{C\rightarrow D, D\}$ but (trivially) not $\perp$, so "$\{C\rightarrow D, D\}\models\perp$" is false, and by the soundness theorem this means that "$\{C\rightarrow D, D\}\vdash\perp$" is equally false.

This issue crops up again further down. You write:

"If we consider $\{C \rightarrow D, D\} \models C$ and $\{C \rightarrow D, D\} \models \neg C$, it is easy to see that $\{C \rightarrow D, D\}$ is unsatisfiable"

but in general neither $\{C \rightarrow D, D\} \models C$ nor $\{C \rightarrow D, D\} \models \neg C$ is true!

This is a major issue, and I suspect it accounts for the confusion here.

$\endgroup$
1
  • $\begingroup$ @NoahScweber yes, there was indeed a huge confusion (on my part) related to the example as you highlighted (see my response to Mauro above). I have updated my question as a result. $\endgroup$
    – Lugh
    May 29, 2017 at 1:19
0
$\begingroup$

There was an error in the original question as pointed out by Noah and Mauro. The answer to the (updated) question can be found in the comments, which I am posting here so that I can close the question.

Answer: "Doesn't the unsatisfiable part (⊨) essentially mean a contradiction?" YES; the gist of the proof is exactly to equate "unsatisfiable" (which is a semantic concept) with "inconsistent" (which is a syntactical concept). A set of formulas is unsatisfiable iff it is inconsistent.

"$\Delta\vdash\theta$ and $\Delta\vdash\lnot\theta$ is just a case of $\Delta$ = P $\land\lnot P$" NO; obviously, if $\Delta\vdash\theta$ and $\Delta\vdash\lnot\theta$, by the rules of the calculus we have also $\Delta\vdash \theta \land\lnot \theta$, but not necessarily an inconsistent set of formulas mut be (or include) a single formula P $\land\lnot P$.

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