Help with an indirect proof (RAA)

[aychamo]

Hey guys;

I was hoping that I could get some help with an indirect proof we are doing in my logic class. It is an introductory class, and this was a homework question that I couldn't get. This isn't course-work that is graded, it is just practice for our exam that is tomorrow! I asked it in class today and the professor worked on it for about 45 minutes but he couldn't get it. He and I are both sure that it is something very simple that we aren't catching.

Here it is: (I will use = to show equivalence, and > to show implication).

1. (R*S) = (G*H)
2. R > S
3. H > G

Conclusion: R=H

The point is to use Reductio ad Absurdum (RAA) to solve this. We can use the 18 Rules of Inference (and Replacement), and also conditional proofs.

Here is one pathway I took that did not steer me towards the answer:

4. ~(R=H) by AP (first thing for the RAA)
5. [(R*S) > (G*H) * [(G*H) > (R*S)] by Equiv 1
6. (R*S) > (G*H) by Simp 5
7. (G*H) > (R*S) by Simp 5
8. ~[(R*H) v (~R*~H)] by Equiv 4
9. ~(R * H) * ~(~R * ~H) by DM 8
10. (~Rv~H) * ~(~R*~H) by DM 9
11. (~R v ~H) by Simp 10
12. ~(~R*~H) by simp 10
13. (RvH) by DM 12
14. (SvG) by CD(2,3,13)

Perhaps there is something to the constructive delimma that is set up on line 14? Also, it seems that I will have to at some point use a conditional proof or something to assume a sentence letter, or something, because I don't see how I can show the contradiction (we do the A*~A on the same line thing) without having some sentence letter to prove another?

I dunno, this should be really easy because this is a basic logic book (A Concise Introduction to Logic by Hurley) and a basic class, and the rest of the proofs are very easy in this section. But this one .. We couldn't get it. Does anyone have a suggestion?

Thank you!
AYCHAMO

 

[metacristi]

Hey guys;

I was hoping that I could get some help with an indirect proof we are doing in my logic class. It is an introductory class, and this was a homework question that I couldn't get. This isn't course-work that is graded, it is just practice for our exam that is tomorrow! I asked it in class today and the professor worked on it for about 45 minutes but he couldn't get it. He and I are both sure that it is something very simple that we aren't catching.

Here it is: (I will use = to show equivalence, and > to show implication).

1. (R*S) = (G*H)
2. R > S
3. H > G

Conclusion: R=H

The point is to use Reductio ad Absurdum (RAA) to solve this. We can use the 18 Rules of Inference (and Replacement), and also conditional proofs.

Here is one pathway I took that did not steer me towards the answer:

4. ~(R=H) by AP (first thing for the RAA)
5. [(R*S) > (G*H) * [(G*H) > (R*S)] by Equiv 1
6. (R*S) > (G*H) by Simp 5
7. (G*H) > (R*S) by Simp 5
8. ~[(R*H) v (~R*~H)] by Equiv 4
9. ~(R * H) * ~(~R * ~H) by DM 8
10. (~Rv~H) * ~(~R*~H) by DM 9
11. (~R v ~H) by Simp 10
12. ~(~R*~H) by simp 10
13. (RvH) by DM 12
14. (SvG) by CD(2,3,13)

Perhaps there is something to the constructive delimma that is set up on line 14? Also, it seems that I will have to at some point use a conditional proof or something to assume a sentence letter, or something, because I don't see how I can show the contradiction (we do the A*~A on the same line thing) without having some sentence letter to prove another?

I dunno, this should be really easy because this is a basic logic book (A Concise Introduction to Logic by Hurley) and a basic class, and the rest of the proofs are very easy in this section. But this one .. We couldn't get it. Does anyone have a suggestion?

Thank you!
AYCHAMO

There is a simple solution using de Morgan laws and the definiton of implication (A->B is equivalent with (~A \/ B),if you are allowed to use them then my proposal might be of help:

*=AND
->=the implication sign
\/=OR
~=the negation sign
=the equivalence sign

Lets' assume that ~(H=R) is true=1

We have H=R equivalent with (R->H)*(H->R)

Thus ~(H=R)=~[(R->H)*(H->R)]

Applying de Morgan's law ~(A*B)=~A \/ ~B --->

~(H=R)=~[(R->H)*(H->R)] =[~(R->H)] \/ [~(H->R)]

[~(R->H)] \/ [~(H->R)]=[~(~R \/ H)] \/ [~(~H \/ R)]

By applying again one of de Morgan's laws ~(A \/ B) = ~A * ~B --->

[~(~R \/ H)] \/ [~(~H \/ R)]=(R*~H) \/ (H * ~R)

(R* (~H)) \/ (H * (~R))=(R \/ H) * (R \/ ~R) * (~H \/ H) * (~H \/ ~R)

(R \/ ~R) and (~H \/ H) are tautotologies (their truth value is always 1)

(R \/ H) * (~H \/ ~R) is 1 only if H is different from R.

Therefore if ~(H=R) is true then H is different from R.

Now if we choose R=1 we have H=0

Next from R->S we have that S=1 and from H -> G we have that G is either 0 or 1 (not important anyway).

Thus (R*S)=1 and (G*H)=0.This is a contradiction with the premise that always R*S=G*H therefore ~(R=H) is false and R=H (in the virtue of excluded middle principle) is true.

 

[R0man]

Hi AYCHAMO,

I completely understand your frustration with this problem. Indirect proofs, especially using RAA, can be tricky and require a lot of logical thinking. Here are some steps that may help you solve this problem:

1. Start by assuming the opposite of what you want to prove. In this case, you want to prove that R = H, so assume ~(R = H).

2. Use the given premises to try and derive a contradiction. Since the conclusion you want to prove is R = H, try to find a way to get both R and H on the same side of the equation.

3. Since you have (R * S) = (G * H), you can use the transitive property to get (R * S) = (R * H).

4. Now, using the conditional proof, assume R. This will allow you to use the premise R > S to also get S.

5. Using conjunction, you can now get (R * S).

6. Going back to step 3, you now have (R * S) = (R * H). Using the transitive property again, you can get (R * H).

7. Now, using the premise H > G, you can get G.

8. Using conjunction again, you now have (R * H) = (R * G).

9. Going back to step 4, since you have R, you can also use the premise R > S to get S.

10. Using conjunction again, you now have (R * G) = (S * G).

11. Going back to step 7, you have G. Using conjunction again, you now have (S * G).

12. Going back to step 10, you have (S * G) = (R * G). Using the transitive property, you can get (S * G) = (S * R).

13. Using commutativity, you now have (S * R) = (R * S).

14. Going back to step 5, you have (R * S). Using the transitive property, you can get (R * S) = (S * R).

15. Using the transitive property again, you now have (S * R) = (S * G).

16. Using commutativity, you now have (S * G) = (G * S).

17. Going back to step