How to write proofs: a quick guide

1 How to writeproofs:a quick guideEugeniaChengDepartment of Mathematics,University of eugeniaOctober 2004A proof is like a poem,or a painting,or a building,or a bridge,or a novel,or a symphony.\Help!I don'tknow how to writea proof!" Well,didanyoneever tellyouwhata proofis, andhowto goaboutwritingone?Maybe which caseit'snowonderyou' good proof is notsupposedto be somethingwe 'slike writinga poemin a to to know it wellenoughto writepoetryin it, notjustsay \Whichway is it to thetrainstationplease?"Even whenyou know how to do it, writinga proof takes planning,e sketchesbeforestartinga paintingforreal;greatarchitectsmake plansbeforebuildinga building;greatengineersmake plansbeforebuildingabridge;greatauthorsp lantheirnovelsbeforewritingthem; ,greatmathematiciansplantheirproofsin advanceas Whatdoes a proof looklike?

2 32 Why is writinga proof hard?33 Whatsortof thingsdowe tryandprove?44 Thegeneralshape of a proof45 Whatdoesn'ta proof looklike?66 Practicalities:how to thinkupa proof97 Somemorespeci cshapes of proofs108 Proof by contradiction159 Exercises:Whatis wrongwiththefollowing\proofs"?1621 Whatdoes a proof looklike?A proof is a seriesofstatements, eachof whichfollowslogicallyfromwhathasgonebefo re. Itstartswiththingsweare assumingto be tryingto ,like a good story, a proof hasa beginning,a middleandanend. Beginning:thingswe areassumingto be true,includingthede nitionsof thethingswe'retalkingabout Middle:statements,each followinglogicallyfromthestu beforeit End:thethingwe'retryingto proveThepoint is thatwe'regiventhebeginningandtheend,ands omehow we have to llin can'tjust llit in randomly{ we have to llit in in a waythat\getsus to theend".}

3 It'slike puttingin steppingstonesto crossa we putthemtoo farapart,we'rein dangerof fallingin whenwe tryto might be okay, butit might not: : :andit'sprobablybetterto be is writinga proof hard?Oneof thedi cultthingsaboutwritinga proof is thattheorderin which we writeitis oftennottheorderin which we thought it fact,we catcha movieat yougoingtogetthere?Yousee thattheBrownLinewill takeyouthere knowthatyoucan getthe#6 Busto theLoop,andyouknowthatyoucan walkto the# makethejourney,youstartby walkingto the#6,andyouendby someoneasksyoufordirections,it will notbe veryhelpfulifyouexplainit to thembackwards: : :Orto putit anotherway, to builda bridgeacrossa river,we might wellstartatbothendsandworkourway might even putsomepreliminarysupportsat variouspoints in themiddleand llin actuallygo acrossthebridge,we startat oneendand nishat theeasiestmistakes to make in a proof is towriteit downin theorderyouthoughtof it.

4 Thismay containalltheright steps,butif they'rein thewrongorderit' 'slike takinga pieceof musicandplayingallthenotesin a di erent wordwithallthelettersin ,you'llprobablyneedto planit outin advanceof actuallywritingit buildinga longbridgeor a largebuilding{ it needssomeplanning,eventhoughbuildinga smallbridgeor a tiny hut might thingsdowe tryandprove?Hereis a classi cationof thesortsof thingswe prove (thislistis notexhaustive, andit'salsonotclearcut{ thereis someoverlap,dependingonhow youlookat it) \somethingequalssomethingelse" ) () purple(orhassomeotherinterestingandrelev ant property) p(x) is \allanimalsof a certainkindxbehave in a certainwayp(x)" (x) is \thereis ananimalthatbehaves in a certainwayp(x)"7.}}

5 Supposethata; b; true.[Notethatthisis justa versionof 2 in disguise.]4 Thegeneralshape of a proofLet'snow have a lookat thegeneralshape of a proof,beforetakinga closerlookatwhatit might look like foreach of mustalways remember thatthereis a beginning,a eldaxioms,provethata(b c) =ab acforanyrealnumbersa; b; c. You mayusethefactthatx:0 = 0foranyreal eldaxiomsde nitionx y=x+ ( y)givenx:0=0middlea(b c) =a(b+ ( c))de nition=ab+a( c)distributivelawac+a( c) =a(c+ ( c))distributivelaw=a:0additiveinverse=0g iven)a( c) = (ac)de nitionof additiveinverse)ab+a( c) =ab acend)by line2,a(b c) =ab acas required functionsAf !

6 Bg ! injectivetheng fis injectivebeginningde nitionof injectivede nition(g f)(a) =g(f(a))assumptionthatf andg are ;a02Af(a) =f(a0) =)a=a08b;b02Bg(b) =g(b0) =)b=b0middle(g f)(a) = (g f)(a0) =)g(f(a)) =g(f(a0))by de nition=)f(a) =f(a0)sinceg is injective=)a=a0sincef is injective)(g f)(a) = (g f)(a0) =)a= f is injective,as required inductionthat8n2N;1 + +n=n(n+ 1)2beginningPrincipleof Inductionmiddlefor n=1, LHS=1 RHS=1(1+1)2=1)resultis truefor n=1If resultis truefor n=k then1+ +k+ (k+1) =k(k+1)2+ (k+1)=k(k+1) +2(k+1)2=(k+1)(k+2) n=k+1)resulttruefor k=)resulttruefor k+1end)by thePrincipleof Induction,theresultis truefor all n2N 5 Ofcourse,whenwe writea good story, we don'tactuallylabelthebeginning,themiddle andtheendwithBEGINNING,MIDDLE,andEND{ it'ssupposedto be sortof trueof a 'sthethingI keepgoingonaboutbutwhich is apparentlynotas obviousas it might sound.}

