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 shows, 24-7 sports events, jackass judges on amateur hours, over-decibilized sitcoms, and boring but chic comedy shows, you might stumble across a program about the achievements of mankind. Although increasingly rare, they are there.
But even those programs tend to shoot for the melodramatic. Not too long ago, you could lean back, press the remote, and suddenly you found a show about the lives of two mathematicians, Kurt Gödel and Georg Cantor (pronounced "GAY-org", but we'll call him "George"). Lamenting how their amazing discoveries drove them crazy, the stone faced narrator spoke with melancholy monotone how George went near insane grappling with the concept of infinity, and Kurt's mental stability deteriorated as he grappled with how George's problem lead to non-provable truths.
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 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 so we'll talk about that. Whether what George did is 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 developing 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 a never ending supply of those.
N = { 1 , 2 , 3 , 4 , ..... }
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 an infinite 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.
1 | → | 2 |
2 | → | 4 |
3 | → | 6 |
⋮ |
But this type of diagram isn't good enough for "rigorous" mathematical articles. A more "rigorous" way to state there are the same number of even numbers as counting numbers is to state you can create a new 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, and 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.
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
which simply means if you start with a integer, n, and start counting up, it will produce an alternative positive/negative integer list. Start with zero and you'll ending up pairing all integers with the counting numbers like that shown above.
(Like the commercials say, try this formula. It really, really works.)
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.
(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.
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 sets or 2^{3} - 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 2^{n} 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 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 above, then it should be 2 taken to the power of ℵ_{0}. 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 ℵ_{0} as well?
But if the set of counting numbers has the same cardinality of its power set, then the two sets can be put into a one-to-one correspondence. But that raises a more general question. Are there infinite sets that cannot be put into a one-to-one correspondence. For instance, can the counting numbers be put into a one-to-one correspondence with the real numbers?
Now the real numbers not only include counting numbers, integers, 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. You start off assuming the opposite of what you want to prove. Then you reason (correctly) 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
Type of Number | Representation |
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 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'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.
(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} .... |
⋮ |
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, then such a list of pairings does exist. It doesn't matter if it would take forever to write it down and we don't know what it is.
But consider this. What happens if we do write such a list - that is we pair the counting numbers with a unique real number? Then we show that there is another number that cannot be in the list? 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.
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? 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 has (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.
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 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 using an indirect proof.
Remember, our premise was 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. This, then, invalidates your premise. So if you now say you can bump the numbers up to establish a one-to-one correspondence, you are saying you can do what you just proved impossible.
The crucial point is that any contradiction derived in an indirect proof invalidates the premise, which in turn was the opposite of what you are trying to prove. Finding just that one extra number proves there is not a one-to-one correspondence between the reals and the counting numbers - and that there are more real numbers. 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. We will then prove there are real numbers that cannot be assigned to natural numbers.
There is another characteristic about the proof that bothers people but they find hard to articulate. This problem is that in the diagonal proof you first define a pairing of the natural numbers and real numbers. That is you have a set of pairs of a natural number and a real number. Then once you do that, you not only create another pair of numbers, but a pair that is defined from the set you just created. Then it looks like you assume this new pair of numbers is in the original list!
Creating a set and then defining a new element that is based on the original set and is in the original set is disturbingly similar to how you produce Richard's Paradox (first described in 1905 by Jules Richard). Not only that, but we read that defining new elements from an infinite set and then placing the new elements in the original set is exactly what renders Richard's and other paradoxes invalid. So why is the diagonal proof valid and Richard's Paradox is not?
Actually there are two reasons. Remember that Richard's paradox creates an ordered list of English sentences, each sentence defining a number (actually Jules wrote in French). The paradox next creates a sentence based on the properties of the entire list and then claims this new sentence belongs with the original sentences. So Richard's paradox improperly mixes definitions of the numbers themselves with the properties about the numbers. George did not do that.
But more importantly George is not assuming or placing the new pair of numbers in the old set. He is simply identifying a real number and asking if that number is in the original list and then proving it is not. It's actually irrelevant that he created the new number by adding 1 to the diagonal. He could have pulled a number out of his - ah - hat as long as he could prove it wasn't in the original list. Using the diagonal method just happened to be the simplest method to do this. Any number that can be shown not to be in the original list shows us that the belief that natural and real numbers can be paired is incorrect. And it is incorrect.
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, an objection 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, and his claim that there are two infinities is as chimerical as having two political parties that can put partisan politics aside for the good of the country.
But sadly, we must point out that this is indeed an effective method. That is it is if you understand what infinity really means.
Saying something "goes on forever" isn't really a proper definition of infinity. That's because "going on forever" is simply a way of saying something is infinite. So this (vague) definition of infinity simply says something is infinite if it is infinite.
So a better way to define an infinite series is that no matter what number I pick, there is always a number that's higher in rank. Or equivalently, a list is infinite if you cannot name a counting number that does not have an associated member of the series. So for any counting number, I can determine the x^{th} digit of the associated real number simply by generating a random number from 0 to 9. I don't have to write down the whole series.
But if you do that then I can tell you the corresponding digit of a number not in the list. I simply by adding one to your random number.
So we'll summarize what we've said about why George's proof is correct.
So what have we done? Well, our effective method for assigning real numbers fulfills the requirement for Step 1. The diagonal method - adding 1 to the diagonal element - fulfills the requirement of Step 2 and Step 3. So being able to bump up the numbers in the list is completely irrelevant to the validity of the proof.
To put it another way, if someone says George is wrong, then the burden is on them to prove that if you assign a unique real number to the counting numbers you can't create a new number. But by adding 1 to the diagonal element, you can always create that number.
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:
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