3.1 Trivial and Vacuous Proofs - Naval Postgraduate School

1 CH3: DIRECT PROOF AND PROOF BY CONTRAPOSITIVEL emma= is a mathematical result that is useful in verifying the truth of another Proposition= a true mathematical statement (that are especially significant)(Propositions are usually more important, and harder to prove than theorems.)Corollary= is a mathematical result that is a consequence of an earlier lemmas, theorems, propositions and corollaries are stated as an implication, or Trivial and Vacuous ProofsMost mathematical results are stated as an implication:P Q. Recall:PQP QTTTTFFFTTFFTLetSbe a universal set,P(x) andQ(x) be two open sentences . Forx S, it can be shownthatQ(x) is true regardless of the truth value ofP(x). ThenP(x) Q(x) is true for allx S. In this case,P Qis true trivially. Such a proof is called a Trivial :Letx R. Ifx>0, thenx2+ 5> :Sincex2 0,for allx R, it follows thatx2+ 5>x2 + 5 that we didn t use the fact thatx>0,since it holds for allx , if it can be shown thatP(x) is false for allx S(regardless of the truth value ofQ(x)), thenP(x) Q(x) is true for all values ofx S.

2 That isP Qis true a proof is called a Vacuous :Letx R. Ifx2+ 1<0, thenx5 thatx2+ 1>x2 0. Thusx2+ 1<0 is false for allx S, and so theimplication is Direct ProofsDirect ProofofP Q: Assume thatP(x) is true for an arbitraryx S, and show thatQ(x) is true for this x. In order to illustrate this type of proof we assume that we know:1. The negative of an integer is an integer2. The sum/difference/product of two integers is an integer13. An integernis evenifn= 2k, k Z4. An integernis oddifn= 2k+ 1, k :Ifnis an odd integer, then 5n+ 3 is an even thatnis an odd integer. Thenn= 2k+ 1 for somek Z. Thus 5n+ 3 =5(2k+1)+3 = 10k+8 = 2(5k+4).Since 5k+4 is an integer, it follows that 5n+3 is :Ifnis an odd integer, then 4n3+ 2n 1 is thatnis odd. Son= 2k+ 1, for some integerk. Thus4n3+ 2n 1 = 4(2k+ 1)3+ 2(2k+ 1) 1= 4(4k3+ 12k2+ 6k+ 1) + 4k+ 2 1= 16k3+ 48k2+ 28k+ 5= 2(8k3+ 24k2+ 14k+ 2) + 8k3+ 24k2+ 14k+ 2 is an integer (ask Z), it follows that 4n3+ 2n 1 is odd.

3 Result :Ifnis an even integer, then 3n5+ 2 is thatnis an even integer. Thenn= 2k, for somek Z. Thus3n5+ 2 = 3(2k)5+ 2 = 253k5+ 2= 2(243k5+32) + 1 = 2(48k5+32) + 48k5+32 Z, it follows that 3n5+ 2 is s wrong with the proof? Be careful with what you claim to be an integer!! The resultis false, but it can be fixed: Ifnis an even integer, then 3n5+ 2 is writing a proof:1. Write a proof so that somebody else can read Write complete sentences , starting with Proof and ending with .3. When introducing a new variable/symbol explain what the symbol is, and what setthe variable belongs If your equation wraps arund, then the equal sign goes at the end of the line, andnot before the new line nor both within the text. Or you may choose to center example, within the text you should use it like thisab= 4k`+ 2k+ 2`+ 1 =2(2k`+k+`) + 4k`+ 2k+ 2`+ 1= 2(2k`+k+`) + Proof by ContrapositiveThe contrapositiveof an implicationP Qis the implication Q : LetP(x) :x= 2, and letQ(x) :x2= Q: Ifx= 2, thenx2= 4.

4 (T) Q P: Ifx26= 4, thenx6= 2. (T)The implicationP Qand Q Pare logically equivalent:PQP Q Q P Q PTTTFFTTFFTFFFTTFTTFFTTTTA proof by contrapositive ofP Qis a direct proof of Q :Letx Z. If 3x 15 is even, thenxis thatxis even. Thenx= 2a, for some integera. Then3x 15 = 3(2a) 15 = 6a 15= 2(?) + 1 = 2(3a 8) + 3a 8 Z, 3x 15 is can also prove it using a direct proof (usex= (3x 15) (2x 15)):Result:Letx Z. If 3x 15 is even, thenxis that 3x 15 is even. Then 3x 15 = 2a, for some integera. Thenx= (3x 15) (2x 15) = 2a 2x+ 15= 2(?) + 1 = 2(a x+ 7) + x+ 7 Z,xis :Letx Z. Then 5x+ 3 is even if and only ifxis thatxis even. Thenx= 2k, k + 3 = 5(2k) + 3 = 10k+ 3 = 2(5k+ 1) + 5k+ 1 Z, it follows that 5x+ 3 is the converse, letxbe odd. Sox= 2k+ 1, k Z. Hence,5x+ 3 = 5(2k+ 1) + 3 = 10k+ 8 = 2(5k+ 4).There are two implications to prove here:(1) If 5x+ 3 is even, thenxis odd.

