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:

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

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: 

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:

Step

Reason

1) $m$ divides $n$

Given

2) $n$ divides $p$

Given

3) There is an integer $q$ for which $n=qm$.

Step 1 by defi­nition of division.

4) There is an integer $q'$ for which $p=q'n$.

Step 2 by def­inition of division

5) $p=q'(qm)$

Steps 3 and 4 by substi­tution of equals

6) $p=(q'q)m$

Step 5 by asso­ciative law of multi­pli­cation

7) $m$ divides $p$

Step 6 by defi­nition of division

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.



Creative Commons License

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