Proof by contradiction/Square root of 2 and Euclid/Introduction/Section

From Wikiversity
Jump to navigation Jump to search

We give two classical examples for a proof by contradiction.

There does not exist a rational number such that its square equals . This means that the real number is irrational.

We make the assumption that there exists some rational number whose square equals , and we have to derive a contradiction from this. Our assumption means the existence of

fulfilling the property

A rational number can be written as a fraction, where numerator and denominator are integers. Hence, the rational number has the form

Moreover, we can suppose that this fraction has been reduced to its lowest terms, so that the greatest common divisor of and is . In fact it is enough to suppose that at least one of and are odd (if both are even we can divide both by until one gets odd). The property

means then

Multiplication by yields

(this is an equation in and even in ). This equation means that is even, since is a multiple of . This implies that itself is even, because the square of an odd number is again odd. Therefore, we can write

with an integer . Putting this into the equation, we deduce

Dividing both sides by we obtain

Hence, also is even and so is even. But this is a contradiction, as and are not both even.

The following theorem is called Theorem of Euclid.

There exist infinitely many prime numbers.

We assume that the set of all prime numbers is finite, say is a complete list of all prime numbers. We consider the number

This number can not be divided by any of the prime numbers , since the reminder of by division through is always . Hence, the prime factors of , which exist due to fact, are not contained in the given set. This is a contradiction.