How to write proofs: a quick guide - GitHub Pages

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.

4 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. 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?}

5 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. 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.}

6 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 !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.

7 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:Theendof a proof shouldcomeat theend,notat ,I've deliberatelymadeit 'sa moreilluminatingway of puttingit:Theproof shouldendwiththethingyou'retryingto prove.}

8 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. 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.}}