Satisfiability Proof Question

Question

Exercise: Prove that $\Gamma\models A$ iff $\Gamma\cup\{\neg A\}$ is not satisfiable.

Proof: We must prove two clauses:

1. $\Gamma\models A\Rightarrow \Gamma\cup\{\neg A\}$ is not satisfiable

2. $\Gamma\cup\{\neg A\}$ is not satisfiable $\Rightarrow\Gamma\models A$

Suppose (1) is not true. In such a case, we could make the following claim (by distributing the negation): $\Gamma\models A\text{ and }\Gamma\cup\{\neg A\}\text{ is satisfiable}$

This would require the existence of a valuation v where $v^{*}(A)=\text{T}$ and $v^{*}(\neg A)=\text{T}$ , or -- simplified -- $v^{*}(A)=\text{F}$ . But a sentence cannot be both T and F under the same valuation v of $\mathcal{L}$ , so (1) must be true.

Suppose now that (2) is not true. In such a case, we could make the following claim (by distributing the negation): $\Gamma\cup\{\neg A\}\text{ is not satisfiable}\text{ and }\Gamma\nvDash A$

Since $\Gamma\cup\{\neg A\}$ is not satisfiable, there must be some S where $S\in\Gamma$ , such that $\{S\}\cup\{\neg A\}$ is not satisfiable. For $\{S,\neg A\}$ to be unsatisfiable, S must be A . Trivially, then, $A\in\Gamma$ and so, $\Gamma\models A$. Therefore, (2) must be true. $\Diamond$

I only got 4/10 points for this proof and before I go to office hours I just wanted to ask if I did something obviously wrong/stupid (which might very well be the case). For what it's worth, here are my professor's notes: https://i.stack.imgur.com/4YN00.jpg

Answer 1

I'll prove (2) not by contradiction but by contraposition. Assume $\Gamma$ doesn't entail $A$. Then there is at least one valuation that makes every sentence in $\Gamma$ true but $A$ false. But this same valuation makes every sentence in $\Gamma\cup\left\{¬A\right\}$ true. So $\Gamma\cup\left\{¬A\right\}$ is satisfiable.

Answer 2

For statement (1), where your professor noted that you need to be more explicit with your arguments, I guess he meant that you should go by the definitions:

By definition, $\Gamma\models A$ means that there is a valuation $v$ such that if for all formulas $B\in \Gamma$, $v^*(B)=\text{T}$, then $v^*(A)=\text{T}$, too.

On the other hand, $\Gamma\cup\{\neg A\}$ being satisfiable means by definition that there is a valuation $u$ such that $u^*(\neg A)=\text{T}\Rightarrow u^*(A)=\text{F}$. But $u$ is a valuation for which $\forall B\in\Gamma, u^*(B)=\text{T}$, so it should also valuate A as true, but it doesn't. Hence the contradiction.

Answer 3

Your proof isn't clear at all.

On one hand, $\Gamma \models A$ means by definition that every every models of $\Gamma$ satisfies $A$. On the other hand, $\Gamma \cup \{\neg A\}$ not satisfiable means that there is no model of $\Gamma \cup \{\neg A\}$. So the exercise is completely trivial once you know that a model can not satisfies a formula and its negation.

If you want to write it, it goes as : $\Gamma \models A$ iff for every structure $\mathcal M$, $\mathcal M \models \Gamma$ implies $\mathcal M \models A$ iff there is no structure $\mathcal M$ such that $\mathcal M \models \Gamma$ and $\mathcal M \models \neg A$ iff $\Gamma \cup \{\neg A\}$ is not satisfiable.