abstractmath.org

help with abstract math

`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

# 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

 This theorem, like many theorems in mathematics, is a universal conditional assertion, so the proof uses universal generalization to show that if n is an arbitrary positive integer satisfying the hypothesis, then it must satisfy the conclusion.

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”.

¨  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).

Thinking up a proof is a CREATIVE ACT

not a mechanical one of grinding out conclusions from hypotheses

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 P1”, If P1 then P2”, …, If Pk 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 = P1, P1 = P2, …, Pk = 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 Qbut 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 …

If a theorem has the form “If P then Q” and the proof begins with “Assume Q is false…”, that is a CLUE that the form of the proof is by contrapositive!

#### 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.

The proof does not say it is a proof by contradiction,

and neither P nor Q is stated explicitly in the proof.

This is very common in narrative proofs

GET OVER IT.

### 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.

 The powerset theorem is a generalization of Cantor’s Diagonal argument, which Cantor discovered when trying to understand how infinity comes in different sizes.

## 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.

# Proof by cases.

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

# Appendix

#### Impossibility of finding a direct proof that MPSetEqnAttrs('eq0045','',3,[[29,10,3,-1,-1],[39,14,4,-1,-1],[50,18,5,-1,-1],[45,16,5,-1,-1],[60,22,6,-1,-1],[75,27,8,-1,-1],[123,44,12,-2,-2]]) MPEquation() MPNNCalcTopLeft(document.mpeq0045ph,'') MPDeleteCode('eq0045')  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