# How to prove : P v ( P → Q ) by Natural Deduction

Another of Tomassi's exercises I can't solve (Logic, page 109, Revision exercise III, 9)

: P v ( P → Q )

I have to use natural deduction and the only rules I know are:

• assumptions,

• modus ponendo ponens,

• modus tollendo tollens,

• double negation,

• conditional proof,

• v-introduction,

• v-elimination,

• and introduction,

• and elimination.

Tomassi's proof consists of 16 steps.

Thanks!

• You have posted many questions regarding elementary logic homeworks on this site: many answers... no one accepted by you. If you are not interested in the answers, wht ask questions ? – Mauro ALLEGRANZA Dec 28 '18 at 17:45
• @MauroALLEGRANZA I'm really sorry I didn't know I had to do that. – Diego Ruiz Haro Dec 28 '18 at 18:00
• Please see: Why is “Can someone help me?” not an actual question? Can you edit to show what you tried and where you got stuck? (That way we can explain what part of that you're confused about). – EJoshuaS Dec 29 '18 at 17:15

Here is what the proof looks like strictly following Tomasello's rules:

{1} 1. ~(P v ( P → Q )) Assumption for RAA

{2} 2. P Assumption for RAA

{2} 3. P v ( P → Q ) 2 vI

{1,2} 4. (P v ( P → Q )) & ~(P v ( P → Q )) 1,3 &I

{1} 5. ~P 2,4 RAA

{6} 6. P Assumption

{7} 7. ~Q Assumption for RAA

{6,7} 8. P & ~Q 6,7 &I

{6,7} 9. P 8 &E

{1,6,7} 10. P & ~P 5,9 &I

{1,6} 11. ~~Q 9,10 RAA

{1,6} 12. Q DNE 11

{1} 13. P → Q CP 6,12

{1} 14. P v ( P → Q ) 13 vI

{1} 15. (P v ( P → Q )) & ~(P v ( P → Q )) 1,14 &I

{} 16. ~~(P v ( P → Q )) RAA 1,15

{} 17. P v ( P → Q )) DNE 16

Notice what I did there: on line 8 I pasted the ~Q to the P from line 6, but then on line 9 I isolated that P again ... the whole effect of which was to make the P now dependent on the assumption of ~Q (after all, I did derive that P from P & ~Q, and I got P & ~Q from (among other things ~Q), so yes, it is dependent on ~Q). And that means that the contradiction on line 10 is dependent on ~Q as well, which is why we can say that the contradiction is 'derived' from ~Q. Indeed, when we then apply RAA, we throw out this very dependency of ~Q.

On pages 63-64 Tomassi talks about this very strategy, and calls it augmentation. There, he used it for CP, for he demands that in order to apply CP, the depencies of the antecedent should be in the depencies of the consequent. On the top half of p.104 he mentions that the same must be true for RAA:

The contradiction must depend upon the assumption if we are to apply RAA legitimately to that assumption.

• Thanks a lot! I still don't get where line 9 comes from. According to Tomassi's text, in order to get line 9, it has to be deduced from line 7 and any other formulas available. However, I don't see how ~Q from line 7 is computed with P & ~P line 8 to get ~~Q. What I mean is how is the assumption ~Q related to P & ~P so to produce ~~Q? – Diego Ruiz Haro Dec 30 '18 at 18:22
• @DiegoRuizHaro Yeah, that's a weird one ... let me explain that in the Answer – Bram28 Dec 30 '18 at 20:36
• @DiegoRuizHaro OK, I very carefully read Tomassi, and found that indeed the depencies of the assumption should be a subset of the depencies of the contradiction, so that it indeed makes sense to say that P&~P is derived from ~Q. To do this, you use a little trick called augmentation .. I explain this in the updated Answer. – Bram28 Dec 30 '18 at 21:40

Hint

Use v-elimination on P v ~P.

Alternatively, we can circumvent the lack of LEM using Double Negation :

1) ~ [P v ( P → Q )] --- assumed [a]

2) ~Q --- assumed [b]

3) ~P --- assumed [c]

4) P --- assumed [d]

5) ~~Q --- from the contradiction of 3) and 4) by RAA

6) Q --- from 5) by DNE, discharging [b]

7) ( P → Q ) --- from 4) and 6) by →-intro, discgarging [d]

8) P v ( P → Q ) --- from 5) by v-intro.

Now we have a contradiction with 1) and we use RAA and DNE with 3) deriving :

9) P --- from 3), discharging [c]

10) P v ( P → Q ) --- from 9) by v-intro.

Contradiction with 1) again : we apply RAA and DNE to 1) deriving :

11) P v ( P → Q ) --- from 1), discharging [a].

• As far as I know he can't prove the law of excluded-middle P v ~P (which is necessary to do v-elimination). – Boris E. Dec 28 '18 at 18:02
• @BorisE. - why not ? DN is equiv to LEM. – Mauro ALLEGRANZA Dec 28 '18 at 18:07
• Oh, sorry, you're right. – Boris E. Dec 28 '18 at 18:10
• @MauroALLEGRANZA Thanks a lot! However it is not clear to me yet how do you get Q from 2 and 3? I'm sorry for the silly question but I'm just teaching myself logic and Tomassi's is the only reference I'm using. I have no mathematics background. So the only information I have is the one in Tomassi's text. For the moment, he hasn't shown how to get the sort of contradiction you got at 4. – Diego Ruiz Haro Dec 29 '18 at 13:50
• @DiegoRuizHaro - I cannot find browsing Tomassi's book a reference list of rules. In Natural deduction there is the rule that allows us to derive a formula whatever from a contradiction. In your case, if this rule is not available, you can simplu assume ~Q and derive Q from it using the contradiction. – Mauro ALLEGRANZA Dec 29 '18 at 14:11