You have probably heard at some point in your life that we use a "base ten" notation system for our numbers, without necessarily understanding what this actually means.
The point of a notation system for numbers is to keep track of how many items have been counted (as in a census, inventory report, etc.). Therefore, the first question is how people count. The answer is that people generally count on their fingers (you may be thinking only of small children at this point, but try listing all seven dwarves from Snow White without using your fingers to keep track of how many you've gotten (and writing them down is cheating)). Counting on your fingers is a convenient way of keeping track of relatively small numbers, but what happens when they get bigger? This is when you need to get creative.
One solution would be to gather several of your friends together and have someone new take over counting each time the previous person runs out of fingers, but then you have to add them all up at the end (essentially counting again), and it would take five people just to count to forty-one, which is not an outlandishly big number. I'd like a better solution.
Suppose that instead of having a friend continue the count when I run out of fingers, I instead ask my friend to count how many times I run out of fingers. Then forty-one is simply four of my friend's fingers and one of mine. This essentially what we do in base ten notation.
There are ten symbols we use to write our numbers: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Each of those symbols alone represents a number, but it helps to think of numbers in terms of "how many." Here, the symbol "3" means "three fingers" (similarly for the other symbols). The pair of symbols "41" (in that order) means "four sets of fingers and one leftover finger" (also known as forty-one, since we have ten fingers). This shorthand notation is significantly easier than having to write down forty-one symbols to represent the forty-one items you counted.
If I have a second friend counting how many times my first friend runs out of fingers, we can make some even bigger numbers. The string of symbols "123" means "one set of ten sets of ten fingers (one hundred fingers) and two sets of ten fingers (twenty) and three more fingers," or one hundred and twenty-three fingers.
You may have noticed that in general we are using the symbol "10" to mean "one set of all my fingers, with no leftovers" and begun to wonder why we should always count with ten fingers. Suppose, for instance, that one hand is busy with something else and therefore can't help with our counting? This would result in a base five system (which did develop in some cultures).
In a base five notation system, you would only need five symbols: 0, 1, 2, 3, and 4. The symbol "10" would mean "one set of five fingers with no leftovers." If you wanted to write ten, it would look like "20" because you would need two sets of five with no leftovers. The number directly before this, nine, would look like "14." And forty-one would have to be written as "131" (one set of five fives (twenty-five) plus three sets of fives (fifteen) plus one). Your arithmetic would look a bit different, but it would work just as well (try a few calculations and see how it turns out).
For any whole number n bigger than or equal to two, you can create a base n notation system. Currently, most of the human race uses base ten, most likely simply because we have ten fingers. Most human cultures have used base five, ten, or twenty (I'm sure you can think of justifications for these). One notable exception is the ancient Babylonians, who used base sixty. As far as I know, no one is quite sure how they decided on this (though it has been pointed out that sixty is the smallest number divisible by 2, 3, 4, 5, and 6, which makes for fewer repeating decimals for fractions), but you can see its influence in how we measure time and angles.
Wednesday, August 3, 2011
Monday, August 1, 2011
Death by Proof By Contradiction
In my first post, I talked a bit about Pythagoras and his school. One important feature of Pythagoras's belief system was that he believed that the natural world was composed entirely of positive whole numbers and ratios of such numbers (called "rational numbers" because they can be expressed as ratios). This belief was as fundamental to the Pythagoreans as the notion of a benevolent creator is to modern Christianity.
Because of their belief that numbers defined the natural world, Pythagoras and his students put a lot of time and energy into studying the properties of numbers and operations on numbers. (They also attributed various properties, such as masculine and feminine, to different numbers, but that's not important to this story). Their work was based in part on real-world observations ("square" numbers derive their name from the Pythagorean observation that certain numbers of stones can be used to make perfect squares in the sand) and they wanted to use their work to understand the workings of the real world.
One day, a student by the name of Hippasus was attempting to discover the rational number that would measure the diagonal of a square whose sides were equal to 1 unit ("unit" can be any unit of measurement you like, the argument will still work the same). The Pythagoreans knew that a square's diagonal cut the square into two identical right triangles, with both legs equal to 1 in this case and the diagonal being the unknown.
Hippasus assumed, as any good student of Pythagoras would, that the measurement of the diagonal would be a rational number of units. We'll call it p/q units, where p and q are both positive real numbers that share no common factors with each other (this is allowed because if they shared common factors, we could cancel them and get a rational number u/v, which equals p/q but doesn't have common factors floating around to complicate things, and we would use that one).
By the Pythagorean Theorem, Hippasus was then able to say that 12+12=p2/q2.
This simplifies (through some basic arithmetic) to 1+1= p2/q2, or 2=p2/q2.
Multiplying both sides by q2 gives 2q2=p2.
Recall that p and q are both whole numbers. This means that p2 and q2 are also whole numbers, since any product of whole numbers is a whole number. Then 2q2 is an even whole number, since twice any whole number is even. That tells us that p2 is even.
A product of two odd numbers is odd, so p itself can't be odd. It must be even.
Since p is even, let's write it as 2k, where k is also a whole number.
Then p2=(2k)2 (by squaring both sides of the equation p=2k). Distributing the exponent on the right side tells us that p2=4k2.
But we said earlier that 2q2=p2, so we know have 2q2=4k2.
Divide both sides by two, and we get q2=2k2. Now by the same reasoning we used before to show that p was even, we can see that q is even. But we had said (without breaking any rules of math) that p and q have no common factors, and now we have shown that they are both divisible by two. The only assumption we made without justification was that our hypotenuse consisted of a rational number of units (or in modern parlance, that the square root of two is rational), and so this assumption must be wrong.
By essentially this same method (I updated notation and language to make it more accessible to modern readers) Hippasus had proven that one of the central tenets of Pythagoras's belief system was false by demonstrating that the diagonal of a square was incommensurable with its sides (sharing no common measure; this is how they would have phrased our statement that the diagonal is irrational), thus showing that there is some part of the natural world which cannot be described as a ratio of whole numbers under any measuring system.
Remember that this had not been Hippasus's intention. He was simply trying to find the correct ratio, and ended up proving that no such ratio exists (it is not uncommon in mathematics for investigations in one direction lead to astonishing unexpected discoveries). Unfortunately, that did not soften the response from the other Pythagoreans. Like many people throughout history, they did not take kindly to having their belief system uprooted with a few strokes of a pen. Accounts vary about how they treated him. The kindest claim that they kicked him out, erected a tombstone for him, and never spoke to him again, while other sources claim they took him out to sea and threw him overboard. In any case, he was punished for his discovery.
Because of their belief that numbers defined the natural world, Pythagoras and his students put a lot of time and energy into studying the properties of numbers and operations on numbers. (They also attributed various properties, such as masculine and feminine, to different numbers, but that's not important to this story). Their work was based in part on real-world observations ("square" numbers derive their name from the Pythagorean observation that certain numbers of stones can be used to make perfect squares in the sand) and they wanted to use their work to understand the workings of the real world.
One day, a student by the name of Hippasus was attempting to discover the rational number that would measure the diagonal of a square whose sides were equal to 1 unit ("unit" can be any unit of measurement you like, the argument will still work the same). The Pythagoreans knew that a square's diagonal cut the square into two identical right triangles, with both legs equal to 1 in this case and the diagonal being the unknown.
Hippasus assumed, as any good student of Pythagoras would, that the measurement of the diagonal would be a rational number of units. We'll call it p/q units, where p and q are both positive real numbers that share no common factors with each other (this is allowed because if they shared common factors, we could cancel them and get a rational number u/v, which equals p/q but doesn't have common factors floating around to complicate things, and we would use that one).
By the Pythagorean Theorem, Hippasus was then able to say that 12+12=p2/q2.
This simplifies (through some basic arithmetic) to 1+1= p2/q2, or 2=p2/q2.
Multiplying both sides by q2 gives 2q2=p2.
Recall that p and q are both whole numbers. This means that p2 and q2 are also whole numbers, since any product of whole numbers is a whole number. Then 2q2 is an even whole number, since twice any whole number is even. That tells us that p2 is even.
A product of two odd numbers is odd, so p itself can't be odd. It must be even.
Since p is even, let's write it as 2k, where k is also a whole number.
Then p2=(2k)2 (by squaring both sides of the equation p=2k). Distributing the exponent on the right side tells us that p2=4k2.
But we said earlier that 2q2=p2, so we know have 2q2=4k2.
Divide both sides by two, and we get q2=2k2. Now by the same reasoning we used before to show that p was even, we can see that q is even. But we had said (without breaking any rules of math) that p and q have no common factors, and now we have shown that they are both divisible by two. The only assumption we made without justification was that our hypotenuse consisted of a rational number of units (or in modern parlance, that the square root of two is rational), and so this assumption must be wrong.
By essentially this same method (I updated notation and language to make it more accessible to modern readers) Hippasus had proven that one of the central tenets of Pythagoras's belief system was false by demonstrating that the diagonal of a square was incommensurable with its sides (sharing no common measure; this is how they would have phrased our statement that the diagonal is irrational), thus showing that there is some part of the natural world which cannot be described as a ratio of whole numbers under any measuring system.
Remember that this had not been Hippasus's intention. He was simply trying to find the correct ratio, and ended up proving that no such ratio exists (it is not uncommon in mathematics for investigations in one direction lead to astonishing unexpected discoveries). Unfortunately, that did not soften the response from the other Pythagoreans. Like many people throughout history, they did not take kindly to having their belief system uprooted with a few strokes of a pen. Accounts vary about how they treated him. The kindest claim that they kicked him out, erected a tombstone for him, and never spoke to him again, while other sources claim they took him out to sea and threw him overboard. In any case, he was punished for his discovery.
Saturday, July 30, 2011
Proof by Contradiction
Tonight I am going to talk a bit about the method of proof by contradiction, but first some things have to be said about the idea of proof in general.
"Proof" in mathematics is stronger than simply "strong evidence" like you would find on a crime show. Once a statement in mathematics has been proven, that statement is definitely true, and will remain so forever. While scientific theories can be built up and torn down over a few years, mathematical theorems will never be disproven.
Of course, you can't make something from nothing. All branches of mathematics involve some underlying axioms, which are taken to be true and then used to prove other results, so the statement "This theorem has been proven true" really means "This statement has been proven true under a particular axiom system (usually implied by context)." A good axiom system should use very few axioms, and they should be things that are otherwise unprovable. For example, the axioms of number theory (which you use for basic arithmetic) essentially say that we have the number 1 and the power to add 1 to any number we have to get another number. From there, it is possible to prove all the rules of arithmetic.
But tonight we're talking specifically about proof by contradiction. To prove a statement by contradiction, you begin by assuming that what you want to prove is actually not true, and explore the consequences under your chosen axiom system until you reach a conclusion that contradicts some part of your axiom system or conclusions drawn from it.
This all sounds a bit technical, but you've probably used some form of this method in your daily life. For example:
Mom didn't have her coffee this morning.
How do you know?
If she had had her coffee this morning, she wouldn't be so irritable right now.
Clearly, this is not an airtight argument. Perhaps mom is irritable because she didn't sleep last night, or because she's nervous about a big meeting at work, or because the cat threw up in her shoes. But the idea behind the argument is simple enough, and mathematicians take this simple idea and make it rigorous.
Euclid's proof that there are infinitely many prime numbers (numbers which can only be divided by 1 and themselves (for example, the number 3)) provides a favorite example among mathematicians of proof by contradiction. This proof relies only on some basic arithmetic. Note that 1 is not considered a prime number.
We want to show that the number of prime numbers exceeds any finite quantity (Euclid would not have used the word "infinite"). Toward this end, let us assume that this is not the case. In other words, for some finite quantity n, there are exactly n prime numbers.
If this is the case, then we can make a finite list of all the prime numbers. Let's call them p1, p2, and so on up to pn.
Now let's make a new number, N, defined by N=p1 x p2 x ... x pn+ 1 (the product of all our primes, plus one), which we can do because the rules of arithmetic allow us to add and multiply numbers.
Since the product of two numbers is not less than either of the two numbers involved (we're working only with whole numbers in this proof, no fractions) and adding one makes it bigger still, N is larger than any number on our list of primes.
Therefore, N cannot be on our list of primes, and so (by our assumption that our list contained every possible prime), N is not prime. Any number that is not prime is composite (this is the definition of a composite number). Since N is composite, there is some prime that divides it evenly (another theorem, perhaps for another day). By our initial assumption, all possible primes are on our list, so N must be divisible by one of those.
We can assume that it is divisible by p1 (we can simply reorder our list so that the smallest prime dividing N is first).
Because p1 divides N, N/p1 is a whole number (this is what we mean when we say one number divides another).
What does N/p1 look like?
N/p1=p2 x p3 x ... x pn + 1/p1
Now we have a problem. p2 x p3 x ... x pnis a whole number, since a product of whole numbers is a whole number. But 1/p1 is a fraction, and the sum of a whole number and a fraction is not a whole number, as we had expected N/p1 should be. It's not that we used the wrong prime; we reordered the list so that the right prime would be p1. This tells us that there is no prime on our list that will divide N.
This leaves two possibilities. Either N itself is prime, or it is composite but divisible by some prime not on the list. In either case, our list was insufficient to cover all the primes. And since n was any arbitrary finite number, and no part of the proof depended on any other property of n, this tells us that any finite list of primes is insufficient. Thus there are infinitely many prime numbers.
The difference between this and the coffee example above is that every step of the argument after the faulty assumptions was mathematically correct (unlike the leap from coffee to lack of irritability). Thus, the only possible flaw in the argument was the initial assumption.
I have heard philosophers claim that a proof by contradiction is less informative than a direct proof because it provides no insight beyond the truth of the theorem. I tend to disagree with that assertion, and this proof supports my view: it provides a way of generating prime numbers (whether instantly or after a factorization).
Philosophers will also be quick to point out that this method of proof relies on an assumption that any statement is either true or false, but never both (if a statement could be neither true nor false, showing that its negation is not true is not sufficient to show that the statement is true; if a statement could be both true and false, it would be much more difficult (to sat the least) to reach a contradiction). Here they are correct, but let me reassure you; all of mathematics works under the assumption that no mathematical statement is both true and false (we say math is "consistent"--if this were not the case there would be nothing we couldn't prove), and while there are statements that are not decidable (can't be proven either way (a really interesting topic to be explored another day)) I know of no branch of mathematics that assumes that some statements are inherently neither true nor false.
I realize that today was somewhat technical, but I hope I was able to explain everything adequately and that you've learned something from it. Tune in tomorrow for a fun story!
"Proof" in mathematics is stronger than simply "strong evidence" like you would find on a crime show. Once a statement in mathematics has been proven, that statement is definitely true, and will remain so forever. While scientific theories can be built up and torn down over a few years, mathematical theorems will never be disproven.
Of course, you can't make something from nothing. All branches of mathematics involve some underlying axioms, which are taken to be true and then used to prove other results, so the statement "This theorem has been proven true" really means "This statement has been proven true under a particular axiom system (usually implied by context)." A good axiom system should use very few axioms, and they should be things that are otherwise unprovable. For example, the axioms of number theory (which you use for basic arithmetic) essentially say that we have the number 1 and the power to add 1 to any number we have to get another number. From there, it is possible to prove all the rules of arithmetic.
But tonight we're talking specifically about proof by contradiction. To prove a statement by contradiction, you begin by assuming that what you want to prove is actually not true, and explore the consequences under your chosen axiom system until you reach a conclusion that contradicts some part of your axiom system or conclusions drawn from it.
This all sounds a bit technical, but you've probably used some form of this method in your daily life. For example:
Mom didn't have her coffee this morning.
How do you know?
If she had had her coffee this morning, she wouldn't be so irritable right now.
Clearly, this is not an airtight argument. Perhaps mom is irritable because she didn't sleep last night, or because she's nervous about a big meeting at work, or because the cat threw up in her shoes. But the idea behind the argument is simple enough, and mathematicians take this simple idea and make it rigorous.
Euclid's proof that there are infinitely many prime numbers (numbers which can only be divided by 1 and themselves (for example, the number 3)) provides a favorite example among mathematicians of proof by contradiction. This proof relies only on some basic arithmetic. Note that 1 is not considered a prime number.
We want to show that the number of prime numbers exceeds any finite quantity (Euclid would not have used the word "infinite"). Toward this end, let us assume that this is not the case. In other words, for some finite quantity n, there are exactly n prime numbers.
If this is the case, then we can make a finite list of all the prime numbers. Let's call them p1, p2, and so on up to pn.
Now let's make a new number, N, defined by N=p1 x p2 x ... x pn+ 1 (the product of all our primes, plus one), which we can do because the rules of arithmetic allow us to add and multiply numbers.
Since the product of two numbers is not less than either of the two numbers involved (we're working only with whole numbers in this proof, no fractions) and adding one makes it bigger still, N is larger than any number on our list of primes.
Therefore, N cannot be on our list of primes, and so (by our assumption that our list contained every possible prime), N is not prime. Any number that is not prime is composite (this is the definition of a composite number). Since N is composite, there is some prime that divides it evenly (another theorem, perhaps for another day). By our initial assumption, all possible primes are on our list, so N must be divisible by one of those.
We can assume that it is divisible by p1 (we can simply reorder our list so that the smallest prime dividing N is first).
Because p1 divides N, N/p1 is a whole number (this is what we mean when we say one number divides another).
What does N/p1 look like?
N/p1=p2 x p3 x ... x pn + 1/p1
Now we have a problem. p2 x p3 x ... x pnis a whole number, since a product of whole numbers is a whole number. But 1/p1 is a fraction, and the sum of a whole number and a fraction is not a whole number, as we had expected N/p1 should be. It's not that we used the wrong prime; we reordered the list so that the right prime would be p1. This tells us that there is no prime on our list that will divide N.
This leaves two possibilities. Either N itself is prime, or it is composite but divisible by some prime not on the list. In either case, our list was insufficient to cover all the primes. And since n was any arbitrary finite number, and no part of the proof depended on any other property of n, this tells us that any finite list of primes is insufficient. Thus there are infinitely many prime numbers.
The difference between this and the coffee example above is that every step of the argument after the faulty assumptions was mathematically correct (unlike the leap from coffee to lack of irritability). Thus, the only possible flaw in the argument was the initial assumption.
I have heard philosophers claim that a proof by contradiction is less informative than a direct proof because it provides no insight beyond the truth of the theorem. I tend to disagree with that assertion, and this proof supports my view: it provides a way of generating prime numbers (whether instantly or after a factorization).
Philosophers will also be quick to point out that this method of proof relies on an assumption that any statement is either true or false, but never both (if a statement could be neither true nor false, showing that its negation is not true is not sufficient to show that the statement is true; if a statement could be both true and false, it would be much more difficult (to sat the least) to reach a contradiction). Here they are correct, but let me reassure you; all of mathematics works under the assumption that no mathematical statement is both true and false (we say math is "consistent"--if this were not the case there would be nothing we couldn't prove), and while there are statements that are not decidable (can't be proven either way (a really interesting topic to be explored another day)) I know of no branch of mathematics that assumes that some statements are inherently neither true nor false.
I realize that today was somewhat technical, but I hope I was able to explain everything adequately and that you've learned something from it. Tune in tomorrow for a fun story!
Friday, July 29, 2011
About my blog
Hey there!
I decided to start this blog because I love math. I love doing math, learning about math, and especially telling other people interesting things about math. I will try to do approximately daily posts, but I am not going to promise anything better than once a week.
Overall, this is going to consist of a combination of (what I consider) cool math facts, lessons in topics that people are either unlikely to have learned or likely to struggle with (but ought to be able to understand if I explain well), and stories from the history of math. If there is something specific you would like to hear about, let me know.
And if you're curious about the title: Pythagoras (best known for the Pythogorean Theorem, which deals with the relationship between the sides of a right triangle (a2 + b2 = c2)) was more than just some old Greek guy. He was a really eccentric man, who founded a school/cult where he taught mathematics. His students/followers had strict dietary rules (vegetarian, with more rules on top of that (they couldn't eat beans because Pythagoras believed that a bit of your soul escapes when you fart)), could not share what they learned at school with outsiders, and spent their time attempting to understand the world around them through numbers (a concept that is still with us today). Before Pythagoras, no one really studied math for its own sake, and they certainly didn't feel the need to prove that their methods worked. Pythagoras was one of the first to recognize the importance of proving your assertions, which is why the aforementioned theorem takes his name; even though it was commonly known and widely used well before his time, he is considered the first to actually prove it. Between his eccentricity and his importance to mathematical history, he is one of my favorite mathematicians. Add to that a rumor (probably started by him) that a river was cried out "Hail Pythagoras!" as he passed, and it seemed too good a name to pass up.
I decided to start this blog because I love math. I love doing math, learning about math, and especially telling other people interesting things about math. I will try to do approximately daily posts, but I am not going to promise anything better than once a week.
Overall, this is going to consist of a combination of (what I consider) cool math facts, lessons in topics that people are either unlikely to have learned or likely to struggle with (but ought to be able to understand if I explain well), and stories from the history of math. If there is something specific you would like to hear about, let me know.
And if you're curious about the title: Pythagoras (best known for the Pythogorean Theorem, which deals with the relationship between the sides of a right triangle (a2 + b2 = c2)) was more than just some old Greek guy. He was a really eccentric man, who founded a school/cult where he taught mathematics. His students/followers had strict dietary rules (vegetarian, with more rules on top of that (they couldn't eat beans because Pythagoras believed that a bit of your soul escapes when you fart)), could not share what they learned at school with outsiders, and spent their time attempting to understand the world around them through numbers (a concept that is still with us today). Before Pythagoras, no one really studied math for its own sake, and they certainly didn't feel the need to prove that their methods worked. Pythagoras was one of the first to recognize the importance of proving your assertions, which is why the aforementioned theorem takes his name; even though it was commonly known and widely used well before his time, he is considered the first to actually prove it. Between his eccentricity and his importance to mathematical history, he is one of my favorite mathematicians. Add to that a rumor (probably started by him) that a river was cried out "Hail Pythagoras!" as he passed, and it seemed too good a name to pass up.
Subscribe to:
Posts (Atom)