Three Ways to Prove “If A, then B.”

1 Three ways to Prove IfA, thenB. A statement of the form IfA, thenB asserts that ifAis true, thenBmust be true also. If the statement IfA, thenB is true, you can regard it as a promise that whenever theAis true, thenBis true theorems can be stated in the form IfA, thenB. Even if they are not written in this form, theycan be put into this form. For example, the statements Every group with 4 elements is abelian. and A group is abelian if it has 4 elements. can both be restated as: Ifa groupGhas 4 elements,thenGis abelian. There are Three ways to Prove a statement of form IfA, thenB.

2 They are calleddirect proof,contra-positive proofandproof by Prove that the statement IfA, thenB is true by means of direct proof, beginby assumingAis true and use this information to deduce thatBis true. Here is a template. What comesbetween the first and last line of course depends on : SupposeAis idea is that if the statement IfA, thenB is really true, thenit s impossible forAto be true whileBis false. Thus, we can Prove the statement IfA, thenB is trueby showing that ifBis false, thenAis false too. Here is a : SupposeBis BY , if the statement IfA, thenB is really true, then it simpossible forAto be true whileBis false.

3 In other words, it is a contradiction to assumeAis true andBis false. Of course, since you have not proved IfA, thenB is a true statement, this contradiction isnot at all obvious. In the technique ofproof by contradiction, you begin by assumingAis true andBis false, and use this to deduce andobviouscontradiction of from Cis true andCis false. Here s : SupposeAis true andBis true andCis of the Three Proof is a homework problem proved Three ways by means of direct proof, contrapositive proof, andproof by 4, Exercise 34:LetGbe a group with a finite number of elements.

4 Show that for anya Gthere is ann Z+for whichan= PROOFT heorem:Ifais an element of a finite groupG, then there is ann Z+for whichan= Supposeais an element of a finite groupG. SayGhasmelements. Consider the following list ofelements ofG:a1,a2,a3,a4, am+1. Since this list hasm+1 items in it, andGcontains onlymelements,it follows that the list has at least two items that are equal. Thusaj=akfor some integersjandkwith1 j<k m+ 1. Thenaj=akaj(a 1)j=ak(a 1)jaj(aj) 1=aka je=ak jSettingn=k j, it follows thatan= PROOFT heorem:Ifais an element of a finite groupG, then there is ann Z+for whichan= (Contrapositive) Suppose there isnon Z+for whichan=e.

5 Consider the infinite list of groupelementsa1,a2,a3,a4,a5 . No two elements of this list are equal, for if they were, there would be positiveintegersjandkwith 1 j<kandaj=ak, and multiplying both sides on the right bya jwould givee=ak j, which we are assuming cannot happen. Thus, since no two elements on the infinite list are equal,they are all different elements ofG. ThusGis infinite, so it is not BY CONTRADICTIONT heorem:Ifais an element of a finite groupG, then there is ann Z+for whichan= (Contradiction) SupposeGis finite and there isnon Z+for whichan=e.

6 Consider the infinitelist of group elementsa1,a2,a3,a4,a5 . No two elements of this list are equal, for if they were, therewould be positive integersjandkwith 1 j<kandaj=ak, and multiplying both sides on the rightbya jwould givee=ak j, which we are assuming cannot happen. Thus, since no two elements on theinfinite list are equal, they are all different elements ofG. It follows thatGis infinite. But it is also finite,as stated in the first sentence of the proof. ThusGis finite andGis infinite, which is a that in the proof by contradiction, to showGis infinite we ended up using much of the samereasoning used in the contrapositive proof.

7 Thus, in this case, the contrapositive approach would besimpler. If possible you should always go with the simplest proof technique. Very often, one approach willseem impossible but another will be quite easy. If you get stuck, try a different ProofsThe theorems that can t be stated in the form of IfA, thenB are of the form Aif and only ifB. Such a statement is asserting two things, namely AifB and Aonly ifB. Now, AifB means IfBthenA, and Aonly ifB. means IfAthenB. Thus Aif and only ifB. means IfAthenB, and IfBthenA. So to Prove a statement of the form Aif and only ifB, you really have to do two proofs.

8 Here is :Aif and only :SupposeAis that in each of the two parts, you are really proving a statement of the form IfXthenY, so foreach part you can use direct proof, contrapositive proof, or proof by contradiction. Use whatever