7 Theendof a proof shouldcomeat theend,notat ,I've deliberatelymadeit 'sa moreilluminatingway of puttingit:Theproof shouldendwiththethingyou'retryingto prove. Theproof shouldnotbeginwiththethingyou'retryingto notto be confusedwiththefactthatwe oftenbeginbyannouncingwhattheendis goingto be. Thisis a bitlike a storythatstartsat theendandthentheentirestoryis a ashback. LikeTheGo-BetweenorBrideshead RevisitedorRebecca. Or,it'slike takingsomeoneona journey{ youmight well tellthemwhereyou'regoingright 've toldthemwhatthedestinationisyoustill startthejourneyfromthebeginning.}

8 Thesameis trueof we beginby announcingwhattheendis goingto be,wethenhaveto startat thebeginningandworkourway to 'ta proof looklike?There are more plastic amingoes in America thanreal theworldthangood ones,andtherearemorebadproofsin theworldthangood themostpopularways to writea Beginat theendandendat thebeginningThisis a really, reallyterriblethingto be evenworsethanleavingoutgapsin youbeginattheendandendatthebeginningyoum onumentallyhaven'tgotwhereyou' 'sanexampleof thisforExample1 fromSection4:a(b c) =ab acab+a( c) =ab aca( c) = acac+a( c) =0a(c+ ( c))=0a.

9 0=00=0 Try comparingthiswiththegoodproof given in Section4 { you'llseethatall thecorrectstepsarethere,butthey'reallin 't it backwards a terriblethingto dobutnota terminalcatastrophe{ if youhave alltherightideasbutin thewrongorder,allyouneedto dois workouthow to putthemin theright order: : :2. Take yingleapsinsteadof to another withoutjustifyingtheleap leavingouttoo many stepsin between usinga profoundtheoremwithoutprovingit (worse)usinga profoundtheoremwithoutevenmentioningitFo r example,spot the yingleapin thefollowing\proof":a(b c) =ab+a( c)=ab ac 3. Take yingleapsandland atonyourfacein themudBywhich I welljustifythemeansin someworlds,butin mathematicsif youusethewrongmeansto getto theright end,youhaven'tactuallygotto theendat Butit'sa gment of 'sanexampleof a veryimaginitive \proof"thatisde nitely atonitsfacein themud:a(b c) =ab+a( c)=ab+a( c) +a:1=ab+a(1 c)=ab ac Ofcourse,it'seven worseif youdosomethingillegalandthereby reach a conclusionthatisn' )x=yorx2<y2=)x<y:Whatis wrongwiththesetwo \deductions"?}}

10 74. HandwavingHandwavingis whenyouarrive at a statement by 'tnecessarilywrong,butyouhaven'tarrived at it in a good resortto writinga fewsentencesof prosein oftena signthatyou've gottheright ideabutyouhaven'tworkedouthow to thehandwavinghere{ youcanseeit froma mileo :a(b c) =ab+a( c)a( c) = acbecauseif youaddac tobothsidesthenbothsidesvanishwhichmeans they0re inverse)ab+a( c) =ab ac Handwavingis badbutis notultimatelycatastrophic{ youjustneedto learnhowto translatefromEnglishinto probablyeasierto learnthantheproblemof comingupwiththeright ideain the IncorrectlogicThisincludesthetwo greatclassics negatinga statement incorrectly provingtheconverseof somethinginsteadof thethingitselfWhatis thenegationof thefollowingstatement:8" >09 >0 <jx aj< ;jf(x) lj< "Thecorrectanswer is at thebottomof thepage1.}}