6
$\begingroup$

I read this answer, but was a bit confused by one of the deductions. It is stated that for some first-order theory $\Gamma$ and statement $\phi$:

If $\Gamma$ is consistent and $\Gamma\not\vdash\phi$, then $\Gamma\cup\{\neg\phi\}$ is also consistent.

This looks natural at first, and the author stated that this is by definition. But for me it is far from obvious that $\neg\phi$ cannot be used to deduce $\phi$ when combined with the other axioms in $\Gamma$. Can someone explain? Am I missing some definition or an obvious point?

$\endgroup$
2
  • 1
    $\begingroup$ See also this answer. $\endgroup$
    – user170039
    Dec 25 '17 at 16:26
  • 2
    $\begingroup$ Your assumption is redundant, since if $\Gamma\not\vdash\phi$, then $\Gamma$ must be consistent. $\endgroup$
    – JDH
    Dec 25 '17 at 19:29
5
$\begingroup$

I came across a solution while writing the question when the key word Deduction Theorem popped up in the side bar. This was not as trivial (for me) as initially assumed. So I decided to give a self-answer, but I am open for answers which show that this may be far more obvious. Especially the "by definition" part in the mentioned answer seems to me like an over-simplification now.


The Deduction Theorem states

If $\Gamma\cup\{\phi\}\vdash\psi$, then $\Gamma\vdash \phi\to\psi$.

Using this result, we can justify the deduction in question.

Assume $\Gamma\cup\{\neg\phi\}$ is inconsistent and therefore proves $\phi$. The Deduction Theorem gives that we can conclude $\Gamma\vdash \neg\phi\to\phi$. This latter statement is equivalent to $\phi\lor\phi$ $-$ or simply $\phi$. So there is a proof of $\phi$ from $\Gamma$ alone. $\;\square$

$\endgroup$
1
  • 1
    $\begingroup$ Indeed it cannot be by definition; the author probably meant "by supposition" rather than "by definition". Anyway if $Γ \cup {\neg φ}$ is inconsistent then it proves $\bot$ and hence by the deduction theorem $Γ$ proves $\neg φ \to \bot$, which is intuitionistically equivalent to $\neg \neg φ$. Only if you have double-negation-elimination will that entail $φ$. $\endgroup$
    – user21820
    Dec 26 '17 at 14:07
3
$\begingroup$

Please note that you are asking two different questions here.

At some point you ask why you wouldn't be able to deduce $\phi$ when adding $\neg \phi$ to $\Gamma$...and how the author of the post you are referring to shows that 'by definition'. Well, the definition used here is that a set of statements is consistent if and only there is no statement such that that statement as well as the negation of that statement can be derived from that set of statements. Hence, since it is obvious that $\neg \phi$ can be derived from $\Gamma \cup \{ \neg \phi \}$, then the consistency of $\Gamma \cup \{ \neg \phi \}$ implies that $\phi$ cannot be derived from $\Gamma \cup \{ \neg \phi \}$, let alone from $\Gamma$ alone.

Ok, but note that the latter result is the converse of what you ask earlier in your post, and what you ask of in the title of your post and, for that matter, what the author should have argued for, which is that if $\Gamma \not \vdash \phi$ then $\Gamma \cup \{ \neg \phi \}$ is consistent. Indeed, it is likely that you are confused about the Answer you are referring to since it is in fact not a good answer to the question that was asked there. Ok, so then how do you show what needs to be shown? Well, see the answer by @M.Winter for one good answer!

$\endgroup$
2
  • $\begingroup$ Doesn't this prove the opposite direction than asked: if $\Gamma\cup\{\neg\phi\}$ is consistent, then $\Gamma\not\vdash\phi$? $\endgroup$
    – M. Winter
    Dec 25 '17 at 16:58
  • $\begingroup$ @M.winter I answered the OP's question why '$\neg \phi$ cannot be used to deduce $\phi$ when combined with the other axioms in $\Gamma$'. Which, by the way, is also what the answer argues that the OP was confused about. But you're right, that is different from showing what that Answer should have shown, which is that if $\Gamma \not \vdash \phi$ then $\Gamma \cup \{ \neg \phi \}$ is consistent $\endgroup$
    – Bram28
    Dec 25 '17 at 17:28
2
$\begingroup$

Note that the above argument use nonconstructive law of reductio ad absurdum:

Let $X\cup\{\neg\varphi\}$ be an inconsistent set of formulas. Then $X\cup\{\neg\varphi\}\vdash\varphi $, so Deduction Theorem gives: $X\vdash\neg\varphi\rightarrow\varphi $. But reductio ad absurdum $(\neg\varphi\rightarrow\varphi)\rightarrow \varphi $ is clasically valid, so by Modus Ponens, $X\vdash\varphi $. $\blacksquare$

This theorem is not true in Intuitionistic Logic. Indeed, $\not\vdash_{INT}p\vee\neg p$, but $\{\neg(p\vee\neg p)\}$ is inconsistent:

suppose that there is a finite Kripke model $K$, and a world $x\in K$, such that $x\Vdash \neg(p\vee\neg p)$. Then taking a maximal element $y$ over $x$, we have $y\not\Vdash p\vee\neg p$, which is mpossible. $\blacksquare$

In Intuitionistic Logic the weaker form holds: If $X\cup\{\varphi\}$ is inconsistent, then $X\vdash_{INT}\neg\varphi $.

$\endgroup$
2
  • 2
    $\begingroup$ Thank you very much for this intuitionistic view on the topic! But do you mean "$\{\neg(p\lor \neg p)\}$ is inconsistent"? $\endgroup$
    – M. Winter
    Dec 26 '17 at 14:04
  • $\begingroup$ Of course, thanks $\endgroup$ Dec 26 '17 at 16:41

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.