If $\Gamma \cup \{ \neg \varphi \}$ is inconsistent, then $\Gamma \vdash \varphi$

Here, a set of formulas is inconsistent means they syntactically imply some formula as well as its negation. Syntactic implication here consists of (1) given formulas, (2) all first-order logical axioms, (3) modus ponens.

I have tried to explicitly construct a syntactic proof for the conclusion but failed to come up with one.

  • $\begingroup$ Can you say more about how you've tried to construct the syntactic proof? $\endgroup$ – Carl Mummert Nov 12 '14 at 17:53
  • $\begingroup$ For instance, my progress includes showing $\Gamma \vdash \neg \varphi \rightarrow \psi$, and $\Gamma \vdash \neg \varphi \rightarrow \neg \psi$ for some formula $\psi$. But I don't see how to make $\neg \varphi$ disappear and/or tie it to the conclusion. Also, I can prove $\Gamma \cup \{ \neg \varphi \} \vdash \varphi$, but this proof sequence may make use of $\neg \varphi$ somewhere. $\endgroup$ – Covi Nov 12 '14 at 17:55
  • 1
    $\begingroup$ In any case, you've proved that $\Gamma \vdash \lnot \phi \to (\theta \land \lnot \theta)$. So $\Gamma$ will also prove the contrapositive of that conclusion; try writing out the contrapositive. $\endgroup$ – Carl Mummert Nov 12 '14 at 17:57
  • $\begingroup$ Interesting, I thought one was "varphi" and the other was "phi". Anyway, I edited one of the symbols. $\endgroup$ – Covi Nov 12 '14 at 17:57
  • 1
    $\begingroup$ In Latex, they are "varphi" and "phi", but that's somewhat analogous to the difference between an italic "$a$" and an upright "a" - it is jarring to see them used to mean different things in the same equation. Try the contrapositive thing I mentioned, and see if you can get that. If so, the way this site works, you'd be welcome to write it up an an answer to your own question. $\endgroup$ – Carl Mummert Nov 12 '14 at 17:58

You need the axiom (or tautology) :

$\vdash (¬φ→¬ψ)→((¬φ→ψ)→φ)$.

Having already proved :

if $Γ∪{¬φ}$ is inconsistent, then $Γ⊢¬φ→ψ$ and $Γ⊢¬φ→¬ψ$,

it is enough to aplly modus ponens twice to conclude with :



Suppose $\Gamma\cup\{\neg\alpha\}$ is inconsistent. Then for some $\beta$ we have $\Gamma\vdash\beta$ and $\Gamma\vdash\neg\beta$. It remains only to show that $\{\beta,\neg\beta\}\vdash\alpha$.

  • 1
    $\begingroup$ This was already mentioned in the comments. But also in the second sentence the $\Gamma$ should be $\Gamma + \lnot \alpha$; $\Gamma$ may be consistent. $\endgroup$ – Carl Mummert Nov 12 '14 at 18:01

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.