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:

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

• Could be nice to add a con­crete “real-life” (non-math) ex­am­ple, say like the fol­low­ing:

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: