# Is my proof by natural deduction for $(p\rightarrow (q\rightarrow r))\rightarrow (q\rightarrow (p\rightarrow r))$ correct?

1. $\left(p\rightarrow\left(q\rightarrow r\right)\right)$---premise
2. q---assumption
3. p---assumption
4. $q\wedge p$---by $\wedge$-Intro from 2 and 3
5. q---by $\wedge$-elim from 4
6. p---by $\wedge$-elim from 4
7. $q\rightarrow r$---by $\rightarrow$-elim from 1 and 6
8. r------by $\rightarrow$-elim from 5 and 7
9. $p\rightarrow r$---by $\rightarrow$-Intro from 3 and 8
10. $q\rightarrow\left(p\rightarrow r\right)$---by $\rightarrow$-Intro from 2 and 9
11. $\left(p\rightarrow\left(q\rightarrow r\right)\right)\rightarrow\left(q\rightarrow\left(p\rightarrow r\right)\right)$---by $\rightarrow$-Intro from 1 and 10

Also is there any other way to do this proof by natural deduction?

• 4, 5 and 6 are cleary unnecessary. – Mauro ALLEGRANZA Sep 6 '17 at 15:13
• Your proof is fine. As Mauro says, 4,5,6 are not needed ... but the fact that you can add unnecessary steps shows that if there is one proof, then there are infinitely many. In terms of different proof 'strategies' .. that's hard to count, but you could do this one with a proof by contradiction ... though that will be more work; without lines 4,5,6, the proof will be as clear and efficient as you can do this one. – Bram28 Sep 6 '17 at 15:41
• @MauroALLEGRANZA please verify my answer ^^ – Pooria Sep 6 '17 at 20:35
• @Bram28 Please verify my answer ^^ – Pooria Sep 7 '17 at 2:51

eliminating 4,5 and 6 which were unnecessary, the correct proof is:

1. $\quad\bullet\; \left(p\rightarrow\left(q\rightarrow r\right)\right)$ --- premise
2. $\quad\bullet \quad\bullet\;q$ --- assumption
3. $\quad\bullet\quad\bullet\quad\bullet\;p$ --- assumption
4. $\quad\bullet\quad\bullet\quad\bullet\;q\rightarrow r$ --- by $\rightarrow$-elim from 1 and 3
5. $\quad\bullet\quad\bullet\quad\bullet\;r$ --- by $\rightarrow$-elim from 2 and 4
6. $\quad\bullet\quad\bullet\;p\rightarrow r$ --- by $\rightarrow$-Intro from 3 and 5
7. $\quad\bullet\;q\rightarrow \left(p\rightarrow r\right)$ --- by $\rightarrow$-Intro from 2 and 6
8. $\; \left(p\rightarrow\left(q\rightarrow r\right)\right)\rightarrow \left(q\rightarrow \left(p\rightarrow r\right)\right)$ --- by $\rightarrow$-Intro from 1 and 7
• It is correct, as was the previous one, provided the deletion of the un-necessary steps. – Mauro ALLEGRANZA Sep 7 '17 at 6:06
• thanks master Mauro ^^ – Pooria Sep 7 '17 at 6:45
• you are welcome :-) – Mauro ALLEGRANZA Sep 7 '17 at 6:57
• @Pooria Yes, both proofs are fine! – Bram28 Sep 7 '17 at 11:30
• And thanks master Bram28 ^^ – Pooria Sep 7 '17 at 12:55

$$\dfrac{\quad\dfrac{[p \to (q \to r)]}{\quad\dfrac{\quad\dfrac{[q]}{\quad\dfrac{\dfrac{\dfrac{[p]}{q \to r}{\small\text{MP}}}{r}{\small\text{MP}}}{p \to r}{\small\to\text{I}}\quad}\quad}{q \to (p \to r)}{\small\to\text{I}}\quad}\quad}{(p \to (q \to r)) \to (q \to (p \to r))}{\small\to\text{I}}$$