abstractmath.org 2.0
help with abstract math

Produced by Charles Wells     Revised 2017-01-15

Introduction to this website    website TOC    website index

Head of Math Reasoning Chapter   blog

PRESENTATION OF PROOFS

This chapter describes how proofs are written, with an extended analysis of a particular proof.  The chapter on forms of proof goes into more detail about certain types of proof.

Narrative proofs

Mathematical proofs in texts and in lectures are usually presented in narrative format, written in math English.

A narrative proof typically has characteristics like these:

• The proof is preceded (or sometimes followed) by a statement of what is to be proved, which is called a theorem, proposition, lemma or corollary.
• The proof includes the proof steps the author thinks are not easy or obvious, but may omit easy steps, in particular algebraic calculations.
• Sometimes the reason for a step comes before the step, sometimes afterward, sometimes it is not given at all.
• Mixed in with the proof steps are other statements such as motivating statements, summaries, and statements about what comes next. (See Varieties of mathematical prose.)
• The proof will use various conventions that are intended to communicate the logic of the proof.

A narrative proof is a sequence of hints
intended to help you discover
the logical structure of the proof.

Difficulties

Learning to read a narrative proof is like learning to read text in a foreign language. It is much easier to learn to read a narrative proof than a story in another language, but it still requires considerable effort and practice to get good at it. See translation problem.

Many professional mathematicians don't in fact put much effort into reading proofs. It is common for us to read the statement of the theorem and then to start thinking about the proof with occasional glances at the written proof to get hints. A lot of the proofs in math texts are badly written, which doesn't help.

When you read a proof you may get stuck trying to see how the author thought up one of the steps in the proof. This can be much harder that simply trying to see if the proof is correct. If you see a step you think would not have occurred to you, but you understand it, then don't feel intimidated. After all, you have learned a new trick for proving things! See Rabbits and Look ahead.

A detailed look at a proof

Here is a short proof to illustrate these ideas.

Definition: Divides

Let $m$ and $n$ be integers with $m\ne 0$. The assertion “$m$ divides $n$” means that there is an integer $q$ for which \[n=qm\]For example, “$3$ divides $12$” is true because $12=4\cdot 3$ (in this case, $q=4$).

Note that in the assertions “$m$ divides $n$” and "$n=qm$", $m$ and $n$ are reversed. This has caused some of my students no end of confusion.

Theorem

Let $m$, $n$ and $p$ be integers with $m$ and $n$ nonzero, and suppose $m$ divides $n$ and $n$ divides $p$. Then $m$ divides $p$.

Proof

Here is the proof in the usual narrative format that might appear in a textbook.  This is in the form of a direct proof.

By definition of divides, there are integers $q$ and $q'$ for which $n=qm$ and $p=q'n$. We must prove that there is an integer $q''$ for which $p=q''m$. But $p=q'n=q'qm$, so let $q''=q'q$.  Then $p=q''m$.

Analysis of this proof

1. Assume $m$ divides $n$ and $n$ divides $p$. (This step is invisible. I am using the direct method, without saying so.)
2. By definition of divides, (signal that I am rewriting the assumption according to the definition)
3. there are integers $q$ and $q'$ for which $n=qm$ and $p=q'n$. (assumption is now rewritten)
4. We must prove that there is an integer $q''$ for which $p=q''m$. (statement of goal using the definition of divides without saying so)
5. But $p=q'n=q'qm$, (an algebraic calculation based on proof step 3)
6. so let $q''=q'q$, (define $q''$)
7. which gives $p=q''m$. (follows from proof steps 5 and 6)
8. Therefore $m$ divides $p$. (This is what I had to prove. It follows from the defiition of divides, but the proof does not say so.)

Remarks

• Step 3 of the analysis is where some students commit existential bigamy.
• Analysis step 5 contains an algebraic calculation.  Algebraic calculations are based on rules just like other proof steps, but texts above the beginning level rarely make them explicit.  Here are the explicit rules:
  • $p=q'n$ (by step 3)
  • $n=qm$ (by step 3)
  • $p=q'qm$  (substitution)
  This particular algebraic calculation is extremely simple. Proofs often leave out much more elaborate calculations.
• Note that analysis step 7 hides a use of the associative law. Students will never notice this, but a computer generated proof would have to include it.

This proof is intermediate in the amount of detail it gives. I could rewrite the proof into a much more detailed one that puts in more steps and reasons, giving a detailed proof. On the other hand, I could have condensed it much more into a short proof. Sometimes, it helps to put a proof into two-column format , with the steps in the left column and the reasons in the right column. All of these version are given below.

There is an analysis of the context of this proof in the article on context.

Five versions of the proof

Here are five possible forms of the proof as they might appear in texts written for people of different levels of expertise.

Omitted proof:

Monographs written at the graduate level or higher would omit this proof altogether or else say something like: "Proof: Easy," or "Division is clearly transitive."

Short proof:

Proof: $p=q'qm$, where $n=qm$ and $p=q'n$.

This proof requires pattern recognition: 

• You must recognize that $n=qm$ and $p=q'n$ are the consequences of rewriting the assumptions by using the definition of "divides".
• You have to recognize $q'qm$ as having the form $q''m$ for some integer $q''$. 
• You have to recognize that $n=q''m$ fits the requirement of the definition of “divides”. (Don't sneer. It is the case that some very newbie students are bothered by the fact that the definition required $qm$ and we are giving them $q''m$. Such students may never become research mathematicians but they still want to learn some math and we need to help them do it.)

Medium proof (the proof given previously):

 By definition of divides, there are integers $q$ and $q'$ for which $n=qm$ and $p=q'n$. We must prove that there is an integer $q''$ for which $p=q''m$. But $p=q'n=q'qm$, so let $q''=q'q$; then $p=q''m$.

Very detailed proof:

Proof: We are given that $m$ divides $n$ and $n$ divides $p$. By definition of division, there are integers $q$ and $q'$ for which $n=qm$ and $p=q'n$. To prove that $m$ divides $p$, we must prove that there is an integer $q''$ for which $p=q''m$; then the statement $m$ divides $p$ follows from the definition of division. We have seen that $n=qm$ and $p=q'n$, and so by substitution of equals, $p=q'(qm)$.  Then $p=(q'q)m$ by the associative law for multiplication. Thus if we let $q''=q'q$, then $p=q''m$ by substitution of equals.  It follows from the definition of division that $m$ divides $p$.

Detailed proof in two-column format:

Proofs in two column format have the advantage that they are very explicit.  If you are stuck or confused about a proof, it helps to write it (or the tough part of it) out in two-column format. Doing that puts everything in front of you.  You don’t have to remember where you got something.  And if you can’t fill in a reason, then you have discovered that your proof is incomplete!

Other examples of proofs

Several examples are in the chapter on forms of proofs.

Density of the rational numbers

An epsilon-delta proof

Look ahead.

References

Communicating mathematical reasoning, by Atish Bagchi and Charles Wells.

Varieties of mathematical prose, by Atish Bagchi and Charles Wells.

Acknowledgments

Thanks to Justin Benjamin for a correction to the proof analysis.

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.