5 (2) Ifxis odd, then 5x+ next result is useful to use, so we refer to it as a :Letx Z. Thenx2is even if and onlyxis :Assume thatxis odd. Thusx= 2k+ 1, for somek (2k+ 1)2= 4k2+ 4k+ 1 = 2(2k2+ 2k) + 2k2+ 2kis an integer,x2is the converse, assume thatxis even. Thenx= 2k,for somekan integer. Thusx2= (2k)2= 4k2= 2(2k2).Recall that the contrapositive ofP Qis Q P. The contrapositive of the Theoremabove gives us another theorem:Theorem:Letx Z. Thenx2is odd if and onlyxis Proof by CasesResult:Letn Z. Thenn2+ 3n+ 5 is an odd proceed by cases, according to whethernis even or Case 2x, x + 3n+ 5 = 4x2+ 6x+ 5 = 2(2x2+ 3x+ 2) + Case 2x+ 1, x + 3n+ 5 = 4x2+ 4x+ 1 + 6x+ 3 + 5 = 2(2x2+ 5x+ 4) + + 3n+ 5 is an odd : The result must be true for all the cases. If it fails for one case, then the result are the typical cases?Ex1: Case evenCase oddEx2: Case >0 Case 0 Case <0Ex3: We can have a combination ofxandyCase <0 Subcase >0 andy>0 Subcase <0 andy<0 Case 0 Thenx= 0 ory= >0 Subcase >0 andy<0 Subcase <0 andy>0 Two integersxandyare of the same parityifxandyare both even or both odd.

6 Twointegersxandyare of opposite parityifxis even andyis odd, orxis odd andyis :Letx,y Z. Then 3x+ 3yis an odd integer if and only iffxandyare of thatxandyare of the same parity. We consider two Case both 2k,y= 2`, k,` + 3y= 6k+ 6`= 2(3k+ 3`).Since 3k+ 3`is an integer, 3x+ 3yis Case both 2k+ 1,y= 2`+ 1, k,` + 3y= 6k+ 3 + 6`+ 3 = 2(3k+ 3`+ 3).Since 3k+ 3`+ 3 is an integer, 3x+ 3x+ 3yis an even now verify the converse. Assume thatxandyare of opposite parity. We consider Case even andyis 2k,y= 2`+ 1, k,` + 3y= 6k+ 6`+ 3 = 2(3k+ 3`+ 1) + 3k+ 3`+ 1 is an integer, 3x+ 3yis Case odd andyis 2k+ 1,y= 2`, k,` + 3y= 6k+ 3 + 6`= 2(3k+ 1 + 3`) + 3k+ 3`+ 1 is an integer, 3x+ 3yis 3x+ 3yis an odd : In this particular theorem, we could have said: Without loss of generality (WLOG)assume thatxis even andyis odd (and this would also cover the case ofxis odd andyiseven.)

7 However, this is not always possible: if you would have to show that 3x+yis eithereven or odd, you cannot use WLOG since this s not a symmetric :Letaandbbe integers. Thenabis even iffais even orbis :Assume thatais odd andbis odd. Thena= 2k+ 1,b= 2`+ 1, k,` 4k`+ 2k+ 2`+ 1 = 2(2k`+k+`) + 2k`+k+`is an integer,abis the converse, assume thatais even orbis even. Without loss of generality say thatais even. Thena= 2k, k (2k)b= 2(kb).Sincekbis an integer,abis :Letx,y Z. Prove that ifxyandx+yare even, then bothxandyare :Assume thatxis odd oryis odd, WLOG sayxis odd. We wish to show thatxyorx+yis odd. Thenx= 2k+ be even orycould be odd. We consider Case 2`+ 1, ` (2k+ 1)(2`+ 1) = 4k`+ 2k+ 2`+ 1 = 2(2k`+k+`) + 2k`+k+`is an integer,xyis Case 2`, ` +y= (2k+ 1) + 2`= 2(k+`) + +`is an integer,x+yis Proof evaluations: gives you good hints on what not to do in terms of