1
Methods of Proof
In this introductory chapter we explain some methods of mathematical proof. They
are argument by contradiction, the principle of mathematical induction, the pigeonhole
principle, the use of an ordering on a set, and the principle of invariance.
The basic nature of these methods and their universal use throughout mathematics
makes this separate treatment necessary. In each case we have selected what we think
are the most appropriate examples, solving some of them in detail and asking you to train
your skills on the others. And since these are fundamental methods in mathematics, you
should try to understand them in depth, for “it is better to understand many things than
to know many things’’(Gustave Le Bon).
1.1 Argument by Contradiction......................................
The method ofargument by contradictionproves a statement in the following way:
First, the statement is assumed to be false. Then, a sequence of logical deductions yields
a conclusion that contradicts either the hypothesis(indirect method),or a fact known to
be true(reductio ad absurdum). This contradiction implies that the original statement
must be true.
This is a method that Euclid loved, and you can find it applied in some of the most
beautiful proofs from hisElements. Euclid’s most famous proof is that of the infinitude
of prime numbers.
Euclid’s theorem.There are infinitely many prime numbers.
Proof.Assume, to the contrary, that only finitely many prime numbers exist. List them
asp 1 = 2 ,p 2 = 3 ,p 3 = 5 ,...,pn. The numberN=p 1 p 2 ···pn+1 is divisible by
a primep, yet is coprime top 1 ,p 2 ,...,pn. Therefore,pdoes not belong to our list of
all prime numbers, a contradiction. Hence the initial assumption was false, proving that
there are infinitely many primes.