Examples of Proof by Contradiction

Example 1: Prove the following statement by Contradiction.

There is no greatest even integer.

Proof:

Suppose not. [We take the negation of the theorem and suppose it to be true.] Suppose there is greatest even integer N. [We must deduce a contradiction.] Then

For every even integer n, N ≥ n.

Now suppose M = N + 2. Then, M is an even integer. [Because it is a sum of even integers.] Also, M > N [since M = N + 2]. Therefore, M is an integer that is greater than the greatest integer. This contradicts the supposition that N ≥ n for every even integer n. [Hence, the supposition is false and the statement is true.]

And this completes the proof.

Example 2: Prove the following statement by Contradiction.

The difference of any rational number and any irrational number is irrational.

Proof:

Suppose not. [We take the negation of the theorem and suppose it to be true.] Suppose ∃ a rational number x and an irrational number y such that (x − y) is rational. [We must derive a contradiction.] By definition of rational, we have

                                 x = a/b        for some integers a and b with b ≠ 0.

and                     x − y = c/d        for some integers c and d with d ≠ 0.

By substitution, we have

                                                x  −  y  =  c/d

                                             a/b  −  y  =  c/d

                                                        y  =  a/b  −  c/d

                                                            = (ad − bc)/bd

But (ad − bc) are integers [because a, b, c, d are all integers and products and differences of integers are integers], and bd ≠ 0 [by zero product property]. Therefore, by definition of rational, y is rational. This contradicts the supposition that y is rational. [Hence, the supposition is false and the theorem is true.]

And this completes the proof.

Example 3: Prove the following statement by contradiction:

The negative of any irrational number is irrational.

First, translate given statement from informal to formal language:

∀ real numbers x, if x is irrational, then −x is irrational.

Proof:

Suppose not. [we take the negation of the given statement and suppose it to be true.] Assume, to the contrary, that

∃ irrational number x such that −x is rational.

[We must deduce the contradiction.] By definition of rational, we have

                                                    −x = a/b  for some integers a and b with b ≠ 0.

                                                         Multiply both sides by −1, gives

                                                      x = −(a/b)

                                                        = −a/b

But −a and b are integers [since a and b are integers] and b ≠ 0 [by zero product property.] Thus, x is a ratio of the two integers −a and b with b ≠ 0. Hence, by definition of ration x is rational, which is a contradiction. [This contradiction shows that the supposition is false and so the given statement is true.]

This completes the proof.

Example 4: Prove the following statement by contradiction:

For all integers n, if n² is odd, then n is odd.

Proof:

Suppose not. [We take the negation of the given statement and suppose it to be true.] Assume, to the contrary, that ∃ an integer n such that n² is odd and n is even. [We must deduce the contradiction.] By definition of even, we have

                                                        n = 2k  for some integer k.

So, by substitution we have

                                                        n . n = (2k) . (2k)

= 2 (2.k.k)

Now (2.k.k) is an integer because products of integers are integer; and 2 and k are integers. Hence,

                                                        n . n = 2 . (some integer)

or                                                        n² = 2. (some integer)

and so by definition of n² even, is even.

So the conclusion is since n is even, n², which is the product of n with itself, is also even. This contradicts the supposition that n² is odd. [Hence, the supposition is false and the proposition is true.]