Ideas in the Night

Tag Archives: Euclid

In this blog post I present a simple example of a famous antithesis proof. This kind of proof’s philosophy is known as reduction ad absurdum. For the theorem to be proven is presented an antithesis, that says an opposite proposition of the theorem. If proving of the antithesis to be true leads to contradiction, the antithesis is not true, from which it implicates that the original theorem is true.

G.H. Hardy has described this kind of proving as sacrificing the game when comparing proving via antithesis to playing chess.

This example in this blog post is the famous Euclid’s proof that the amount of prime numbers is infinite.

The presented proof is adapted by me from Finnish source, where G. H. Hardy has presented this proof in his book A Mathematician’s Apology.

Statement: The amount of prime numbers is infinite.

Proof.

The prime numbers are numbers

(A) 2, 3, 5, 7, 11, 13, 17, 19, 23, …

that cannot be divided in smaller factors. Furthermore, the prime numbers are building blocks of all numbers by multiplication.

(In this proof from technical reasons number 1 is not considered as a prime number.)

Antithesis: The amount of prime numbers is finite.

Now there exists a greatest prime number P, that’s the greatest prime number. Let’s now examine number Q, that is is defined as follows:

Q = (2 * 3 * 5 * … * P) + 1

From this one can clearly see, that Q is not divisible with numbers 2, 3, 5, …, P, because if Q is divided with those numbers, one get’s always 1 as reminder. But if Q is now not itself a prime number, Q is divisible with some prime number (that can be Q itself), that is greater that the numbers in the list (A). This is in contradiction with the antithesis that proposes that number of prime number is finite. Therefore the antithesis is false and the original statement is true. Thus the amount of prime numbers is infinite.

ID-10080131

Image courtesy of nattavut at FreeDigitalPhotos.net

This Euclid’s proof has been criticized by some logicians; according to them this statement should be proven directly.

This is my translation of my Finnish post about the subject elsewhere. I hope it makes enough sense…

Advertisements