Produced by Charles Wells.  Home.   Website Contents     Website Index   

Back to top of Proofs chapter

Posted 10 March 2009

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.

Contents

Narrative proofs. 1

A detailed look at a proof 1

Analysis of this proof 2

Five levels of the proof 2

Expanding proofs. 3

Other examples of proofs. 4

Narrative proofs

Mathematical proofs in texts and in lectures are usually presented in  narrative format , written in math English.   Less commonly, proofs may also be written in one of the formats of symbolic logic.

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.  See theorem.

¨  The proof will include the proof steps the author thinks are not easy or obvious, but may omit easy steps, including 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.

¨  The proof will use various conventions that are intended to communicate the logic of the proof. 

Your problem in reading a narrative proof is to determine the logical structure of the proof from the narration.  See translation problem.

A detailed look at a proof

Here is a short proof to illustrate these ideas.

Definition: Divides

Let m and n be integers with . The statement “m divides n” means that there is an integer q for which .

For example, “3 divides 12” is true because  (in this case,  ). 

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 of a textbook.  This is in the form of a direct proof.

By definition of divides, there are integers q and q’ for which  and . We must prove that there is an integer  for which . But , so let .  Then .

Analysis of this proof

By definition of divides, (gives a reason)

there are integers q and q’ for which  and . (proof step 1)

We must prove that there is an integer  for which . (statement of goal)

But , (proof step 2, an algebraic calculation based on step 1)

so let , which gives .  (proof step 3  which follows from step 2, although the proof does not say so)

Proof step 2 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:

 (by proof step 1)

 (by proof step 1)

  (substitution)

Proof step 3 hides part of a reason, too:  Proof step 2 really gives us , but the statement that we want to prove, “  “, requires that we know that .  This is OK, because the associative law for multiplication says that . 

¨  This analysis shows how the proof leaves out the reasons for some steps and also condenses some steps into an algebraic calculation. 

¨  This proof is intermediate in the amount of detail it gives.

¨  We 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, we 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.

Five levels 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.

Short proof:

Proof: , where  and .

This proof requires pattern recognition: 

¨  You have to recognize  as having the form  for some integer . 

¨  You have to recognize that  fits the requirement of the definition of “divides”.

The proof given previously:

  By definition of divides, there are integers q and q’ for which  and . We must prove that there is an integer  for which . But , so let ; then .

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  and . To prove that m divides p, we must prove that there is an integer  for which ; then the statement m divides p follows from the definition of division. We have seen that  and , and so by substitution of equals, .  Then  by the associative law for multiplication. Thus if we let , then  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!

Expanding proofs

Any correct proof can be expanded in principle to give a detailed proof that puts in every step and gives a reason for every step, as in the two-column format given above. I say “in principle” because in practice, although you can expand some of the steps of a proof, it is not practical to expand “all the way” all the steps of a long proof.

Other examples of proofs

Several examples are in the chapter on forms of proofs.

Density of the reals

An epsilon-delta proof

Equality of  and 1.0.

See also References on proofs