|
|
|
A Most Merry and Illustrated Proof of Cantor's Theorem on the Countability of Integers
With a Most Merry and Illustrated Explanation of Proof by Induction Thrown In (and a Little Bit about Transfinite Numbers as well).
George said they both weighed the same.
Did CooperToons hear a most massive yawn when the title of this essay was posted? Well, we suppose it is kind of hard to come up with an eye-catching title when you're going to prove that the number of counting numbers (1, 2, 3, 4, ... ) is the same as the number of integers ( ..., -3, -2, -1, 0, 1, 2, 3, ... ). Lack of a snappy title is not, though, is a lack of merit.
Far from it. In fact, if you stick through to the end, you'll get a bonus - two bonuses, in fact. In addition to our proof about integers, we will also prove that there are just as many even numbers (2, 4, 6, ...) as there are number of counting numbers. And - please try to contain your excitement - we will also give a quick course in one of the most fundamental methods of mathematical proof: proof by induction. So before you click over to a website on - well, on less savory topics, remember when we are finished reading, we will have covered some of the most important topics in the history of philosophy.
Yes, that's philosophy. After all, mathematics is a sub-branch of the larger field, and in fact some universities combine assorted departments of computers, mathematics, psychology, and, yes, philosophy together. But specifically here we will be discussing the nature of the infinite. Infinity, as you know, is a topic that philosophers have struggled with for millennium, and therefore it is a topic that fully merits inclusion on a website modestly dedicated to total eradication of ignorance and superstition.
Infinity is a difficult topic. It wasn't until the 1900's, that the German mathematician, Georg Cantor, brought real meaning to the word (Georg, by the way, is pronounced "GAY-org" but we'll call him George). So we can't blame less educated dilettantes like Plato and Aristotle if they had trouble. And we sure can't blame middle school kids because they struggle with a subject that has taxed the greatest minds of history.
But - and it's a big but - CooperToons must give a disclaimer. All though he thinks the proofs given below are complete and correct, he has to disavow any responsibility to anyone who has been frantically surfing the Fount of All Knowledge (i. e., the Internet) trying to find a solution for a homework problem the night before it's due. Remember, if you find anything on the Fount, make sure you get a second opinion. Better yet, start your homework on time.
(For those who want to skip detailed explanations and examples of induction, you can view a more concise version of this essay if you click here. A pdf version - more suitable for printing - is available by clicking here
The Problem
First we'll begin by stating exactly what we need to prove and how we're going to prove it.
As we said, we are going to prove that the number of counting numbers
is the same as the number of integers:
Now some readers may immediately see a couple of glitches. First, how can the two sets be same size? You have two integers for every counting number - and that's not even counting the zero. Can twice something be that something?
Next, although the set of counting numbers has a lower limit - the number 1 - it never runs out of numbers. The integers never run out of numbers either, but for them there are no bounds in either direction. How can you count such sets, much less compare their size?
It was George who came up with the answers. Once he began looking into set theory (he invented the field, in fact), he had to develop an exact definition of counting and what we mean when we say two sets are the same size. And during his studies, he found out you could count at least some infinite sets, and you could tell if some infinite sets were the same size. But you couldn't count like ordinary people.
Count Like a Mathematician
In normal English, when you say you count something, you mean that you start numbering the objects until you run out of things to count. The highest number you reach is the number of objects you have.
Or put in a bit more mathematical terms, when you count a set of objects, you make a one-to-one correspondence between the set of counting numbers (in increasing order, of course) and the objects of that set. You stop making the correspondence when you run out of objects. Once more, the highest counting number you reach is the size of the set.
For instance, to count the objects in Set A,
You just start matching them with counting numbers until you have nothing left.
3
2 6
3 11
4 20
Now a more rigorous representation of counting is to show that you can create a new set, P, where each element is an ordered pair. The first elements of the pairs are selected from the lowest possible counting numbers without repetition. You pick the second element from the other set. The highest value of the first elements is the size of the set.
Now George also realized that it is possible to tell if two sets are the same size without actually counting the objects. All you need to do is pair the objects of the two sets. If nothing is left over, then the sets are the same size.
For instance, if we want to see if set B below
is the same size as Set A from above, we just match them up.
Simple enough. But now George went further and made a discovery that made his reputation. And members of the Georg Cantor Fan Club say this discovery made him the greatest mathematician of all time.
Counting the Uncountable?
There are some sets, George said, that even though infinite, you can nevertheless pair off with each other. And you don't even need to go beyond simple algebra.
The simplest way to pair off two infinite sets is just to multiply the counting numbers by two.
2
2 4
3 6
4 8
.
.
.
So what we have done is to make explicit the one-to-one correspondence of the counting numbers and the even numbers. Using the "rigorous" notation the pairing is even clearer.
And an even simpler way to show the pairing is using a function like we've seen in our math classes:
f(n) = 2n
where n = 1, 2, 3, ...
So you see it is possible - and easy - to make a one-to-one correspondence between two infinite sets. This was clearly nothing new.
But George pointed out if we make a one-to-one correspondence between the two sets, they must be the same size. More than that, by pairing the even numbers with counting numbers we are actually counting the even numbers. It doesn't matter if the set is infinite.
George said that a set that can be put on one-to-one correspondence with counting numbers is countably infinite or denumerable. So George not only now had a topic for scholarly papers (he was a professor by the way), but he had come up with the first unambiguous definition of infinity.
On the other hand, George did realize the notion of size isn't the same for finite and infinite sets. Infinity is a concept, not a number, and you can't characterize the size of an infinite set with a specific number.
Instead, when talking about the size of sets, George said we should first talk about their cardinality. Any sets that can be put into a one-to-one correspondence have the same cardinality. For finite sets, the cardinality is simply the size. So Sets A and B above both have four elements, and so have a cardinality of four. But how do you express the size - that is, the cardinality - of an infinite set? Well, since George couldn't use counting numbers, he recognized he had discovered a new type of number, the transfinite numbers.
The size of a countable infinity, George said, could not be a counting number. After all, no matter what counting number you pick, there is always a higher number. And just saying the size is "infinite" wasn't quite correct either.
Instead George said the size - or rather cardinality - of infinite sets requires a new type of number called transfinite numbers. The size of the counting numbers was indeed the smallest transfinite number, a number George designated as aleph-null, or 
. is still an infinity, but only one of many infinities and it was smallest infinity possible (hence, the "null" part). You can learn more about how George discovered a larger infinity if you click here. But that's not necessary for what we want to do here.
There's one more thing to realize about what George proved. We all know that the even numbers are a proper subset of the counting numbers. Therefore certain subsets of an infinite set can themselves be infinite. After all, there really are half as many even numbers as the counting numbers. In other words, George proved half of a countable infinity is still a countable infinity. Furthermore, because you can write the function, f(n) = kn, where k is any positive integer, you can take arbitrarily small chunks of countably infinite sets and still have a countably infinite set.
George's conclusions upset some mathematicians in his own time, and even today some people still have trouble accepting what he said (just as some Ph. D.'s from major universities will go into spittle flinging diatribes when you explain the Monty Hall Problem). But in the realm of infinity, a strange answer is not necessarily an incorrect answer and when George talked about infinity, we know he got it right.
Admittedly we haven't yet shown that the number of integers is the same as the number of counting numbers. But at least we have rigorously proven that there are as many even numbers as counting numbers.
Or have we?
Proof by Induction
Honesty compels us to point out that strictly speaking we have not proven anything. We have not proven a one-to-one correspondence exits between counting numbers and even numbers.
What we have proven - in our pairing diagram - is the counting numbers up to 4 pair off with the even numbers up to eight. We also have a formula, f(n) = 2n, that we claim establishes the correspondence for all n. But we have not proven the formula always works. For that we need to prove it as a theorem.
Proving theorems is one of the greatest terrors for mathematics students. Now the reason it seems tough to prove theorems is because, dammit, it is tough, and a major stumbling block for learning to prove theorems (in a humble CooperToons opinion) is that although students are told to prove theorems, they rarely, if ever, are they actually told how to do it. Instead they do their best to imitate the conversational style intermixed with equations that they find in their textbooks - and which they can never seem to get to their teacher's satisfaction.
The difficulty is compounded because to understand the conventions used for creating an acceptable proof, students need to grasp the fundamentals of logic and the derivation of the foundations of mathematics. These are topics - we must point out - that are usually reserved for the last and most difficult course taught to mathematics majors in college.
But lest CooperToons call down the wrath of math teachers everywhere, let him say he - as one who continues a decades long association with a math teacher (wink, wink) - understands it isn't practical to teach a whole course in proof theory at the middle or high school level. So here he will try to relieve part of the students' (and teachers') burden by explaining one the most elementary - but not necessarily easy - methods of proof. That is proof by induction.
To prove something by induction, there are two steps.
First you simply show that your proposed theorem - that is the equation you think works - is true for a specific number. This step is generally easy and is nothing more than a plugging an actual number in the formula and showing you get what you want.
The next step - and this is where it can get a bit tricky - is to prove if your proposed theorem is true of some unspecified value of n, it is also true for the value n + 1. If you can demonstrate both steps, then you have a proof by induction.
Mathematical induction is often introduced - not always successfully - at the secondary school level. But even when the method is explained, the students tend to doubt it really proves anything.
The teachers, though, do their best to explain induction is like falling dominoes. If something is true for n and also true for n + 1, well, then it's true for the number n + 2. And n + 3. And the next number. And the next. And it never stops being true.
The answer, though, rarely satisfies the students, and the teacher has to return to the topic again and again. But trying to explain why induction is a proper proof is rarely worth the effort because the real reason is so simple it won't satisfy the students either.
We know induction is a proper proof because it is simply a fundamental postulate of number theory. In other words, in the nineteenth and early twentieth century the most famous mathematicians and logicians like Gottlob Frege, Giuseppe Peano, and Bertrand Russell (not to mention George), decided that induction was good enough for them. And if something is good enough for George, Gottlob, Giuseppe, and Bertie, it's good enough for us.
(But don't try telling your teacher, "Well, I've decided that my homework assignments are all fundamental postulates of mathematics. So I don't need to prove them." That won't work.)
A Nice, Simple Example
As an introduction to induction (sounds like the lyrics to a Paul Simon song, doesn't it?) we will start with probably the easiest example. We will prove our claim there are the same number of even numbers as counting numbers.
We've already taken care of the first step in induction since we've shown there were some specific numbers where successive counting numbers generated successive even numbers. After all, the equation worked fine for numbers n = 1 to n = 4. So we don't have to repeat that part.
But the induction part remains and that itself has two parts. First, we show the formula produces an even number for n + 1. That part is essentially self-proving by definition. Any number times two is even.
f(n + 1) = 2(n + 1).
Now we have to show that the value of f(n + 1) is not only an even number, but the next even number after f(n). That's not too hard either since we know that the difference between an even number and the next lower one is 2. In other words we must prove that
f(n + 1) - f(n) = 2.
which is also easy:
|
f(n + 1) - f(n) |
= |
2(n + 1) - 2n |
|
|
= |
2n + 2 - 2n |
|
|
= |
2 |
Hey, presto! Proof by induction.
This example also illustrates a point that is not often stressed when trying to teach kids how to prove theorems. In proving a theorem you have to take concepts of ordinary English and put them into mathematical equations. So to prove "f(n + 1) is the next even number after f(n)" we had to devise and prove the mathematically equivalent statement that f(n + 1) - f(n) = 2. Admittedly this was a quick, simple example, but often translating English into Mathematish is not so easy.
Prelude to the PROOF
Now, as the psychiatrist in Portnoy's Complaint said, "Now we can begin. Yes?"
We are at the point where we want to prove what we came to prove, that the numbers of counting numbers is the same as the number of integers. Now on the Fount of All Knowledge, you can find various - quote - "proofs" - unquote - for this theorem. Some are only one or two sentences long and make allusions to sets, mapping, bijections and such stuff. But such a proof, as correct as it may be, is the type that enlightens only those who don't don't need enlightenement
.More often, though, you will see a diagram like:
0
2 -1
3 1
4 -2
5 2
6 -3
7 3
.
.
.
So what you see is that after pairing 1 with zero, you then alternate with positive and negative integers. So it certainly looks like you can set up a one-to-one correspondence with counting numbers and integers.
We must emphasize: Although some websites on the Fount and even some books (those non-electronic device with white flappy things in the middle) may say this is a proof, it is not. True, it is helpful in setting up the proof, but it is nothing more than that.
So what we have to do for the integers is what we did for even numbers. First, we propose a formula that relates the counting numbers to each integer and then show it works for 1 (the lowest counting number). Then we prove that if it works for any counting number, n, it works for n + 1.
Next we need to be a bit more specific than saying we need to produce alternative positive and negative integers. Instead we need to come up with specific mathematical relationships which unambiguously show we have such a pattern, but avoid relying on tables or diagrams with trailing dots.
Specifically, then, we need a function, f(n) where n is a counting number and
1. If n is 1, the f(n) = 0
2. If n = 2, then f(2) = -1. Then as we move to the next even counting number the value of the function decreases by one. In other words, for any even number, n, then
f(n+2) = f(n) - 1
or equivalently
f(n+2) - f(n) = -1
So if you plug in any even number into the function, we will generate all the negative integers.
3. If n = 3, the f(3) = 1. Then for every odd counting number greater than 3,
f(n+2) = f(n) + 1
which is the same as
f(n+2) - f(n) = 1
So each odd counting number increases the function by one. The odd numbers produce zero and afterwards all the positive integers.
These conditions will meet the criteria that we will match every counting number uniquely with with all integers - which is what we want to prove.
At this point you see that we have made a apparent modification in the induction method. Instead of working with the f(n + 1) function we are working with f(n + 2). But since we are dividing the function by whether it accepts odd and even numbers, using n + 2 is correct. In general, then when you use induction, you prove that if a function works for a particular argument, it works for the next argument in the sequence. This allows you to use induction for functions that don't even use numbers.
But now we need to quit futzing around and make a formula which works.
THE Function?
The discerning reader can now see that by dividing the function into whether it uses odd or even numbers, the required equations are pretty simple.
For the odd counting numbers:
f(n) = (n - 1)/2
that is, where n = 1, 3, 5, 7, ...
For even numbers:
f(n) = -n/2
where n = 2, 4, 6, ...
And the two formulas, when intermixed in increasing order of n, produce exactly what we want (the actual number crunching will be left to the reader):
|
f(1) |
= |
0 |
|
f(2) |
= |
-1 |
|
f(3) |
= |
1 |
|
f(4) |
= |
-2 |
|
f(5) |
= |
2 |
|
f(6) |
= |
-3 |
|
f(7) |
= |
3 |
So at this point we have shown the formula(s) work for the counting numbers up to n = 7. So at least we've finished with the first step in the proof by induction.
The Final Function
There's nothing wrong with defining a function in multiple parts and working with odd and even numbers separately. But the curious reader may want to know whether we can come up with one single formula that will do the job. Of course, the answer is yes, but first a word about where equations in general come from.
There is no real hard and fast rule for finding equations. Yes, some equations are derived by logical steps from accepted postulates and theorems. Such a derivation is nice because it will also be a proof, and the equation is true. But that is not, by any means, the way it's always done.
Instead, you can, if you wish, just pull the equations out of your ..., well, out of your hat. If you can just guess what equation you need - which is sometimes what it seems like the great Indian mathematician, Srinivasan Ramanujan did - that's all well and good. Of course, if you make a guess, you still have to prove the equation is true. But the ability to zoom in intuitively on the right formula is certainly an ability all mathematicians would love to have.
More often, though, mathematicians get equations from a combination of derivations from other equations, educated guesswork, experience, and empiricism. That's what we will do here.
To combine the two equations, we take advantage of the properties of another function, f(n) = (-1)n. From the laws of exponents you will remember that if n is even then
(-1)n= 1
If n is odd, then
(-1)n=-1
So after a bit of trial and error, we come up with:
![f(n) = n(-1)^(n-1)/2-(1-[-1]^n/4](function1_72dpi.jpg)
This formula certainly seems to work. For instance, if n = 1, then
![f(n) = n(-1)^(n-1)/2+(1-[-1]^n/4](function2_72dpi.jpg)
And if n = 2,
![f(n) = n(-1)^(n-1)/2+(1-[-1]^n/4](function3_72dpi.jpg)
And if n = 3?
![f(n) = n(-1)^(n-1)/2+(1-[-1]^n/4](function4_72dpi.jpg)
If you keep this up for a few more numbers, you find out that we get the same pairing as before.
|
f(1) |
= |
0 |
|
f(2) |
= |
-1 |
|
f(3) |
= |
1 |
|
f(4) |
= |
-2 |
|
f(5) |
= |
2 |
|
f(6) |
= |
-3 |
|
f(7) |
= |
3 |
So it seems we have found a formula that produces a 1:1 correspondence of the counting numbers with the integers. The formula certainly works for some counting numbers.
Alas, we have not yet proven the formula works for all counting numbers.
Two Steps Forward and One Back
Now it is possible to deduce a relationship between f(n) and f(n + 1) using the full equation and go on with the proof by induction. However, although straightforward, it's easy to make mistakes. And also sorting out the relationship of f(n + 1) and f(n) between successive odd and even integers is more trouble than it's worth.
So instead we're going to take a step backwards and work with the odd and even numbers separately. So first we will prove our single formula reduces to the two separate formulas we showed earlier.
So we start off with
If n is odd, then, the first exponent, n - 1, is always even and the second exponent is always odd. So the equation immediately becomes:
![f(n) = n(-1)^(n-1)/2-(1-[-1]^n/4](function5_72dpi.jpg)
Which was the earlier function for the odd numbers.
But if n is even, the first exponent, n - 1, is always odd and the second exponent is always even. So the equation becomes
![f(n) = n(-1)^(n-1)/2-(1-[-1]^n/4](function6_72dpi.jpg)
which was the earlier equation for the even numbers.
The Final PROOF (Finally)
Now we are ready for the actual proof by induction. But since we've already shown the equations work for some values of even and odd counting numbers, we only need to show the equations work with f(n + 2) if it works for n (again remember the n + 2 means we are working with even and odd number separately).
For odd numbers we need to show
f(n + 2) - f(n) = 1
And sure enough:
![f(n) = n(-1)^(n-1)/2-(1-[-1]^n/4](function7_72dpi.jpg)
For even numbers we have to prove.
f(n + 2) - f(n) = -1
and indeed:
![f(n) = n(-1)^(n-1)/2-(1-[-1]^n/4](function8_72dpi.jpg)
So what have we shown? Well, exactly what we said we would
The function
1. Has a value 0 if n = 1 and increases sequentially by 1 for all odd numbers.
2. Has a value of -1 if n = 2. It decreases sequentially by 1 for each even number.
Therefore f(n) will generate all integers if n is restricted to the counting nummbers. This proves there is a 1:1 correspondence between the integers and counting numbers. The two sets are of the same cardinality and hence size. There really are as many integers as counting numbers.
So George was right after all.
How about that?
Addendum
Of course, George didn't stop here. He not only used his famous diagonal argument to prove that the number of real numbers was greater than the counting numbers, but he also - and in someways this was even more amazing - showed that the number of rational numbers - that is, the fractions - were the same as the number of counting numbers. This latter conclusion is by no means intuitive since you can pick two rationals and squeeze any number of other rationals between them (something you cannot do for counting numbers or integers). The proof, though, is more involved than the proofs we've shown here, but is pretty slick and still follows from the rules of induction and simple algebra.
But that, perhaps, will be another story.
