Proof by Contradiction

In a proof by contradiction we assume, along with the hypotheses, the logical negation of the result we wish to prove, and then reach some kind of contradiction. That is, if we want to prove "If P, Then Q", we assume P and Not Q. The contradiction we arrive at could be some conclusion contradicting one of our assumptions, or something obviously untrue like 1 = 0. Read the proof of the irrationality of the square root of 2 in the introduction for an example.

Here are a few more examples.

Infinitely Many Primes

One of the first proofs by contradiction is the following gem attributed to Euclid.

Theorem. There are infinitely many prime numbers.

Proof. Assume to the contrary that there are only finitely many prime numbers, and all of them are listed as follows: p₁, p₂ ..., p_n. Consider the number q = p₁p₂... p_n + 1. The number q is either prime or composite. If we divided any of the listed primes p_i into q, there would result a remainder of 1 for each i = 1, 2, ..., n. Thus, q cannot be composite. We conclude that q is a prime number, not among the primes listed above, contradicting our assumption that all primes are in the list p₁, p₂ ..., p_n.

Proof by contradiction is often used when you wish to prove the impossibility of something. You assume it is possible, and then reach a contradiction. In the examples below we use this idea to prove the impossibility of certain kinds of solutions to some equations.

Example: A Diophantine Equation

A Diophantine equation is an equation for which you seek integer solutions. For example, the so-called pythagorean triples (x, y, z) are positive integer solutions to the equation x² + y² = z². Here is another.

Theorem. There are no positive integer solutions to the diophantine equation x² - y² = 1.

Proof. (Proof by Contradiction.) Assume to the contrary that there is a solution (x, y) where x and y are positive integers. If this is the case, we can factor the left side: x² - y² = (x-y)(x+y) = 1. Since x and y are integers, it follows that either x-y = 1 and x+y = 1 or x-y = -1 and x+y = -1. In the first case we can add the two equations to get x = 1 and y = 0, contradicting our assumption that x and y are positive. The second case is similar, getting x = -1 and y = 0, again contradicting our assumption.

Example: Rational Roots

There is a formula for solving the general cubic equation a x³ + b ² c x + d = 0, that is more complicated than the qaudratic equation. But in this example, we wish to prove there is no rational root to a particular cubic equation without have to look at the general cubic formula.

Theorem. There are no rational number solutions to the equation x³ + x + 1 = 0.

Proof. (Proof by Contradiction.) Assume to the contrary there is a rational number p/q, in reduced form, with p not equal to zero, that satisfies the equation. Then, we have p³/q³ + p/q+ 1 = 0. After multiplying each side of the equation by q³, we get the equation

p³ + p q² + q³ = 0

There are three cases to consider. (1) If p and q are both odd, then the left hand side of the above equation is odd. But zero is not odd, which leaves us with a contradiction. (2) If p is even and q is odd, then the left hand side is odd, again a contradiction. (3) If p is odd and q is even, we get the same contradiction. The fourth case--p even and q even--is not posssible because we assumed that p/q is in reduced form. This completes the proof.

The Converse of a Theorem

The Converse of "If P, Then Q" is the assertion "If Q, Then P". For example, the converse of "If it is my car, it's red" is "If the car is red, then its mine." It should be clear from this example that there is no guarantee that the converse of a true stement is true.

Proof by Contradiction is often the most natural way to prove the converse of an already proved theorem.

The Converse of the Pythagorean Theorem

The Pythagorean Theorem tells us that in a right triangle, there is a simple relation between the two leg lengths (a and b) and the hypotenuse length, c, of a right triangle: a² + b² = c². Perhaps you don't know that the converse is also true.

The Converse of the Pythagorean Theorem. If the (nonzero) three side lengths of a triangle--a, b and c--satisfy the relation a² + b² = c², then the triangle is a right triangle. (Assume the Pythagorean Theorem has already been proved.)

Proof. (Proof by Contradiction.) Suppose the triangle is not a right triangle. Label the vertices A, B and C as pictured. (There are two possibilites for the measure of angle C: less than 90 degrees (left picture) or greater than 90 degrees (right picture).)

Erect a perpendicular line segment CD as pictured below.

By the Pythagorean Theorem, BD² = a² + b² = c², and so BD = c. Thus we have isosceles triangles ACD and ABD. It follows that we have congruent angles CDA = CAD and BDA = DAB. But this contradicts the apparent inequalities (see picture) BDA < CDA = CAD < DAB (left picture) or DAB < CAD = CDA < BDA (right picture).

Exercises

Use the method of Proof by Contradiction to prove each of the following.

The cube root of 2 is irrational.
There are no positive integer solutions to the diophantine equation x² - y² = 10.
There is no rational number solution to the equation x⁵ + x⁴ + x³+x²+ 1 = 0.
If a is a rational number and b is an irrational number, then a+b is an irrational number.

Next==>Proof by Contrapositive

<==Back To Direct Proofs

Back to Proofs

In Romanian