3
$\begingroup$

Using the Fitch system, how do I prove $((p \implies q) \implies p)\implies p$? I started with the hypotheses $(p \implies q) \implies p$ and $\sim p$. However, from these hypotheses I did not get the desired contradiction to solve the question.

Thanks sb45

$\endgroup$
  • $\begingroup$ If $p$ is not true, then $(p\Rightarrow q)$ is true, so from the hypotheses, $p$ is true, a contradiction. $\endgroup$ – Questioner Feb 21 '17 at 18:13
  • $\begingroup$ The law is pierce's law, and it is well known to not be constructively provable. So if you don't have double negation elimination, or law of the excluded middle, or something similar, then you can't prove it. If you do have law of the excluded middle, then you prove it the same way you prove every propositional formula. There are $n=2$ boolean variables so there are $2^n$ cases of them being true false. Prove the formula under all $4$ cases the stitch it up with proof-by-cases (also called "or elimination"). $\endgroup$ – DanielV Feb 21 '17 at 18:21
2
$\begingroup$

You were on the right track .... almost there in fact:

enter image description here

$\endgroup$
  • $\begingroup$ How did you produce this image? $\endgroup$ – grndl Feb 21 '17 at 18:33
  • 2
    $\begingroup$ It's a screen shot of an interactive program (called 'Fitch') to create these kinds of Fitch proofs (and get instant feedback from the system whether you applied the rule correctly or not). $\endgroup$ – Bram28 Feb 21 '17 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.