Proof by Contradiction

Tonight I am going to talk a bit about the method of proof by contradiction, but first some things have to be said about the idea of proof in general.

"Proof" in mathematics is stronger than simply "strong evidence" like you would find on a crime show.  Once a statement in mathematics has been proven, that statement is definitely true, and will remain so forever.  While scientific theories can be built up and torn down over a few years, mathematical theorems will never be disproven.

Of course, you can't make something from nothing.  All branches of mathematics involve some underlying axioms, which are taken to be true and then used to prove other results, so the statement "This theorem has been proven true" really means "This statement has been proven true under a particular axiom system (usually implied by context)."  A good axiom system should use very few axioms, and they should be things that are otherwise unprovable.  For example, the axioms of number theory (which you use for basic arithmetic) essentially say that we have the number 1 and the power to add 1 to any number we have to get another number.  From there, it is possible to prove all the rules of arithmetic.

But tonight we're talking specifically about proof by contradiction.  To prove a statement by contradiction, you begin by assuming that what you want to prove is actually not true, and explore the consequences under your chosen axiom system until you reach a conclusion that contradicts some part of your axiom system or conclusions drawn from it.

This all sounds a bit technical, but you've probably used some form of this method in your daily life.  For example:

Mom didn't have her coffee this morning.
How do you know? 
If she had had her coffee this morning, she wouldn't be so irritable right now.


Clearly, this is not an airtight argument.  Perhaps mom is irritable because she didn't sleep last night, or because she's nervous about a big meeting at work, or because the cat threw up in her shoes.  But the idea behind the argument is simple enough, and mathematicians take this simple idea and make it rigorous.

Euclid's proof that there are infinitely many prime numbers (numbers which can only be divided by 1 and themselves (for example, the number 3)) provides a favorite example among mathematicians of proof by contradiction.  This proof relies only on some basic arithmetic.  Note that 1 is not considered a prime number.

We want to show that the number of prime numbers exceeds any finite quantity (Euclid would not have used the word "infinite").  Toward this end, let us assume that this is not the case.  In other words, for some finite quantity n, there are exactly n prime numbers.

If this is the case, then we can make a finite list of all the prime numbers.  Let's call them p₁, p₂, and so on up to p_n.

Now let's make a new number, N, defined by N=p₁ x p₂ x ... x p_n+ 1 (the product of all our primes, plus one), which we can do because the rules of arithmetic allow us to add and multiply numbers.

Since the product of two numbers is not less than either of the two numbers involved (we're working only with whole numbers in this proof, no fractions) and adding one makes it bigger still, N is larger than any number on our list of primes.

Therefore, N cannot be on our list of primes, and so (by our assumption that our list contained every possible prime), N is not prime.  Any number that is not prime is composite (this is the definition of a composite number).  Since N is composite, there is some prime that divides it evenly (another theorem, perhaps for another day).  By our initial assumption, all possible primes are on our list, so N must be divisible by one of those.

We can assume that it is divisible by p₁ (we can simply reorder our list so that the smallest prime dividing N is first).

Because p₁ divides N, N/p₁ is a whole number (this is what we mean when we say one number divides another).

What does N/p₁ look like?

N/p₁=p₂ x p₃ x ... x p_n + 1/p₁
 

Now we have a problem.  p₂ x p₃ x ... x p_nis a whole number, since a product of whole numbers is a whole number.  But 1/p₁ is a fraction, and the sum of a whole number and a fraction is not a whole number, as we had expected N/p₁ should be.  It's not that we used the wrong prime; we reordered the list so that the right prime would be p₁.  This tells us that there is no prime on our list that will divide N.


This leaves two possibilities.  Either N itself is prime, or it is composite but divisible by some prime not on the list.  In either case, our list was insufficient to cover all the primes.  And since n was any arbitrary finite number, and no part of the proof depended on any other property of n, this tells us that any finite list of primes is insufficient.  Thus there are infinitely many prime numbers.


The difference between this and the coffee example above is that every step of the argument after the faulty assumptions was mathematically correct (unlike the leap from coffee to lack of irritability).  Thus, the only possible flaw in the argument was the initial assumption.

I have heard philosophers claim that a proof by contradiction is less informative than a direct proof because it provides no insight beyond the truth of the theorem.  I tend to disagree with that assertion, and this proof supports my view: it provides a way of generating prime numbers (whether instantly or after a factorization).

Philosophers will also be quick to point out that this method of proof relies on an assumption that any statement is either true or false, but never both (if a statement could be neither true nor false, showing that its negation is not true is not sufficient to show that the statement is true; if a statement could be both true and false, it would be much more difficult (to sat the least) to reach a contradiction).  Here they are correct, but let me reassure you; all of mathematics works under the assumption that no mathematical statement is both true and false (we say math is "consistent"--if this were not the case there would be nothing we couldn't prove), and while there are statements that are not decidable (can't be proven either way (a really interesting topic to be explored another day)) I know of no branch of mathematics that assumes that some statements are inherently neither true nor false.

I realize that today was somewhat technical, but I hope I was able to explain everything adequately and that you've learned something from it.  Tune in tomorrow for a fun story!