3

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.

Ali Caglayan
  • 5,726
Covi
  • 819
  • Can you say more about how you've tried to construct the syntactic proof? – Carl Mummert Nov 12 '14 at 17:53
  • 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. – Covi Nov 12 '14 at 17:55
  • 1
    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. – Carl Mummert Nov 12 '14 at 17:57
  • Interesting, I thought one was "varphi" and the other was "phi". Anyway, I edited one of the symbols. – Covi Nov 12 '14 at 17:57
  • 1
    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. – Carl Mummert Nov 12 '14 at 17:58

2 Answers2

2

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 :

$Γ⊢φ$.

Mauro ALLEGRANZA
  • 94,169
-1

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

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