Real Mathematics = Proof
I remember a day in high school when our algebra teacher assigned a simple proof as a homework problem. Another of the students asked plaintively "What does he want?" Proof can be a tough concept to grasp, so I want to illustrate it here. I'll take a landmark in the history of mathematics: The discovery by the Pythagoreans that the square root of 2 is not rational, that is, √(2) is not the quotient of two natural numbers. (The "natural numbers" are just the counting numbers, 1, 2, 3, etc.)
This has an interesting story associated with it. The Pythagoreans' world-view centered around the natural numbers; for instance, they discovered that pleasing harmonies result when the lengths of two plucked strings are a simple ratio, like 1:2 or 2:3. Anyway, whatever their justification for the importance of natural numbers, they thought that any fraction was the ratio of two natural numbers. One of their order, Hippasus, discovered the theorem and proof which we will explore shortly, which says that the square root of 2 is not the ratio of any natural numbers. For this heresy, it is said that others of the Pythagorean order threw Hippasus overboard at sea, drowning him.
This proof, which is ancient, uses what is called the indirect method. This means that we assume the opposite of what we're trying to prove, and then try to derive a contradiction. This is not as mysterious as it appears to some at first glance. We use a similar idea all the time in our daily lives. For instance, suppose I suspect that my young neighbor Hannah killed President Kennedy. If she did, then she would have had to be in Dallas on that day, so I might try to establish her whereabouts when it happened. And now my theory has a problem: She couldn't have been in Dallas because she was born in 1990, more than two decades after Kennedy was murdered. This contradiction with a known fact establishes that my starting point was incorrect; so Hannah is cleared.
Ok, so that was a pretty trivial example. How about something real? Let's assume that √(2) = a/b, where a and b are whole numbers, and investigate what properties a and b must have. If we find that they must have properties that they can't have, then we know that our assumption was false, namely that √(2) cannot equal a/b for any whole numbers a and b.
Starting with
√(2) = a / b
let's square both sides. We get
2 = a2 / b2
and now let's multiply both sides by b2 to get
2b2 = a2.
Now that's interesting. It says that a2 is even, because it's equal to 2 times another number. What does that say about a itself? Can a be odd? No, it can't, because the product of two odd numbers is always odd.
(Why is the product of two odd numbers always odd, you ask? Every odd number
is of the form 2n+1, that is, an even number — 2n —
plus 1. So let's see what happens when we multiply an odd number by itself:
(2n+1)(2n+1) = 4n2 + 4n + 1
= 2(2n2 + 2n) + 1
which is 2 times a number, plus 1, which is an odd number.)
So the fact that a2 is even tells us that a itself is even, that is,
that a = 2a1 for some number a1. I'll just make that
substitution in the equation to get:
2b2 = (2a1)2
= 4a12
And now I'll divide both sides by 2 to get, finally,
b2 = 2a12
Now that's interesting too. It says that b2 is even, and so we know
that b must be even, by the same logic that we went through for a. In the same
way then we have b = 2b1 for some number b1. We'll just
substitute that into the earlier equation to get:
(2b1)2 = 2a12
4b12= 2a12
and I'll divide through by 2 to get:
2b12= a12
Now that's interesting. It means that a12 is even, and
so a1 also has to be even. So a1 has to be equal to
2a2 for some number a2. We substitute that back into
the previous equation and simplify it, thus:
2b12= (2a2)2 =
4a22, so
b12 = 2a22
Now that's interesting. It means that b12 is even, and so b1 must be even. But by this time, this is getting repetitive. It's clear that we can go on like this forever, taking a factor of two out of one side or the other each time. So here's the situation: We assumed that √(2) = a / b, where a and b are whole numbers, and we discovered that we can take a factor of 2 out of both a and b, forever. Now how many numbers can you think of which have an infinite number of factors of 2?
Right; there aren't any. All ordinary whole numbers are finite. They can't have an infinite number of factors. We've proved that our assumption that √(2) = a / b must be false.
More Power!
Just as there are many routes from one place to another, there are many ways to prove mathematical theorems. Let's see a very short proof that √(2) is irrational, based on factoring numbers.You've probably reduced numbers to their prime factors. Start with any whole number, say 1092, and start looking for smaller numbers that divide it with no remainder. 1092 is even, so we divide by 2 to get 546. That's still even, so we find 1092 = 2*2*273. 273 isn't even so we can stop trying any even divisor. 3 divides 273, so 1092 = 2*2*3*91. Via trial and error, or various clever tricks, we find that 7 divides 91, so 1092 = 2*2*3*7*13. All the divisors are prime, so there the process stops.
You can try different divisors, for instance 182. 1092 = 182*6, and we can push that further since we can see the factors of 6: 1092 = 182*2*3. And 182 is even, so 1092 = 91*2*2*3. Again we have 91 as a factor, and we already know that 91 = 7*13, so 1092 = 2*2*3*7*13. Those are the same factors that we found the first time. Could that be coincidental?
Could be, but it isn't. One of the first big theorems you'll encounter and prove if you study number theory is the fundamental theorem of arithmetic. This says that the list of factors of any whole number is unique. I'll use that fundamental property of whole numbers to give a short proof that √(2) is irrational.
Once again, suppose it isn't. That is, suppose there exist whole numbers m
and n such that
√(2) = m/n.
Again we square both sides to get
2 = m2/n2.
And again multiply by n2 to get
2n2 = m2
Now let's use the fundamental theorem of arithmetic on m and n. That says that
m and n have a unique list of prime factors. Say m = a*b*c*d*... and n =
z*y*w*v*.... I don't know how many factors each has; if one of them is prime
then it'd be only one factor, namely itself. But that won't matter. We
substitute the prime factorization of m and n in our last equation and get
2*z*z*y*y*w*w*v*v*... = a*a*b*b*c*c*d*d*...
Now we're almost done. We have a single number written as two lists of prime factors. The fundamental theorem of arithmetic says that the list of prime factors is unique. So those two lists have to be the same. But the one on the left has an odd number of factors (2 and the list of factors from n, each of which appears twice because n is squared), and the list on the right has an even number (the factors of m, each of which appears twice). So they can't be the same. We have our contradiction. √(2) is irrational.