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

Question

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?

Answer 1

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$

Answer 2

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!

Answer 3

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