2

How to solve this problem using a Fitch System proof for $( \neg p \implies q) \implies ((\neg p \implies \neg q) \implies p)$ with no premises?

I tried assuming $( \neg p \implies q) $ then assuming $ \neg p $ but where do I go from there to get to $((\neg p \implies \neg q) \implies p)$?

MmmHmm
  • 231

1 Answers1

2

I wasn't sure how to type out the Fitch layout in any other way so sorry about the typesetting. I spent a long time trying to write a proof that didn't use negation elimination but I couldn't think of one. This works though, it's just not ideal.

|$\neg p \rightarrow q\qquad (\mathrm{assumption})$
| |$\neg p \rightarrow \neg q\qquad (\mathrm{assumption,\ want}\ \neg\neg p)$
| |$\neg \neg p\qquad (\mathrm{negation\ introduction}, 1,2)$
| |$p\qquad (\mathrm{negation\ elimination}, 3)$
|$(\neg p \rightarrow \neg q)\rightarrow p \qquad(\mathrm{implication\ introduction}, 2,4)$
$(\neg p \rightarrow q) \rightarrow ((\neg p \rightarrow \neg q)\rightarrow p) \qquad(\mathrm{implication\ introduction}, 1,5)$

Harambe
  • 8,230
  • Ah - thanks! Been struggling with negation introduction/elimination! – MmmHmm Apr 26 '17 at 21:10
  • 1
    A good example for practicing would be using a Fitch style proof to prove negation introduction: $((p \rightarrow q) \wedge (p \rightarrow \neg q)) \rightarrow \neg p$. (However, if you try to prove negation elimination using other inference rules you'll end up sitting at your table until you yourself get eliminated by old age.) – Harambe Apr 26 '17 at 22:04