How to show $\neg(P \rightarrow Q) \rightarrow (P ∧ \neg Q)$ in Fitch?

Question

How do I show $ \neg (P \rightarrow Q) \rightarrow (P ∧ \neg Q) $ in Fitch-style FOL proof system? I've been struggling with this for a few days now.

Thanks for the help!

(I'm pretty sure this property is called Negative Implication or something like that, if anybody knows that'd also be great)

EDIT: I'm not allowed to use Contradiction Elimination. Sorry for not specifying in original post!

EDIT 2: Apparently am allowed so thanks to Manx for the answer and to everybody else for the help!

Answer 1

$$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}} \fitch{0.~~}{\fitch{1.~~\neg(P\to Q)}{\fitch{2.~~\neg P}{\fitch{3.~~P}{4.~~\bot\hspace{10ex}\bot~\text{Intro 2,3}\\5.~~Q\hspace{10ex}\bot~\text{Elim 4}}\\6.~~P\to Q\hspace{6.5ex}\to\text{Intro 3-5}\\7.~~\bot\hspace{13.4ex}\bot~\text{Intro 1,6}}\\8.~~P\hspace{17.2ex}\neg~\text{Intro 2-7}\\\fitch{9.~~Q}{\fitch{10.~~P}{11.~~Q\hspace{11ex}\text{Reit 9}}\\12.~~P\to Q\hspace{5.5ex}\to\text{Intro 10-11}\\13.~~\bot\hspace{12.4ex}\bot~\text{Intro } 1,12}\\14.~~\neg Q\hspace{14.5ex}\neg~\text{Intro 9-13}\\15.~~P\land\neg Q\hspace{9.5ex}\land\text{Intro 8,14}}\\16.~~(1.\to 15.)\hspace{9.5ex}\to\text{Intro 1-15}}$$

Answer 2

Start a subproof, assume $\neg (P \to Q)$, and try to derive $P \land \neg Q$. Then close the subproof and derive your statement using $\to$ Intro

No further hints though until I see some effort on your part...

Answer 3

This is where I would start in a proof outline: \begin{align*} &01.\;|\neg(p\to q)\quad\text{Assumption} \\ &02.\;|------\\ &03.\;||\neg p\quad\text{Assumption} \\ &04.\;||------ \\ &05.\;||\vdots \\ &06.\;||\perp \\ &07.\;|\neg\neg p\quad\neg\text{Intro}, 03-06\\ &08.\;|p \quad \neg\text{Elim}, 07\\ &09.\;||q \quad\text{Assumption}\\ &10.\;||------\\ &11.\;||\vdots \\ &12.\;||\perp \\ &13.\;|\neg q\quad \neg\text{Intro}, 09-12\\ &14.\;|p\land\neg q\quad \land\text{Intro}, 08, 13\\ &15.\;(\neg(p\to\neg q))\to(p\land\neg q) \quad \to\text{Intro}, 1-14 \end{align*} Now the most difficult work is still remaining: getting the $\perp$'s in Lines 06 and 12, which I've represented by the vertical dots in 05 and 11. Are you able to continue?