|
|
|
Caricature and Biography Links |
Cantor's Diagonal Argument
A Most Merry and Illustrated Explanation
(With a Merry Theorem of Proof Theory Thrown In)
If you flick on the tube today, in addition to the ubiquitous but misnamed reality show, 24-7 sports events, the yank-'em off amateur hour, sit-coms of the average family with the wealth of the top 99.9 percentile, and boring but chic comedy shows with their drawn-out skits which have no joke but where you have to laugh like you did when your were a teenager and heard a joke you didn't understand, you might stumble across a program about the achievements of mankind. Although increasingly rare, they are there.
But even those program tend to shoot for the melodramatic. Not too long ago, you could lean back, press the remote, and suddenly you beheld a stone faced narrator telling with monotone melancholy about the lives of two mathematicians, Georg Cantor (pronounced "GAY-org", but we'll call him "George") and Kurt Godel. Lamenting how their amazing discoveries drove them crazy, we learn George went near insane grappling with the concept of multiple infinities and Kurt's mental stability deteriorated as he grappled with George's problem and the concept of the non-provable truths. Of course between these scenes we get the inevitable talking heads - the experts who fill in the details on what these gentlemen did. But with only twenty seconds at a pop, generally the viewer's left as uncertain (no joke intended) as before.
Although not really a bad introduction to the work of these two fellows (and of two more), this show definitely suffered from the Definciency of the Tube. First, there was a misplaced cause-and-effect message. Yes, both men had mental problems which ultimately became true mental illness. But it's highly questionable that their work was the primary cause. We also come away from the program hearing that Kurt and George had made discoveries of near mystic profundity shaking the very foundations of truth and the mind of man. Now that might be pushing it a bit, although what Kurt and George did was important.
Oh, yes, it's probably not fair to expect a TV show is to go into the technical details of what George or Kurt did. But on the other hand the only way to decide how profound their discoveries are is to see exactly what they did. Now admittedly Kurt's work is very mathematical and in its original form nearly incomprehensible. However, what George did is not difficult to understand at all. Whether it's profound is a personal opinion, but it is undeniably one of the slickest mathematical tricks ever invented, a discovery that was totally glossed over in the program.
George's discovery - one of many - was to come up with the diagonal argument. Although George used it mostly to talk about infinity, it's proven useful for a lot of other things as well. The best of its applications is to prove there are things can't be proven. Ultimately that's what Kurt did, but we'll get to that at the end.
George's interest was not infinity per se. What he was doing was developling set theory. Remember how you were always bored because every book of math you had in school started off with sets? And you didn't see what the heck it had to do with any of the following chapters? Well, you can blame George for that.
But in developing set theory, George came across the need to precisely develop the notion of infinite sets. After all if you want to talk about counting numbers, integers, and the points on a line, you have to know about infinity. George found there was a way to do this precisely and unambiguously.
George decided to start off simple: pick the counting numbers. Now George and everyone knew there is an never ending supply.
The symbolism is pretty clear. You can pick any number, no matter how large, add 1 to it, and you'll always have another number. This property then defines the infinity of the counting numbers. And if a set has members that can be put into a one-to-one correspondence with counting numbers, then George said that set was countably infinite.
George, though, found there were some oddball properties of a countably infinite set. For instance, some subsets of countably infinite sets are also countably infinite. For instance, you'd think there would be only half as many even numbers as counting numbers. But George showed you can put the counting and even numbers into the one-to-one correspondence. So the two sets have the same number of elements.
2
2 4
3 6
.
.
.
So half of a countable infinity is still a countable infinity!
Another weird property is that if you combine a countably infinite set to another countably infinite set, the new set is also countably infinite. Take the natural numbers (ergo, 1, 2, 3, etc.). Group them with zero and the negative numbers (-1, -2, -3, ...) and what you have is the set of integers. But you can prove the number of integers is the same as the number of counting numbers simply by setting up the following one-to-one correspondence. And although it's a little more complex, George showed that the fractions - rational numbers - are also countably infininte.
0
2 -1
3 1
4 -2
5 2
6 -3
7 3
.
.
.
So you can more than double the number of a countable infinity and still have a countable infinity! The part is the same as the whole and the whole is the same as the part! Very strange but rigorous from a mathematical point of view.
What stamped George as a great mathmetician is he realized he didn't have to worry about the strange results (although some of his colleagues did). He just accepted them, and with them he invented the concept of cardinality. Essentially the cardinality is simply the size of a set.
For finite sets determining cardinality is simple. That's just the number of elements in the set. For infinite sets, though, it's a bit more abstract. Two sets (and this includes finite sets) have the same cardinality if their elements can be paired off in a one-to-one correspondence. Therefore all countably infinite sets - the even numbers, odd numbers, integers, fractions or whatever - also share the same cardinality. Since infinity is not a number, George designated the cardinality of a countably infinite set by the a symbol called aleph null
or 
.
So far so good. But then George found not all infinities were created equal.
One property of sets is that you can make sets of sets. Take the set { 1 , 2 , 3 }. Now take all combinations of the numbers and put them in sets. What you have is:
Notice that there are 7 sets. In other words,
if you have a set with three members you can make 7 sets or
23 - 1 sets. To make it nice and easy, mathmeticians say
the empty set {}, that is a set with nothing in it and most often represented by 
, should also be counted as a subset. That makes of eight sets from a set of three elements. So if you have a set of n elements you have a total
2n subsets.
Now put all these sets into still another set and call it the power set of the original set. A power set of a set S is represented by writing by 2S.
So for our set { 1 , 2, 3 } the power set is :
}
OK, but what about the set of counting numbers? How many sets can you make from a countably infinite set?
Well, if you go by the formula we came up with
above, then it should be 2 taken to the power of .
But what the heck number is that? I mean a number to the infinity
power should be infinity, right? Can't we just say it's infinite too,
and say the cardinality of the power set of the natural numbers is
as well?
Now that would be true if you can show that you can put the set of natural numbers into a one-to-one correspondence with its power set. It turns out, though, that this is the same (and George showed it was the same) as trying to set up a one-to-one correspondece of the set of natural numbers with set of real numbers.
Now the real numbers not only include fractions (¼ ½, ¾, etc.), but also the irrational numbers like the square root of 2, and our friend pi (3.141592653589793238462643383279502884197, etc., etc.). But at the same time, we remember you can combine a countably infinite set with a countably infinite set and still have a countable infinite set. So could the set of real numbers also be countably infinite? This is where George came up the diagonal argument.
George's proof, we should mention, is an indirect proof. Your starts off assuming the opposite of what you wants to prove. Then you ruminate until you find a contradiction with something you know is true. Once you do that, logicians tell us, then what we wanted to prove in the first place - that is, the opposite of our assumption - is correct.
The diagonal argument relies of being able to represent real numbers as we did in school. You put a decimal point someplace and then put a string of numbers afterwards. That way you can represent intergers, fractions (repeating and non-repeating), and irrational numbers by the same notation
Integer 1.000000000000000000000000000000000000000000000.......... Non-repeating fraction 0.250000000000000000000000000000000000000000000.......... Repeating fraction 0.123123123123123123123123123123123123123123123.......... Irrational Number 1.414213562373095048801688724209698078569671875
.........
OK. For our indirect proof, we'll start off assuming you can put the real numbers into one-to-one correspondence with the natural numbers. To make things simpler, though, we'll restrict our lists to the real numbers between 0 and 1. If they can't be put into a one-to-one correspondence with natural numbers, then the rest of the points on an infinite line sure can't either.
A partial list of the one-to-one corresondence might look something like the following table. Again this isn't to be take too literally but is simply a hypothetical example.
|
|
|
|
10 |
0.000000000100000000000000000000000000000000000.......... |
|
128931 |
0.500000000000000000000000000000000000000000000.......... |
|
583910 |
0.414213562373095048801688724209698078569671875.......... |
|
3291293 |
0.515151515151515151515151515151515151515151515......... |
|
78481839 |
0.718281828459045235360287471352662497757247093.......... |
|
948118319 |
0.141592653589793238462643383279502884197169399.......... |
But this won't help us prove the theorem. What we need is a more more general representation, all the better to reason with. So what we do is dream up a symbolic list. Ergo:
|
|
|
|
1 |
0.d11d12d13d14d15d16d17d18d19 .... |
|
2 |
0.d21d22d23d24d25d26d27d28d29 .... |
|
3 |
0.d31d32d33d34d35d36d37d38d39 .... |
|
4 |
0.d41d42d43d44d45d46d47d48d49 .... |
|
5 |
0.d51d52d53d54d55d56d57d58d59 .... |
|
. |
|
|
n |
0.dn1dn2dn3dn4dn5dn6dn7dn8dn9 .... |
|
. |
In other words, write a zero with a decimal point followed by a series of numbers that goes on forever. Remember if - and it's a big if - the real numbers can be put in one-to-one correspondence with natural numbers there is a list like this even if it would take forever to write it down and we don't know what it is.
The kicker is this: If we can show that once you've written the list above you can still write another number that wasn't there then our initial assumption - the number of natural numbers and real numbers are the same - can't be true.
It turns out a new number is very easy to write. Call it m and define it as:
In other words take the diagonal elements of the original list - that is, take d11, d22, d33, d44, d55 and all the rest and then add one to them. Then line them up after a zero and a decimal point. This is a real number, and if our assumption that the real numbers and counting numbers have a one-to-one correspondence it true, then that number will be somewhere in our original list.
All right. Just where does this number fit in the list? It can't be the first place because the first number after the decimal point is d11, not (d11+1). It can't be the second place either since the second number is d22, not (d22+1). Third place? Nope. That has d33 not (d33+1).
It's the same for any number you pick. There is no place in the whole lousy list where you can put the new number, m. That is, for any natural number n the new number cannot be put in the list since the original list had dnn and our new number has (dnn+1).
And the consequence? If the real numbers and rational numbers were in a one-to-one correspondence we can always come up with a new number that's not in the list. That's our contradiction. So our assumption you can put the two sets into the corresponence is incorrect.
At this point it's tempting to say, "Well, you can add one to a countably infinite set and still have a countably infinite set. So we'll advance every number by one place, and stick in the new number. So now we have our one to one correspondence with the counting number.
Well, that doesn't work either. You can still take the new diagonal, add one to each number, and come up with a number that's not in our new list. You can't win and the real numbers and counting numbers cannot be put in a one-to-one correspondence.
But more to the point. If the real numbers and counting numbers cannot be put in a one-to-one correspondence and we are coming up with new numbers, then there are more real numbers than natural numbers. That means there's too many real numbers to count. Now that means we have two types of infinity. One is countable (the natural numbers) and the other is uncountable.
Calling a spade a spade, George called this new and uncountable infinity an uncountable infinity. A lot of sets are
uncountable: the number of points on a line, the number of points on
a plane; stuff like that. Since this infinity is larger than the
earlier infinity, George called this infinity, aleph one, 
.
You can, though relate the two alephs. Remember
the power set of natural numbers? George showed that if the
cardinality of a countable infinity is
then the cardinality of an uncountable set
is:
The point to remember is
is larger than .
That is the diagonal argument. And we've proven that there are more real numbers than counting numbers. But now what can we do with it?
Well, how about proving there are more truths in the universe than we can prove? The diagonal argument has let us do that. But first we need to decide what it means to prove something. And to do that we need to know what we mean by a theorem.
In math or logic, when you want to prove something you have to start with a set of premises. In math these are axioms or previously proven theorems. Then by deductive reasoning you arrive at your conclusion.
Now if you do this right, each step of your reasoning is either an axiom, a previously proven theorem, or a new statement derived (correctly) from one or more of the previous steps. Eventually (if you're correct) then the last step in your line of reasoning will be the final conclusion you want. That last line is the theorem. The whole list of symbols from top to bottom is your proof.
The simplest and most boring "proof" in the history of mankind began with Aristotle. But it shows the difference between a proof and a theorem.
In this case the theorem is the final sentence. "Socrates is mortal." That's what you have proven. The proof is the list of sentences that lead to the final statement.
In essence then a proof is a list of statements arrived at by a given set of rules. Whether the theorem is in English or another "natural" language or is written symbolically doesn't matter. What's important is a proof has a finite number of steps and so a uses finite number of symbols.
Now it is true that the number of symbols is open ended. If you don't want to use English you can use mathematical and logical symbols. In that case, you can have an unlimited number of variables which can be written as x0, x1, x2, ... and so on forever. But at most we can only use a countably infinite number of symbols. So any theorem must be shorter than a countably infinite number of steps and the limit of symbols is likewise countably infinite.
So no matter how many theorems we prove, books we write, or politicians give speeches, the symbols used will always make at most a countably infinite list. So at most there are only a countably infinite number of mathematical theorems and so only a countably infinite set of proofs.
So now as the $500 an hour psychiatrist said after a year of twice a week sessions, we can begin, yes?
OK. Let's take the set of natural numbers and make the power set. That is make all possible subsets of the natural numbers.
Then pick a number, any number. We'll pick the number "1". Then for every subset it will be either true or false that "1" is a member of that particular set. So there is at least one true mathematical statement associated with each subset of the natural numbers.
But wait. How many truths do we have? Well, since the number of subsets of the natural numbers is uncountably infinite, there must be an uncountable number of true mathematical statements.
But remember what we said above? We only have a countable number of theorems. So there are not enough theorems to prove all the true mathematical statements.
Yes, Virginia, there are there are true mathematical statements that can't be proven.
How about that?
References
Metalogic: An Introduction to the Metatheory of Standard First Order Logic , Geoffrey Hunter, University of California Press, (1973).
As hard as it is to believe, there are many people who think that the CooperToons Merry Histories and Educational Essays are written in a spirit of sarcasm and in fact are satires of scientific, philosophical, and theological writings. But a quick perusal of Geoffrey's book (just the first chapter for crying out loud) will show you that the proof given in such painful length and detail above is essentially that which Geoffrey gives us with much less wind.
Geoffrey's book is intended for people who have some introduction to formal logic but otherwise its for the layman who is interested in going beyond the "Socrates is mortal" type schtick. As he points out, if you take a logic course in college they usually end before you get to studying the interesting stuff.
An alternative proof, by the way, to show there are true statements with no proof is to realize you have specifiable sets which can be expressed as a formula, and there are other sets which cannot be specified as a formula.
For instance the set of even numbers, E, is defined as:
This is read as "The set E is the set of all x such that x = 2n where n = 1, 2, 3, ...
So in general a set, S, is specifiable if you can write it like:
where P(x) is a formula you can plug x into and get a member of the set.
Now you can only prove an element is in a set if the set is finite - which means you can check each element if you have the time - or if you have a formula for determining if the element satisifies the equation. But there are only a finite number of formulas or at best a countably infinite number of formulas. As we showed there are uncountably infinite sets, there are sets without an associated formula and yet are infinite. So you there are some sets where you can't tell if a given number is a member or not - even though it is. So once more we have more true mathematical statements than we have proofs.
Links
Return to Kurt Godel Brief Biography
Return to CooperToons Department of Education