Produced by Charles Wells.  Home.   Website Contents     Website Index   Blog

Back to top of Proofs chapter

Last edited 8/21/2009 10:14:00 AM

FORMS OF PROOF

A proof written in narrative form is very often arranged in one of a few basic forms. Authors don’t usually tell you which form they are using.  To understand proofs, you need to recognize these forms.  This chapter describes them and shows examples.

Contents

Proving conditional assertions: The direct method. 1

Proving conditional assertions: The contrapositive method. 2

Proof by Contradiction. 3

Proving equivalences. 5

Uniqueness theorems. Error! Bookmark not defined.

Proving conditional assertions: The direct method

Method: To prove “If P, then Q”  assume P is true and deduce that Q must be true as well.  This form of proof is called the direct method.

Note:  In the process of proving Q, you would expect to use other facts that you know as well as the assumption that P is true.  

Easy example

Remember that the integer n is even if there is an integer m for which n = 2m. 

Theorem

If n is even, then  is even.

Narrative proof by the direct method

Suppose that n is even.  Then by definition of “even” there is an integer m for which n = 2m.  Then .   is an integer because m is an integer, so by definition of “even”,  is even.

Remarks

¨  In this proof, P is “n is even” and Q is “  is even”. 

¨  The author does not tell you that the proof of “If P, then Q”  is by the direct method.  But you can detect the pattern when the proof starts with “Suppose that n is even”, in other words, “Suppose P”. 

¨  A proof using the direct method is called a direct proof.   You undoubtedly already knew how to give a direct proof.  This article is intended to raise your knowledge to a conscious level (if it isn’t already there).  

¨  This is an example of a proof by rewriting according to the definition of the words in the theorem.

¨  The name “direct method” is not common usage.  I believe it originated with Daniel Solow’s book How to Read and Do Proofs. 

Coming up with proofs

In a more complicated situation, you might have to prove

If P then ,

If  then ,

…

If  then Q

using a sequence of deductions. 

Normally, although your final proof would be written up in that order, you would not think up the proof by thinking up , , … in order. What usually happens is that you think of statements which imply Q, statements which imply them (backing up), and at the same time you think of statements which P implies, statements which they imply (going forward), and so on, until your chain meets in the middle (if you are lucky).

A very sad tale

This has happened to my students many times: 

¨  You are asked to prove “If P, then Q.”

¨  You assume Q. 

¨  You find statements “If Q, then P₁”, If P₁ then P₂”, …, If P_k then P” that you prove, or think you have proved.

¨  You triumphantly conclude  “If P, then Q.”

¨  You get your paper back and that problem is marked wrong. Zero points.  Zilch. 

You constructed your proof backward.  If all the steps are right, you might even have correctly proved “If Q then P”.  But you were asked to prove “If P then Q”.  How sad .

Students often prove P = Q by proving Q = P₁, P₁ = P₂, …, P_k = P.  This is perfectly correct, because “P = Q” is symmetric in P and Q.  Unfortunately, “If P then Q” is not symmetric in P and Q. 

Proving conditional assertions: The contrapositive method

Method: To prove “If P, then Q”  assume Q is false and deduce that P must be false as well.  

This method is the Direct Method applied to “If not Q, then not P.”  That is the contrapositive of “If P, then Q” but proving the contrapositive of P is the same thing as proving P, since a conditional sentence and its contrapositive always have the same truth value.

Example

Theorem

If  is even, then n is even.

Narrative proof by the contrapositive method

Suppose n is odd.  Then for some integer k, n = 2k + 1.  Then .  Thus  for some integer h, so  is odd.  QED.

Remarks

¨  The proof of the contrapositive proceeds like any direct-method proof, by assuming the hypothesis ( n is odd) and deducing the conclusion (  is odd)  but the hypothesis and conclusion are those of the contrapositive of the theorem as stated.

¨  If you didn't think of proving the contrapositive, you might be dumbfounded when you saw that a proof of a theorem which says "if  is even then n is even” begins with, "Let n be odd.”  (See translation problem and walking blindfolded).   

But that is a clue …

Proof by Contradiction

Method:  

To prove that an assertion P is false, prove that “If P then Q” is true and that Q is false.  This method is called proof by contradiction or reductio ad absurdum, sometimes abbreviated r.a.a.

I will give an example proof and then talk about why it works.

Example

Theorem

The number  is not rational.

Typical narrative proof

Let  where m and n are positive integers.  Then by definition of log, , so .  This is impossible because every positive power of 10 is even and every positive power of 3 is odd.  QED.

 

 Analysis of the proof

In this proof, P is the statement “  is rational” and Q is the statement “An even integer cannot equal an odd integer.” 

¨  The proof proceeds by contradiction, which means it must prove “If P, then Q” .

¨  It proves “If P, then Q” by the direct method. 

¨  Therefore it starts with the unstated assumption that  is rational. 

¨  By rewriting according to the definition of “rational”, we get  where m and n are positive integers.  This is the first actual statement in the proof. 

¨  Then it uses the definition of log to conclude . 

¨  Using the algebra of exponents, it concludes that  (a certain even integer equals a certain odd integer)..

¨  The statement “Every positive power of 10 is even and every positive power of 3 is odd” is then made without proof (regarded as common knowledge)..

¨  It claims a contradiction, without stating the fact Q (also regarded as common knowledge) that it contradicts. 

Remarks

¨  This analysis of the proof is an example of the translation problem.

¨  Note that a direct proof is impossible (note) 

¨  Authors sometimes tell you they are doing a proof by contradiction, and sometimes don’t.

¨  In practice it frequently happens that Q is obviously false so that the work goes into proving “If P then Q.” Thus a proof that P is false might begin, "Suppose P is true..."!   That is a clue that you are reading a proof by contradiction.

Example: Powerset theorem

This example may be hard to understand, not because it is a proof by contradiction, but because it uses the method of comprehension, which many beginners in abstract math find difficult to understand. 

Let S be a set and let  be the power set (set of all subsets) of S.  Then there is no surjective function  . 

Proof

Suppose  is a function.  Let .  Then A is a subset of S, so it is an element of .  Now I will show that there is no element x of S for which F(x) = A.  Proof:  There are two cases:

¨  .  Then if F(x) = A, then  by the method of comprehension.  This is a contradiction.

¨  .  Then if F(x) = A, then  by the method of comprehension.  This is also a contradiction.

There is no other possibility, so there is no element x of S for which F(x) = A.  Therefore F is not surjective.

Examples

Let .  Then .  

¨  Define  by

F(1) = {2, 3}

F(2) =  

F(3) = {1, 2, 3}

Then A = {1, 2}. 

¨  Define  by

G(1) = {1, 2}

G(2) =  

G(3) = {1, 3}

Then A =  {2}. 

¨  Define  by

H(1) = {2, 3}

H(2) = {3}

H(3) = {1, 2}

Then . 

 Of course, in this case you could prove that no function could be surjective because S has 3 elements and  has 8 elements.  The remarkable thing about the proof by contradiction is that it works for infinite sets.

Proving equivalences

Proof by cases.

Also called proof by exhaustion.  For now, see what Wikipedia says.

Uniqueness theorems

Appendix

Impossibility of finding a direct proof that

 is irrational

 You can’t try every pair of integers m and n to see that  because there are an infinite number of pairs.   

In any case there are pairs m and n that will give you the first googol digits of  correctly.  (Why?) You can’t calculate the first googol digits, so you could not carry out the calculation for such a pair in your lifetime.

 Still, you know there is no rational number that gives  to infinite precision because we have proved there is no such number, by contradiction.  return