Indirect Proofs

Proofs by Contradiction

A proof by contradiction works this way:

step 1: Assume the opposite of what you want to prove.

step 2: Work out the consequences of your assumption and show that this leads to a mathematical impossibility, or contradiction.

Here is a classic example.

Example: Prove that the number is irrational.

Solution: An irrational number is a real number that cannot be represented as the ratio of two integers in lowest terms. Conversely,

all rational numbers can be represented as the ratio of 2 integers in lowest terms.

For example,

is a rational number. That's because, even though it is currently written as a repeating decimal, it CAN be represented as

Therefore, to prove that is not rational, we first ...

step 1: Assume that can be written as the ratio of two integers in lowest terms. In other words, assume that there exists two

integers

and such that

where

and have no divisors in common i.e. the fraction is in lowest terms. Our goal is to show that this leads to a contradiction.

step 2: Square both sides of that equation to get

and

This clearly shows that is a multiple of 2; therefore, since 2 is prime, that means that itself is a multiple of 2. Hence,

there exists an integer

such that . Substitute this back into the equation to get

From this we can see that

must also be a multiple of 2. What a minute! Didn't we say that and have no common factors? We've

reached a contradiction. Therefore, our original assumption, namely that

is rational, must be wrong. We've proven that is irrational.

Purple Question: Prove that there is an infinite number of primes by using the following (ancient) method:

Assume that there is a finite number of primes

. Now define the number

What can you say about this number N?

Reductio ad Absurdam

There is another method of indirect proof that relies on making an initial assumption that is the opposite of what you want to prove. You then

show that this argument can be continued indefinitely, meaning forever and forever, and thereby lead to a mathematical absurdity.

Here is an example.

Example: Prove that where is any prime number number, is irrational.

Solution: This problem could be solved using straightforward indirect proof just like we did above, but let's see how the reductio ad

absurdam argument works.

First, assume that

where

and are integers.

By squaring both sides and doing some algebra we get

and therefore

. (*)

At this point, it probably looks like the proof we did for the irrationality of , however you may notice that I didn't assume that and have no common divisors.

This statement shows that is divisible by hence, since is prime, that means that is divisible by . Therefore, there

exists an integer

such that . Plug this in.

and hence

From this we see that

is also divisible by , so is divisible by , and therefore there exists an integer such that . Plug this in.

This last equation is similar to (*). It shows that

is divisible by and hence, must be divisible by . We could continue this

argument in a similar manner, showing that

is divisible by and then and then and then.... raised to any whole number power.

But how can an integer

be divisible by by ANY power of ? This is absurd because must have a finite number of prime factors.

must equal 0 and is certainly not 0. We've reached the point where the argument, carried on indefinitely, leads to an absurdity.

Hence, our original assumption must have been incorrect.

is irrational.

Page updated

Google Sites

Report abuse