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.

Answer 1

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

Answer 2

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.