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^{2} 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^{2} 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} = 2. (some integer)

and so by definition of n^{2} even, is even.

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