0
$\begingroup$

As mentioned in the title. I need to show that

$S \vdash A$ when I know that $S \cup \{ \neg A \} \vdash B$

And I can't use completeness theorem here.

I know I can say

$S \vdash \neg A \rightarrow B$

due to what we know. However I don't see how thats helpful. I have also tried to show that $S \cup \{ \neg A \}$ is inconsitent by trying to deduct $\neg B$ or A from it but no success thus far.

Edit.

Just to make sure this is bit more clear as I think the initial version might be bit messy.

So let S be a group of propositional formulas and A a propositional formula. Lets assume that for all propositional formulas B, $S \cup \{ \neg A \} \vdash B$. Now show without completeness theorem that $S \vdash A$.

$\endgroup$
  • 1
    $\begingroup$ It is not true... You have to check $B$: maybe it must be different ($\bot$ ?). $\endgroup$ – Mauro ALLEGRANZA Mar 4 '17 at 18:43
  • $\begingroup$ Are you aware of the definition of inconsistent set $S$ of formulas ? $\endgroup$ – Mauro ALLEGRANZA Mar 4 '17 at 18:48
  • $\begingroup$ What you mean by 'check B'? Also I assume I am familiar with definition of inconsistent set S of formulas but not entirely sure as English is not my native language. $\endgroup$ – E.K. Mar 4 '17 at 18:52
  • $\begingroup$ Take $S=\varnothing$ and $B=\lnot A$, then easily $S\cup\{\lnot A\}\vdash B$, but unless $A$ is a tautology, $S$ cannot prove $A$. $\endgroup$ – Asaf Karagila Mar 4 '17 at 19:22
  • 1
    $\begingroup$ @E.K.: What was missing was the "for all propositional formulas $B$" part. $\endgroup$ – Clive Newstead Mar 4 '17 at 19:33
2
$\begingroup$

A theory proves all propositional formulas if and only if it is inconsistent. As such, the assumption that $S \cup \{ \neg A \} \vdash B$ for all formulae $B$ implies that $S \cup \{ \neg A \}$ is inconsistent. Now either $S$ is consistent or it is inconsistent:

  • If $S$ is inconsistent, then $S \vdash A$.
  • If $S$ is consistent then so is $S \cup \{ C \}$ for any $C$ for which $S \vdash C$. Since $S \cup \{ \neg A \}$ is inconsistent, it follows that $S \nvdash \neg A$, so that $S \vdash A$ by completeness.

In either case we see that, $S \vdash A$.

$\endgroup$
  • $\begingroup$ Been reading this answer and some materials and while this is obviously correct answer I think this could be done little bit more efficient by using some theorems. We have a theorem which says the following are equivalent 1) $S \vdash A$ 2) $S \cup \{\neg A\}$ is inconsistent. If we use this wouldn't the second case be unnecessary? $\endgroup$ – E.K. Mar 6 '17 at 11:23
  • $\begingroup$ @E.K. Yes, if you have already proved that then there's no need to re-prove it in your proof of this result $\endgroup$ – Clive Newstead Mar 6 '17 at 11:56

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.