Produced by Charles Wells Revised 2017-01-15 Introduction to this website website TOC website index Head of Math Reasoning Chapter blog
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.
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.
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.
Here is a short proof to illustrate these ideas.
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.
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$.
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$.
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.
Here are five possible forms of the proof as they might appear in texts written for people of different levels of expertise.
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."
Proof: $p=q'qm$, where $n=qm$ and $p=q'n$.
This proof requires pattern recognition:
$n=qm$and
$p=q'n$are the consequences of rewriting the assumptions by using the definition of "divides".
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$.
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$.
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 definition of division. |
4) There is an integer $q'$ for which $p=q'n$. |
Step 2 by definition of division |
5) $p=q'(qm)$ |
Steps 3 and 4 by substitution of equals |
6) $p=(q'q)m$ |
Step 5 by associative law of multiplication |
7) $m$ divides $p$ |
Step 6 by definition 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!
Several examples are in the chapter on forms of proofs.
Density of the rational numbers
Communicating mathematical reasoning, by Atish Bagchi and Charles Wells.
Varieties of mathematical prose, by Atish Bagchi and Charles Wells.
Thanks to Justin Benjamin for a correction to the proof analysis.
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.