A Note on Proofs Joe Rabinoff October 11 2004 I originally wrote this note in the fall of 2002 for the benefit of the students taking Math 23a at Harvard University who were under the excellent instruction of John Boller Math 23 is a first year class introducing rigorous calculus and linear algebra and was designed to be the first experience most of its students had with pure math and in particular with proofs Being a course assistant and grader I wrote this note from a grader s perspective immediately after having graded the first homework assignment 1 It addresses the more important things one must do when writing proofs and points out the most common mistakes If you ve never written a mathematical proof before and have some desire to do so then this note is for you A proof at its base is an argument I assume that you know how to make persuasive arguments everybody has had late night philosophical debates with roommates If you are asked to prove for instance that there are an infinite number of prime numbers then your job is to convince the reader of the truth of that statement Your proof should read like any other written argument it should have a thesis it should have a logical progression and it should be in grammatically correct English 2 But there is an essential difference between a mathematical proof and a philosophy paper a mathematical proof should be so precise that there is theoretically no room for error None That s the beautiful thing about pure mathematics it s the only subject in which you can be absolutely sure of the truth of your statements It s not enough to find overwhelming evidence for a statement in order to prove its truth You can leave no room to doubt that what you say is completely correct The proof then were you to write it out in full would be extremely longwinded because every step must be meticulously exact This is where mathematical notation comes in common precise constructions like for all x in the set A can be shortened to x A This is the first important point about writing proofs were you to expand out all of the notation e g replace each x with there exists an x you should have a grammatically correct paper As with any argument a proof is a logical path from a starting point to an ending point So in order to write one the first thing to do is start with a precise 1 I then threw that version away and rewrote it the next morning so that I would sound helpful instead of frustrated 2 Unless your class is being given in another language in which case it s bizarre that you re reading this note 1 statement of your assumptions and work towards a precisely stated conclusion By precise I mean something totally unambiguous with nothing left for interpretation For example the prime factorization theorem might be stated Every n N can be written as a product n pa1 1 pa2 2 pamm where p1 pm are distinct prime numbers and a1 am are natural numbers For more examples read the statements of the lemmas and theorems in your textbooks The only mathematical way to get from the assumptions to the conclusions is by making precise logical deductions that is statements that use facts that you know or have already shown and imply other facts Each statement should again be totally unambiguous and have impeccable support you must be able to justify each statement with a mathematical reason that cannot be argued like a theorem out of a book e g if p is prime and n is any natural number then there exists a nonegative integer m such that pm divides n but pm 1 does not because of the existence of prime factorizations There cannot be any room for the reader to say but what if or now why is that every statement must be infallible Again this is the beauty of mathematics whereas one rarely wins a philosophical debate with one s roomates especially at three in the morning the correctness of a mathematical argument cannot be debated It s just true This does not mean that you have to write down every step this would make your proofs impossibly long even with generous use of math notation For instance you do not have to cite the distributive and associative properties of the real numbers to say that a b c d ac ad bc bd but you should know how to prove it in case someone doesn t believe that step In each case use your judgment about whether the logical leap you are about to make is small enough that it does not require further justification If done well this will make your proofs much less tedious while still not leaving any of your statements up for debate you simply leave out few enough logical steps that the reader can easily fill them in At this point however what you should consider is whether the grader will believe that you know how to fill them in There are also several things to avoid when writing a proof One of the most common mistakes is to write a proof by example A proof by example is not a proof Examples are never necessary in a proof and are only relevent if there are only a finite number of cases and you prove them all For instance if you prove that 10 has a prime factorization 2 5 then that s great but you haven t proved that 12 has a prime factorization too If your proof for 10 generalizes to any natural number then write the general proof the specific case will follow It is often helpful to work out an example if you don t know how to prove something in general but you still need to do the general proof afterwards So you can usually omit any examples if you find yourself needing to insert them for clarity then you should usually try to make your general proof more clear Adding examples when it s not necessary can serve to clutter your proofs and confuse your reader at least until you re more fluent at proof writing It is likely as you take more advanced classes and have to write harder proofs that you will run into situations where an abstract definition or a statement would become much more concrete if an example is added in that case an example may be justified to the extent that it helps your reader understand the general 2 definition or proof which is the importart part For the moment it s probably best to leave out examples until you re confident in your proof writing abilities The same rules apply to writing down your intuition for a proof it s never necessary for the proof and it is often best to omit it I don t mean to say that intuition is unimportant on the contrary mathematical intuition is the absolute most valuable thing a mathematician can have it s