Proof by Contradiction

A very useful question to ask yourself when you are trying to figure out if something is true or not is, "What if this wasn't true? This kind of thinking is at the heart of a proof by contradiction.

These are the steps in a proof by contradiction:

· State the opposite of what you are trying to prove.

· For the sake of argument, assume that this (the opposite) is true.

· Beginning with that assumption, see what conclusions you can draw. These conclusions will be based only on the assumption you made, and things that are true

· Try to draw a conclusion that you know is false or that contradictssomething that is true.

· If you can draw a false conclusion from the assumption and other true statements, you know that the assumption must be false.

· But the assumption is the oppositeof what you are trying to prove. If that is false, what you are trying to prove must be true. And so you have proved it.

An Example of Proof by Contradition

You can use a proof by contradiction to show that a solution to the Three for the Money problem, it will be a graph that has an even number of vertices.

Statement:If a graph exists that is 3-regular with diameter less than 3, its size will be even. Proof:Assume that a graph exists that is 3-regular with diameter less than 3 and that its size is odd.

· It doesn't matter how many vertices there actually are, only that the number is odd. Let p stand for the size of the graph.

· Since the graph is 3-regular, the degree of every vertex is 3. Therefore, the sum of the degrees of all the vertices is 3 times p, or 3p.

· Because p is an odd number, 3p will always be odd.

· We know from the First Theorem of Graph Theory that the sum of all the degrees of all the vertices is twice the number of edges. No matter how many edges there are, that number will always be even.

· We have just concluded that if a 3-regular, planar graph of diameter 3 and an odd number of vertices exists, the sum of the degrees of all the vertices will be a number that is both odd and even!

· Therefore, such a graph cannot exist.

· We do not arrive at the same contradiction if the graph has an even number of vertices. Therefore, if a graph exists which meets the conditions of the Three for the Money problem it will have an even number of vertices.

Infinity

Infinityis not a number or a thing, but the idea behind many notions:

• no matter how high you count, you can always count higher
• no matter how long you draw a pair of parallel lines, they never meet
• if you start with a line of any length, you can divide it in half, then divide one of the pieces in half, and no matter how many times you repeat the process, you will always have another piece that you can divide in half again.

Our intuition tells us that these infinite things are theoretically possible, even though our experience, which is finite, tells us that it is impossible to demonstrate them in the physical world. Still, it is easier to imagine them being true than it is to imagine them not to be true. How could there be a "last number" when practically everyone knows how to add 1 to it?

Where does this leave us, though, when we accept these truths that involve infinity? Does it makes sense to have a number that is greater than the estimated number of particles in the universe, or to begin dividing a line into lengths shorter than the diameter of any particle known to atomic physicists? What if, in the vast unreachable universe that is larger than our senses can comprehend, parallel lines do eventually meet?

We might want to ask, then if it is ``legal'', for mathematicians, whose field of study is founded on logic and proof to say, in effect, ``Well, imagine that this line or this process does go on forever, and then at the end, the result would be...'' Isn't everything in mathematics supposed to be rigorous and concrete?

In attempting to grapple mathematically with these ideas, Georg Cantor surprised and puzzled himself by demonstrating, not only that infinities come in different sizes, but also that there are infinitely many of them!

The idea of infinity is a deep and confounding one, and it does not seem that mathematics will ever nail it down.

Date: 2015-12-17; view: 995