Prove that $¬(A → B) ⊢ ¬(¬A ∨ B)$ in natural deduction

Question

I just can’t seem to find a way to prove $¬(A → B) ⊢ ¬(¬A ∨ B)$

Any help would be appreciated!

I am using a reductio strategy. I have made the following assumptions:

$ \text{1.} ¬A ∨ B$

$ \text{2.} ¬A$

$ \text{3.} A$

$ \text{4.} ¬B$

But I just can’t get further from here.

Welcome to [math.se] SE. Take a [tour]. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an [edit]): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. — Shaun, Mar 23 '23 at 12:02
Ok, step 1 is correct. Then, you have to apply Disjunction Elim to it. — Mauro ALLEGRANZA, Mar 23 '23 at 12:06
@Shaun thx for your input. I’ve updated my post. I’m allowed to use the I/E-rules for the relevant connectives — StudentusErasmusMontanus, Mar 23 '23 at 12:07
You're welcome. Thank you for adding context. Here's a MathJax tutorial :) — Shaun, Mar 23 '23 at 12:43

score 1 · Answer 1 · answered Mar 28 '23 at 00:28

To use disjunction elimination (${\lor}\mathsf E$) you make sub-proof assuming the disjuncts aiming to derive the same conclusion under each. To complete the reductio ad absurdum ($\textsf{RAA}$) proof, that conclusion needs to be a contradiction ($\bot$), or something that would allow you to then derive such.

$\qquad\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \fitch{~~1.~~\lnot(A\to B)}{\fitch{~~2.~~\lnot A\lor B}{\fitch{~~3.~~\lnot A}{~~~~\vdots\\~~\ell.~~\bot}\\\fitch{~~m.~~ B}{~~~~\vdots\\~~n.~~\bot}\\~~o.~~\bot\hspace{14ex}{\lor}\mathsf E~~2,3{-}\ell,m{-}n}\\~~p.~~\lnot(\lnot A\lor B)\hspace{8ex}\mathsf{RAA}~2{-}o}\\\quad\therefore\quad\lnot(A\to B)~\vdash~\lnot(\lnot A\lor B)$

score 0 · Answer 2 · answered Mar 28 '23 at 00:39

We look at the cases when the parts inside the parenthesis is false, as that will correspond to the outside parts. The parenthesis on the left is only false when A is false and B is true, and the same can be said for the set of parenthesis on the right. Therefore, this statement is true.

Prove that $¬(A → B) ⊢ ¬(¬A ∨ B)$ in natural deduction

2 Answers2