# How can a set tautologically imply every wff?

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.

• 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$. – Mauro ALLEGRANZA Sep 27 '17 at 13:48
• Apply this to show $\Sigma \vDash B$ by contradiction. – Mauro ALLEGRANZA Sep 27 '17 at 13:49
• I still don't understand, could you explain it a little bit more. – Sasha Sep 27 '17 at 13:52
• 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$. – Mauro ALLEGRANZA Sep 27 '17 at 13:55
• 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$. – Mauro ALLEGRANZA Sep 27 '17 at 13:58

## 3 Answers

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.

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

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.

• There are none, how could a∧¬a ever be satisfied? – Sasha Sep 27 '17 at 13:53
• @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.") – Noah Schweber Sep 27 '17 at 13:54
• is there any way to do this without completeness theorem? I haven't touched upon that yet. – Sasha Sep 27 '17 at 13:55
• @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. – Noah Schweber Sep 27 '17 at 13:56
• yes ok, that makes sense. – Sasha Sep 27 '17 at 13:58

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!