A Most Merry and Illustrated Explanation
(With a Merry Theorem of Proof Theory Thrown In)
George showed it wouldn't fit in.
Not too long ago, while surfing the TV channels, you could lean back, press the remote, and suddenly you found a show about Georg Cantor (pronounced "GAY-org", but we'll call him "George"). The story told of how George, one of the most important mathematicians in history, went insane grappling with the concept of infinity.
Although not really a bad introduction to the work of George (and three more mathematicians and physicists) it's highly questionable that his work was the primary cause of his mental problems. And because the show was intended for a general audience, it did not go into details of what George actually did.
On the other hand the only way to decide how profound George's discovery was is to see exactly what he did. Now, yes, many of the mathematical discoveries during and after the 19th century are difficult to understand. But what George discovered was undeniably one of the slickest mathematical tricks ever invented and is easy enough to follow for anyone who reached middle school mathematics.
George's famous discovery - one of many by the way - 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 being part of the famous theorem of undecidability of mathematics that Kurt Gödel came up with.
George's interest was not infinity per se. What he was doing was developing set theory.
Some sets, George realized were infinite. The sets of counting numbers, integers, and the points on a line had no limit to how many members they had. But the concept of infinity was not well defined. Just saying an infinite set has no limit to its members is simply saying an infinite set is infinite. So George decided he needed to come up with a precise and unambiguous definition of what infinity was.
George decided to start off simple. Pick the counting numbers. Now George and everyone knew there is a never ending supply of those.
N = { 1 , 2 , 3 , 4 , ..... }
Here George realized that if there was an upper limit to the counting numbers, then there was some number that could pick that had no higher numbers.
But that meant there had to be some number you couldn't add 1 to and get another number. But that was absurd. No matter how large a number you pick, if you add 1 to it, you'll always have another number.
This property - that every counting number has a successor - then defines the infinity of the counting numbers. The counting numbers then are countably infinite. And if any other infinite set has members that can be put into a one-to-one correspondence with counting numbers, then George said that set was also countably infinite.
George, though, found there were some oddball properties of countably infinite sets. For instance, some subsets of countably infinite sets are also countably infinite. For instance, you'd think there would only be 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:
1 | → | 2 |
2 | → | 4 |
3 | → | 6 |
⋮ |
But this type of diagram isn't good enough for "rigorous" mathematical articles. A more exact way to state that there are the same number of even numbers as counting numbers is to create a set or ordered pairs, P, defined by:
P = { (n, 2n) where n = 1, 2, 3, ...}
The key point is that for any integer, n, you have both a counting number - which is n - and its double, 2n, which is a unique even number. So there is a one-to-one correspondence between counting numbers and the even numbers. That means that 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 and strange, George showed that the fractions - rational numbers - are also countably infinite.
1 | → | 0 |
2 | → | -1 |
3 | → | 1 |
4 | → | -2 |
5 | → | 2 |
6 | → | -3 |
7 | → | 3 |
⋮ | ||
This can be put a bit more formally as:
Odd Numbers: | (n - 1)/2 |
Even Numbers: | -n/2 |
Now this formulation would probably pass muster in a mathematics journal. But if you want an even more formal representation, you can define the set P containing the ordered pairs:
P = (n, (-1)^{(n+1)}n/2 - [(1 - (-1)^{(n)}])/4)
where n = 0, 1, 2, 3, ...
which is the same as the more familiar algebraic notation:
f(n) = (-1)^{(n+1)}n/2 - [(1 - (-1)^{(n)}])/4
Try this formula. Like the commercials say, it really, really works.
(At this point, we have to admit that although we have shown the formulas for the one to one correspondence of counting numbers and the other sets, we have not actually proven the formulas are correct. This would require a process called mathematical induction. It can be a bit tricky but not so tricky that the average person can't understand it. For a Most Merry and Illustrated essay with an introduction to induction click here.)
What stamped George as a great mathematician 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 as long as 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, ℵ_{0}
So far so good. But then George found not all infinities were created equal. He realized this when he started thinking about subsets.
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:
{ 1 } , { 2 }, { 3 }, { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 }
Notice that there are 7 sets. In other words, if you have a set with three members you can make 7 subsets or
2^{3} - 1
... subsets. But to make it nice and easy, mathematicians 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 eight subsets from a set of three elements.
So if you have a set of n elements you have a total of
2^{n} subsets.
Now put all these sets into still another set and call it the power set. A power set of a set S is represented by writing by 2^{S}.
So for our set { 1 , 2, 3 } the power set is :
2^{{ 1 , 2, 3 }} = { { 1 } , { 2 }, { 3 }, { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 }, φ }
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, then it should be 2 taken to the power of ℵ_{0}.
2^{ℵ0}
It was at this point that George thought that this new number was more than countably infinite. This is where George came up the diagonal argument.
George's proof, we should mention, is an indirect proof. That is, you:
Assume the opposite of what you want to prove. |
Start to reason until you come to a statement we know is false. |
Then we know (so the logicians tell us) the opposite of what we want to prove is incorrect. |
So what we wanted to prove in the first place is true, after all! |
(The proof that an indirect proof works is a simple theorem of logic, but we'll skip it for now.)
So George first assumed he could match the counting numbers and real numbers in a one-to-one correspondence and then proved that assumption produced nonsense. Ergo, you could not match the counting and real numbers.
And to this end he invented the diagonal argument.
To use the diagonal argument we first 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
Type of Number | Representation |
Integer | 1.000000000000000000000000000000000000000000000.......... |
Non-repeating fraction | 0.250000000000000000000000000000000000000000000.......... |
Repeating fraction | 0.123123123123123123123123123123123123123123123.......... |
Irrational Number | 1.414213562373095048801688724209698078569671875 ......... |
Now if the set of real numbers has the same size - the same cardinality - of the counting numbers, the two sets can be put into a one-to-one correspondence. And this is an indirect proof, we'll start off assuming you can put all the real numbers into one-to-one correspondence with all the natural numbers.
To make things simpler, though, we'll restrict our lists to the real numbers between 0 and 1. If they can not 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 correspondence might look something like the following table. Again this isn't to be take too literally but is simply a hypothetical example.
(Hypothetical) Place in List |
Number |
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:
Place in List | Number |
1 | 0.d_{11}d_{12}d_{13}d_{14}d_{15}d_{16}d_{17}d_{18}d_{19} .... |
2 | 0.d_{21}d_{22}d_{23}d_{24}d_{25}d_{26}d_{27}d_{28}d_{29} .... |
3 | 0.d_{31}d_{32}d_{33}d_{34}d_{35}d_{36}d_{37}d_{38}d_{39} .... |
4 | 0.d_{41}d_{42}d_{43}d_{44}d_{45}d_{46}d_{47}d_{48}d_{49} .... |
5 | 0.d_{51}d_{52}d_{53}d_{54}d_{55}d_{56}d_{57}d_{58}d_{59} .... |
⋮ | |
n | 0.d_{n1}d_{n2}d_{n3}d_{n4}d_{n5}d_{n6}d_{n7}d_{n8}d_{n9} .... |
⋮ |
Now if it is true there is the one-to-one correspondence with the counting and real numbers, then it will be impossible to find another real number other than the ones we've already matched up with the counting numbers.
But what happens if we do find another real number that wasn't paired up? Well, then we've found our contradiction. And that means our initial assumption - that there is the one-to-one correspondence of natural and real numbers - can't be true. And the infinity of the real numbers is not the same infinity as the counting numbers.
In fact, it turns out our mysterious new number is very easy to write. Call it m and define it as:
m = 0.(d_{11}+1)(d_{22}+1)(d_{33}+1)(d_{44}+1)(d_{55}+1)(d_{66}+1).....(d_{nn}+1)....
In other words. take the diagonal elements of the original list - that is, take d_{11}, d_{22}, d_{33}, d_{44}, d_{55} 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.
(Strictly speaking, what we do is slightly more complicated. If d_{mm} is 0 through 8, then we substitute d_{mm} + 1 for d_{mm}. But if d_{mm} = 9, the d_{mm} becomes 0).
All right. Just where does this number fit in the list?
Well, it can't be the first place because the first number after the decimal point is d_{11}, not (d_{11}+1).
It can't be the second place either since the second number is d_{22}, not (d_{22}+1).
Third place? Nope. That has d_{33} not (d_{33}+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 d_{nn} and our new number must have (d_{nn}+1).
And the consequence? If the real numbers and rational numbers were in a one-to-one correspondence, then any number we come up with should have been in the list. But we have a number that is not and can never be in the list. That's our contradiction. So our assumption you can put the two sets into the correspondence 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. We'll elaborate some more on why you can't expand the list later.
But consider this point. If the real numbers and counting numbers cannot be put in a one-to-one correspondence and we are coming up with extra numbers, then there are more real numbers than counting 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. And it turns out that 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, ℵ_{1}.
How are these two alephs related? Well, do you remember the power set of natural numbers? George believed that that if the cardinality of a countable infinity is ℵ_{0} then the cardinality of an uncountable set ℵ_{1} is:
ℵ_{1} = 2^{ℵ0}
This equation represents what George called the continuum hypothesis. He also believed that there were no infinities between these two numbers. That is, there is no set whose cardinality is between the cardinality of integers and the cardinality of the real numbers.
Kurt and Paul
They finally solved it.
Despite George's efforts to prove the continuum hypothesis he had no luck in doing so. That's because it can't be proven. The continuum hypothesis is instead independent of the other axioms of set theory. That was shown by the work of two men. In 1940, Kurt Godel showed the continuum hypothesis cannot be disproven with the set theory axioms. Then in 1963 Paul Cohen proved they can't be proven either.
That means the continuum hypothesis is like Euclid's fifth proposition. It is independent of the other axioms. If you want, you can create a set theory where the continuum hypothesis is true. Or you can create a set theory where it is not.
The point to remember is the counting numbers are a subset of the real numbers, and the two sets are not equal. Ergo, there are more real numbers than counting numbers and ℵ_{1} is larger than ℵ_{0}.
The diagonal argument bothers a lot of people, and you will find many spittle flinging diatribes on the Fount of All Knowledge (i. e., the Internet) that attempt to prove it is wrong. All of these objections - regardless of how much mathspeak they use - are erroneous and can be distilled down to simple but subtle misunderstandings.
A common error we mentioned before is to believe you can indeed bump-up-the-numbers and slip in the new diagonal number. And as we pointed out, slipping in a new number only leads to a never ending goose chase since you can always create a new diagonal that's not in the list. But some people reason that because you can engage in a wild goose chase, then that means the real and countable numbers are indeed the same size. This belief, though, is due to a misunderstanding of proper reasoning used in an indirect proof.
Remember, our premise was all - that's all - real numbers could be assigned uniquely to every counting number. But then you found a real number that could not have been assigned to one of the real numbers. So you found a contradiction.
In an indirect proof, finding a contradiction invalidates your premise. So if you now say you can bump the number lists up to establish a one-to-one correspondence, you are saying you can do what you just proved impossible. Saying you can bump up a number to prove George was wrong actually means you've proven George was right.
But yes, you say, you found a contradiction. But that only means some assumption is false. Who knows? Maybe, there is another fundamental flaw in arithmetic that really caused the contradiction - not the assumption of a one-to-one correspondence between the reals and the counting numbers. What about that?
Well, in the next section we will show that there is a proof which, though it may seem indirect, is in fact, not. Instead we will devise an effective method, to generate unique real numbers each of which will be assigned to every counting number. Then we'll create a number that will never be in the list - no matter how much you bump up.
George could have pulled it out of his - ah - hat.
Strangely, you'll find there are people who believe the diagonal argument is wrong because the proof uses dots when writing a series of numbers 1, 2, 3, ..., n, ...., etc. For some reason they triumphantly point out the dots - particularly at the end - mean you can always slip in as many counting numbers you need for any number of real numbers.
Fortunately that objection is totally erroneous because the dots are simply a simplification of more rigorous notation. And this objection is disposed of quite easily by using the more rigorous notation as we will not proceed to do.
The diagonal proof is, we will restate, accomplished by first writing a function that maps every counting numbers with a unique real number. For the two sets of numbers to be the same size, then every real number must have a corresponding natural number.
All right. We'll add the rigor here and point out that our function is formally an ordered pair of numbers, something anyone with middle school math is familiar with. The first number is a unique natural number and the second number of the pair is a unique real number. Our function is the set of all such ordered pairs.
So to begin George's proof completely without dots, we now define a set of ordered pairs:
A bit of explanation may be in order. What the formula above means is we have defined a set of all ordered pairs (x, y_{x}) where x is a member of the natural (counting numbers). This means that there are as many ordered pairs as counting numbers.
The second element of the ordered pair y_{x} is defined as:
The part of this equation, y_{xi}, is in turn defined as:
y_{xi} = RND( {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} )
That is, y_{xi} is simply a single digit from 0 to 9 but randomly selected.
Knowing that the capital letter Sigma, Σ represents summation, we see that y_{x} is a number represented by a decimal point followed by a random infinite series of the digits from 0 to 9. Ergo, the ordered pair (x, y_{x}) has a counting number for the first number and a real number for the second.
First we need to deal with the pesky requirement that y_{x} values are unique. But fortunately we don't need to have some algorithm to weed repeats out since there can be no repeats. A little minor reflection tells us that no two values of y_{xi} are identical.
Alas, for those for whom the reflection does not yield immediate gratification, consider two numbers. Call them, y_{r} and y_{s}. We will define them as we did y_{x} but sum over a finite number, k, of randomly chosen digits.
For instance, if k = 10, then y_{r} and y_{s} could be.
y_{r} = 0.4408754017
y_{s} = 0.8598501984
Now of course if we kept trying we would eventually end up with two values that happen to be equal. But just what is that probability? That is, y_{r} and y_{s} will be the same?
y_{r} = 0.5200845709
y_{s} = 0.5200845709
Well, that's easy enough to calculate. Since we have k digits (here k = 10), the probability that two series of digits of length k are equal is given by:
That is, if, we have two series of numbers that are 2 digits long, the odds that the numbers are equal is 0.01. If they have three digits, then the odds are 0.001 they will be the same. With 10 digits (as we have in our example) we have a probability 0.0000000001.
So if y_{r} and y_{s} have an infinite number of digits:
This means that with our definition of y_{x} with an infinite number of random digits after the decimal point, no two y_{x} values will be the same. Ergo, each y_{x} will be unique.
(Note: We emphasize that is not true if k is a finite number. Then if you create enough y_{x} values, then eventually you'll find two that are the same. That's the famous Birthday Problem but generalized.)
What we have done, here, is not set up a premise for an indirect proof. Instead, we have defined an effective method for generating unique real numbers, each of which can be assigned to a unique counting number. What follows, though, may appear similar to our earlier indirect proof is actually a direct or constructive proof.
Now at this point we have to wonder. So far we've generated an infinite number of real numbers each having an infinite number of digits. Now the point to note is that if there are the same number of real numbers as counting numbers, then there cannot be any more real numbers than the ones we have created. And if we can find at least one more real number, then the two sets do not have the same number of elements and there are more real numbers than counting numbers.
And you'll probably guess how we'll do that. Yes, we'll just take our previously defined ordered pairs, (x, y_{x}) and keeping in mind that y_{x} is built up from a series of digits, y_{ik}, we'll write the following ordered pair:
Here y_{ii} is digit i from number y_{n} of our previously (and hypothetically) defined set of ordered pairs. As before if y_{i}_{i} = 9, then we take y_{ii} + 1 = 0, not 10.
(Note: For you sticklers for exactness, that means we actually define the ordered pair, as { n, Σmod( [y_{ii} + 1] / 10) } )
All right. Can the ordered pair be in our original set? Or rather what value of n can we select so is equal to some y_{x} of our original ordered pairs?
Since no digit is equal to itself plus 1, there is no such n. Furthermore, no matter how we change the real numbers assigned to the counting numbers, substituting new reals for the old ones, shifting numbers up and inserting new ones - doesn't help. The number defined as y_{ii} + 1 - or more exactly as mod( [y_{ii} + 1] / 10) - will always be an extra number not in the original list. So you will always have more real numbers than counting numbers.
But (the holdouts continue to say), how can this be an effective method for assigning the counting numbers to a unique real number? Because each real number is an infinite series, you could never write it down. So you can't assign a real number to each counting number because it would take forever to do so. Clearly, the holdouts shout triumphantly, George didn't prove anything.
OK. So we'll just turn the problem over to the holdouts. If George is wrong, then they must prove that once you match the counting numbers with a real number, then it is impossible to create a new real number not in the list.
But George's diagonal argument does what they must prove is impossible!
Soddy, old chaps, George was right. You can't enumerate the real numbers, there are more real numbers than there are natural numbers, integers, or rational numbers.
And there's nothing we can do about it.
In any case, we now have 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.
All men are mortal. |
Socrates is a man. |
Socrates is mortal. |
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 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 x_{0}, x_{1}, x_{2}, ... 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 true mathematical statements that can't be proven.
How about that?
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:
E = {x: x = 2n where n = 1, 2, 3, ...}
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:
S = {x: P(x)}
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 satisfies 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.
Return to Kurt Godel Brief Biography