By the deduction theorem, if $Γ,A⊢B$, then $Γ⊢A→B$ .
But may I also conclude that if $$Γ,A⊬B,$$ then $$Γ⊬A→B \;?$$
Asked
Active
Viewed 87 times
3
-
2Sure. Proof by contrapositive. If $\Gamma \vdash A \rightarrow B$, then by monotonicity $\Gamma, A \vdash A \rightarrow B$, and by closure under the inference rules you can conclude $\Gamma, A \vdash B$. – Z. A. K. Sep 28 '21 at 16:39
-
Awesome, thank you! – Pascal Meier Sep 28 '21 at 17:46
2 Answers
2
Yes. The deduction theorem is actually a biimplication: $$\Gamma, A \vdash B \iff \Gamma \vdash A \to B$$ The non-derivability biimplication then straightforwardly follows as the contraposition of each of the directions: $$\Gamma \not \vdash A \to B \iff \Gamma, A \not \vdash B$$
Natalie Clarius
- 10,530
0
$$Γ,A⊬B\\ \lnot ((Γ\land A)\to B)\\ (Γ\land A)\land\lnot B\\ Γ\land (A \land\lnot B)\\ Γ\land \lnot(\lnot A \lor B)\\ Γ\land \lnot(A \to B)\\ \lnot(Γ\to (A \to B))\\ Γ⊬A→B$$
ryang
- 38,879
- 14
- 81
- 179