Remember Me
forgot your password?

Proof by Contradiction

The phrase "reductio ad absurdum" literally means reduction to absurdity, and it describes an ancient method of proof which we tend now to call by the name of "Proof By Contradiction."

In this method of proof, we take the proposition we are trying to prove, and assume that the opposite is true. Then we follow a logical argument until we reach a conclusion which contradicts our original assumption. Then we know that the assumption was false, and so we have proved what we wanted to prove.

There are many very beautiful and elegant proofs which use this method. One of my favorites is the Proof of the Infinitude of Primes, given by Euclid. I shall try to present the proof here without using any too technical language!

Before we start, we have to talk about numbers. Everyone knows that if you start counting from the number 1 you could go on for ever without stopping. The way we describe this is that the set of counting numbers is an infinite set. There is no number of which you can say, this is the biggest one, we've now reached the end!

There are some special numbers in the set that have a peculiar property. These are called the Prime Numbers. A prime number can only be divided by itself or the number 1.
For example, 17 is only divisible by 17 or 1, whereas a number like 15 is divisible by 1, 3, 5, and 15 itself. So 17 is a prime, but 15 is not.

Now the question arises, is the set of prime numbers an infinite set? Do the prime numbers go on for ever, or is there a number to be found of which we can say, this is the largest prime number, and there are no more after this?

At first sight, you might think that there IS a largest prime, because as you count higher and higher, there are more smaller numbers that can potentially divide into the number you have reached. However, Euclid believed that they went on for ever, that there was an infinitude of primes. And he proved it, using reductio ad absurdum, proof by contradiction.

First, assume that there is a largest prime number, we give it the label p, and this number is divisible only by itself and 1.

Now we construct a (much larger) number by multiplying together all the prime numbers from 2 up to our number p. We label this number N.

Now, by definition, N is divisible by 1, 2, 3, and all the prime numbers up to and including the number p.

Now consider the number that follows the number N, we will label it (N+1). This number is certainly divisible by 1 and itself, as all numbers have that property. But it is not divisible by 2, since the previous number N is divisible by 2. Also, for the same reason, (N+1) is not divisible by 3, 4, 5, and so on all the way up to N, the number just before it.

Therefore we are forced to conclude that (N+1) is a prime number. But this contradicts our original assumption, since (N+1) is larger than p, and you remember that we assumed p to be the largest prime. Therefore our assumption must be false and hence there is no largest prime number.

Thus we have proved that the set of prime numbers is an infinite set.

Author's Note: The article above was first published by me on Qassia. To find out more about Qassia, and what makes it different from other sites, please visit my Qassia page on http://zencath.qassia.com/

Robert Paterson

Robert Paterson writes on a wide variety of subjects. Currently he is involved with a project designed to raise awareness of the benefits of water filters in the home. You are invited to visit his blog http://purewaterstore.blogspot.com/ to find out more about this.

Rate this Article: 5 / 5 stars - 1 vote(s)
Print Email Re-Publish

Add new Comment



Captcha

  • Latest Science Articles
  • More from Robert Paterson

Tips for Winning a Science Fair Project with a Rock Set

By: Joe Kanooga | 09/12/2009
Collecting rocks is a popular hobby that kids and adults can enjoy together. More than just a fun activity, rock collecting is a great way to study rocks and geology. It can also make a great science fair project. This article provides tips on how to win a science fair project with an amazing rock set.

How to Use a Rotary Rock Tumbler Kit

By: Joe Kanooga | 09/12/2009
A rock tumbler is a tool commonly used by rock collectors and geologists to polish rocks. It is amazing to see a rough rock transformed into a beautiful gem, just be spending time in the tumbler. This article explains how to use a rock tumbler to make it perform its’ magic.

Estes Model Rockets Help Kids Learn Rocket AeroDynamics

By: Joe Kanooga | 09/12/2009
Model rockets go beyond being simple toys - they offer a fun way to learn about physics and aerodynamics. Few things are more satisfying than launching a rocket into the air, and many kids will happily spend hours doing this.

Secrets to Bigger Crystals with a Crystal Growing Kit

By: Joe Kanooga | 09/12/2009
If you’ve ever grown crystals, you have learned that bigger is always better. Everyone wants to make the biggest crystals. This article reveals the secrets to growing bigger crystals with or without the help of a crystal growing science kit.

How to Grow Crystals Bigger than Ever With a Science Kit

By: Joe Kanooga | 09/12/2009
Growing crystals is a fun, hands-on way to study chemistry and look at basic principles of geology and mineralogy. While some simple crystals can be made at home without special assistance, a science kit can provide a valuable starting point for getting larger and purer crystals.

Guide to Implementing a Laser Safety Procedure

By: Andrew Wood | 09/12/2009
The reason that laser procedures are gaining popularity so rapidly is their efficacy and safety in treating such a wide range of aesthetic skin conditions. However, that efficacy comes only with potent technology, that obviously has adjunct safety matters.

What is Ultraviolet Microscopy?

By: Fabio Pacheco | 08/12/2009
The so-called ultraviolet microscopy uses ultraviolet light instead of white, common, light, or visible light, as the light source. The ultraviolet light has a wavelength of 180 to 400 nm, much smaller than the visible light, whose wavelength is from 400 to 700 nm. And the advantage is?

Basics about the science of chemistry

By: Dave | 08/12/2009
Chemistry is one of the most important and fundamental natural sciences and everyone should know at least the definition of chemistry as a science, along with some of the most important and well known branches of this interesting science.

Overcome First Date Anxieties - Impress Your Date With Confidence

By: Robert Paterson | 06/11/2009 | Dating
A lot of folks find it nerve-racking to go on a first date. You sense yourself to be under pressure to impress, you feel that you are under inspection and your imperfections will be out in the open, you feel that some accidental remark you make could be sufficient to wreck the whole evening.

Dating Success - What Characteristics Turn A Woman On?

By: Robert Paterson | 02/11/2009 | Dating
What exactly is it that turns a woman on? It is useful to know this to keep away from doing what might cause the precise opposite to take place.

Dating - What Qualities Turn A Woman On?

By: Robert Paterson | 01/11/2009 | Dating
What is it that turns a woman on? You need to know this to keep away from doing things that might bring about the exact opposite to occur.

Dating Online - Some Tips To Help You Attain Your Desire

By: Robert Paterson | 30/10/2009 | Dating
With such a confusing range of online dating options to select from, how is it feasible for singles to make efficient use of these services?

Online Dating Becomes More Popular All The Time

By: Robert Paterson | 30/10/2009 | Dating
Just a small number of years ago it seems, dating online was more or less unknown. Nowadays practically everyone is trying it.

Online Dating Is Getting More Popular Each Day

By: Robert Paterson | 29/10/2009 | Dating
Not so long ago, dating online was virtually unknown. Nowadays nearly everyone does it. Perhaps you haven't tried it yet, and you're considering taking the plunge.

How You Can Get The Most From Online Dating Websites

By: Robert Paterson | 29/10/2009 | Dating
Lots of people are now trying out online dating as a method of meeting new people, be it for fun or friendship, or with a hope of beginning a fresh and enduring relationship.

How To Use 4 Alpha Male Techniques To Become Attractive To Women

By: Robert Paterson | 28/10/2009 | Dating
If you are looking to have dating success, it is a good idea to pay close attention to what your own body language is saying about you.

Submit Your Articles Free: Signup
Article Categories




Use of this web site constitutes acceptance of the Terms Of Use and Privacy Policy | User published content is licensed under a Creative Commons License.
Copyright © 2005-2008 Free Articles by ArticlesBase.com, All rights reserved. (0.07, 1, w1)