1
$\begingroup$

Let Σ be a subset of Wp such that for some wff a, Σ |= a and Σ |= ¬a. How do I prove that Σ |= b for all b in Wp?

I understand that a and ¬a will be satisfied when Σ is satisfied but I'm not sure how to go from there.

$\endgroup$
  • 1
    $\begingroup$ If $\Sigma \vDash A$ and $\Sigma \vDash \lnot A$, this means that there is no valuation that satisfy $\Sigma$. Obvious from the definition: $\Sigma \vDash \lnot A$ iff $\Sigma \nvDash A$. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '17 at 13:48
  • 1
    $\begingroup$ Apply this to show $\Sigma \vDash B$ by contradiction. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '17 at 13:49
  • $\begingroup$ I still don't understand, could you explain it a little bit more. $\endgroup$ – Sasha Sep 27 '17 at 13:52
  • 1
    $\begingroup$ If a valuation $v$ satisfies $A$ (i.e. $v \vDash A$) it cannot satisfy also $\lnot A$, and vice versa. Thus the assertion that $\Sigma \vDash A$ and $\Sigma \vDash \lnot A$ amounts to asserting that $\Sigma$ is unsatisfiable, i.e. that there is no valuation $v$ satisfying $\Sigma$. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '17 at 13:55
  • 1
    $\begingroup$ We want to prove vthat $\Sigma \vDash B$, for $B$ whatever. Assume not: i.e. there is a valuation $v$ such that $v$ satisfies $\Sigma$ and $v$ does not satisfy $B$. But we have concluded that there is no valuation that satisfies $\Sigma$; thus there is no valuation that satisfies $\Sigma$ and in addition does not satisfy $B$. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '17 at 13:58
2
$\begingroup$

From comments by user Mauro ALLEGRANZA:

If $\Sigma \models A$ and $\Sigma \models \neg A$, this means that there is no valuation that satisfy $\Sigma$.

Apply this to show $\Sigma \models B$ by contradiction.

$\endgroup$
  • 1
    $\begingroup$ Glad to see Mauro's comments are made into an answer! Mauro often gives excellent comments that really should be an answer. $\endgroup$ – Bram28 Sep 27 '17 at 14:52
1
$\begingroup$

EDIT: the argument below is semantic - it uses valuations, and ultimately relies on the completeness theorem. A purely syntactic argument would be to show how your specific proof system can produce a proof of $\varphi$ from $\Sigma$ if $\Sigma\vdash a$ and $\Sigma\vdash\neg a$. The details here will depend on your specific proof system (this is one reason why semantic arguments are often better than syntactic arguments), but a rough outline that you can fill in yourself is as follows:

  • Since $\Sigma\vdash a$ and $\Sigma\vdash\neg a$, we have $\Sigma\vdash a\wedge\neg a$. ($\wedge$ rules)

  • Since $\Sigma\vdash a\wedge\neg a$, we also have $\Sigma\cup\{\neg \varphi\}\vdash a\wedge\neg a$. (monotonicity)

  • Now the whole key to this problem is that you should have a rule for proof by contradiction: this will say that if $\Sigma\cup\{\neg\varphi\}\vdash a\wedge\neg a$, then $\Sigma\vdash\varphi$. How transparent this will be will depend on your proof system: some systems have this built in as an inference rule directly, while others will make it harder to prove. Without knowing your specific proof system, I can't give more help; but hopefully this gets you to the point where you can see where to go on your own.


Remember that the claim "$\Sigma\not\vdash\varphi$" is existential$^1$ - it says that there is some valuation making $\Sigma$ true but making $\varphi$ false. In particular, in order to have $\Sigma\not\vdash\varphi$ we need some valuation making $\Sigma$ true.

Now, if $\Sigma\vdash a\wedge\neg a$, what can you say about valuations making $\Sigma$ true? (This is going to boil down to the notion of vacuous truth: that certain kinds of statements are true for a "silly" reason. It might help to think first about the sentence: "every flying pink elephant is on fire." Is this statement true or false? Remember, since it's a universal statement, if it's false there has to be a counterexample ...)


$^1$This is the whole point of the Completeness Theorem! On the face of it, "$\Sigma\not\vdash\varphi$" is a universal claim: it says that there does not exist a proof of $\varphi$ from $\Sigma$. But by the Completeness Theorem, we get another way to describe when $\Sigma\not\vdash\varphi$ holds - namely, in terms of valuations.

$\endgroup$
  • $\begingroup$ There are none, how could a∧¬a ever be satisfied? $\endgroup$ – Sasha Sep 27 '17 at 13:53
  • $\begingroup$ @Sasha Exactly. So a universal statement about things that don't exist is what? (HINT: think about the sentence "Every flying pink elephant is on fire.") $\endgroup$ – Noah Schweber Sep 27 '17 at 13:54
  • $\begingroup$ is there any way to do this without completeness theorem? I haven't touched upon that yet. $\endgroup$ – Sasha Sep 27 '17 at 13:55
  • $\begingroup$ @Sasha Do you know that if every valuation making $\Sigma$ true also makes $\varphi$ true, then $\Sigma\vdash \varphi$? That's what we're using here. $\endgroup$ – Noah Schweber Sep 27 '17 at 13:56
  • $\begingroup$ yes ok, that makes sense. $\endgroup$ – Sasha Sep 27 '17 at 13:58
0
$\begingroup$

Suppose there is some $b$ such that $\Sigma \not \models b$. Then there is some valuation $\tau$ such that $\forall \sigma \in \Sigma \colon \sigma[\tau]$ and $\neg b[\tau]$. However, since $\Sigma \models a$ and $\Sigma \models \neg a$ we must have $a[\tau]$ and $\neg a[\tau]$ - a contradiction!

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