Proof by contradiction

A proof by con­tra­dic­tion (a.k.a. re­duc­tio ad ab­sur­dum, re­duc­tion to ab­sur­dity) is a strat­egy used by math­e­mat­i­ci­ans to show that a math­e­mat­i­cal state­ment is true by prov­ing that the nega­tion of that state­ment leads to be­ing able to prove that two op­po­site state­ments are si­mul­ta­neously true (a con­tra­dic­tion).

Outline

The out­line of the strat­egy is as fol­lows:

  1. Sup­pose that what you want to prove is false.

  2. Derive a con­tra­dic­tion from it.

  3. Con­clude that the sup­po­si­tion is wrong.

Examples

To illus­trate the con­cept, we will do a sim­ple, non rigor­ous rea­son­ing. Imag­ine your­self in the next situ­a­tion:

You are a defense lawyer. Your client is ac­cused of steal­ing the cookie from the cookie jar. You want to prove her in­no­cence. Lets say you have ev­i­dence that the jar is still sealed. Rea­son as fol­lows:

  1. As­sume she stole the cookie from the cookie jar.

  2. Then she would have had to open the jar.

  3. The jar is still sealed.

  4. For the jar to be sealed and for her to have opened it is a con­tra­dic­tion.

  5. Hence the as­sump­tion in 1 is false (given the de­duc­tions be­low it are true).

  6. Hence she did not steal the cookie from the cookie jar.

Now we will work through an ac­tual math­e­mat­i­cal ex­am­ple: we will show that \(\sqrt 2\) is not ra­tio­nal; that is, it can­not be ex­pressed as the di­vi­sion of two nat­u­ral num­bers.

  1. We sup­pose that \(\sqrt 2\) is ra­tio­nal, which means that there ex­ist \(a,b\in\mathbb{N}\) such that \(\sqrt 2 = \frac{a}{b}\). Without loss of gen­er­al­ity, we can sup­pose that \(a\) and \(b\) have no com­mon di­vi­sors, since oth­er­wise we can just di­vide both num­bers by their great­est com­mon di­vi­sor to ob­tain a pair of num­bers which satisfy both prop­er­ties.

  2. If this was the case, \(b\sqrt2=a\). by squar­ing both sides, we ar­rive to \(2b^2=a^2\). But then \(2\) di­vides \(a\), so we can ex­press \(a\) as \(2n\) for some \(n\in\mathbb{N}\). Sub­sti­tu­ing in the pre­vi­ous ex­pres­sion, we ar­rive to \(2b^2 = 4n^2\implies b^2 =2 n^2\). By the same rea­son­ing, \(2\) must di­vide \(b\), but then \(a\) and \(b\) have a com­mon di­vi­sor! We have a con­tra­dic­tion.

  3. We con­clude that our origi­nal as­sump­tion that \(\sqrt 2\) is ra­tio­nal must be false, and thus \(\sqrt 2\) is not ra­tio­nal.

When to use it

Proof by con­tra­dic­tion is one of the most use­ful tech­niques one can use to prove any­thing.

In par­tic­u­lar, if you get stuck while do­ing a proof, re­sort­ing to proof by con­tra­dic­tion is a great way to keep ex­plor­ing a prob­lem from a differ­ent per­spec­tive. Even if you do not get to solve the prob­lem, you may get a use­ful in­sight about the prob­lem when perform­ing the pro­ce­dure of proof by con­tra­dic­tion.

Also, try­ing to do proof by con­tra­dic­tion may re­sult in a coun­terex­am­ple, which dis­solves the prob­lem in ques­tion.

exercises