[PDF] Three Ways to Prove “If A, then B”

41264_13ways.pdf

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 also.

Most theorems can be stated in the form "IfA, thenB." Even if they are not written in this form, they

can 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." They are calleddirect proof,contra- positive proofandproof by contradiction. DIRECT PROOF.To prove that the statement "IfA, thenB" is true by means of direct proof, begin by assumingAis true and use this information to deduce thatBis true. Here is a template. What comes between the first and last line of course depends on whatAandBare.

Theorem: IfAthenB.

Proof. SupposeAis true....

ThereforeBis true.

CONTRAPOSITIVE PROOF.The idea is that if the statement "IfA, thenB" is really true, then it"s impossible forAto be true whileBis false. Thus, we can prove the statement "IfA, thenB" is true by showing that ifBis false, thenAis false too. Here is a template.

Theorem: IfAthenB.

Proof. SupposeBis false....

ThereforeAis false.

PROOF BY CONTRADICTION.Again, if the statement "IfA, thenB" is really true, then it"s

impossible forAto be true whileBis false. In other words, it is a contradiction to assumeAis true and

Bis false. Of course, since you have not proved "IfA, thenB" is a true statement, this contradiction is

not at all obvious. In the technique ofproof by contradiction, you begin by assumingAis true and Bis false, and use this to deduce andobviouscontradiction of from "Cis true andCis false." Here"s a template.

Theorem: IfAthenB.

Proof. SupposeAis true andBis false....

ThereforeCis true andCis false.

1

Examples of the Three Proof Techniques.

Here is a homework problem proved three ways - by means of direct proof, contrapositive proof, and proof by contradiction. Section 4, Exercise 34:LetGbe a group with a finite number of elements. Show that for anya?G there is ann?Z+for whichan=e.

DIRECT PROOF

Theorem:Ifais an element of a finite groupG, then there is ann?Z+for whichan=e. Proof. Supposeais an element of a finite groupG. SayGhasmelements. Consider the following list of

elements 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 integersjandkwith

1≤j < k≤m+ 1. Thenaj=ak

a j(a-1)j=ak(a-1)j a j(aj)-1=aka-j e=ak-j Settingn=k-j, it follows thatan=e.CONTRAPOSITIVE PROOF Theorem:Ifais an element of a finite groupG, then there is ann?Z+for whichan=e. Proof. (Contrapositive) Suppose there isnon?Z+for whichan=e. Consider the infinite list of group

elementsa1,a2,a3,a4,a5···. No two elements of this list are equal, for if they were, there would be positive

integersjandkwith 1≤j < kandaj=ak, and multiplying both sides on the right bya-jwould give

e=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 finite.PROOF BY CONTRADICTION Theorem:Ifais an element of a finite groupG, then there is ann?Z+for whichan=e. Proof. (Contradiction) SupposeGis finite and there isnon?Z+for whichan=e. Consider the infinite

list of group elementsa1,a2,a3,a4,a5···. No two elements of this list are equal, for if they were, there

would be positive integersjandkwith 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. 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 contradiction.Notice that in the proof by contradiction, to showGis infinite we ended up using much of the same

reasoning used in the contrapositive proof. Thus, in this case, the contrapositive approach would be

simpler. If possible you should always go with the simplest proof technique. Very often, one approach will

seem impossible but another will be quite easy. If you get stuck, try a different approach. 2

If-And-Only-If Proofs

The 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. Here is a template.

Theorem:Aif and only ifB.

Proof:

SupposeAis true....

ThereforeBis true.

SupposeBis true....

ThereforeAis true.

Notice that in each of the two parts, you are really proving a statement of the form "IfXthenY," so for

each part you can use direct proof, contrapositive proof, or proof by contradiction. Use whatever seems

easiest. 3