Excerpt From:
Modern Physics and Ancient Faith
STEPHEN M. BARR
University of Notre Dame Press. Notre Dame, Indiana
Copyright © 2003 by University of Notre Dame Notre Dame, Indiana 46556 www.undpress.nd.edu
Appendix C
Gödel’s Theorem
Historical Background
Godel's Theorem is regarded as one of the great intellectual milestones, comparable in the depth of its philosophical implications to the discoveries in physics of Newton, or Einstein, or Heisenberg. I will try to give some idea of how Godel proved it, but before doing so it may be helpful or at least interesting to sketch a little of the historical background of Godel's achievement.
The first thing to appreciate is that mathematics is not just a collection of facts. Rather, what makes mathematics so interesting—at least to some people-is the fact that one can start with a few obvious and seemingly trivial statements and deduce from them a large number of things that are not at all obvious or trivial. The classic example of this was Euclid's treatise on geometry, written about twenty-three centuries ago, in which he based all of plane geometry with its many beautiful theorems about circles, and triangles, and other shapes on only ten fundamental axioms. Eor many centuries Euclid's achievement stood as the chief example or the power of pure reason, and as a model for mathematicians to emulate.
Later, mathematicians tried to find systems of axioms from which other branches of mathematics could be built up. Gottlob Frege wrote a book at the end of the nineteenth century called The Foundations of Arithmetic, in which he tried to construct an axiomatic system for arithmetic and algebra. Sadly for him, as he was getting ready to publish his magnum opus, Frege got a letter from Bertrand Russell pointing out a fatal inconsistency in a large part of his system. This inconsistency came to be called Russell's paradox.
Frege's difficulty arose from the carefree way in which he had used the notion of "set." (Actually, Frege used the notion of "concept" rather than "set." However, for the present discussion the difference is not important.) A set is just a collection of objects, which are called "members" of the set. One can have sets of anything: sets of apples, sets of oranges, or sets of numbers, for example. One
279
280 APPENDIX C_______________________________________
can even have sets of sets! In fact modern mathematics could not get along without the idea of sets that contain other sets as members. This, along with the fact that he had used sets with an infinite number of members (which modern mathematics also cannot do without), was what got Frege into hot water.
Russell pointed out that if sets can contain sets as members, without any restrictions, then one could have the curious situation where a set contained itself-as a member. Some sets would contain themselves as members, and others would not. Let us call a set which does not contain itself as a member a "normal set." Then one can think about the set—which in honor of Russell we will call R—that is defined to be the set whose membership consists of all normal sets. That is to say, R contains as members all those sets, and only those sets, that do not contain themselves as members. (Notice, by the way, that the set R has an infinite number of members.)
The deadly question —for Frege—was ''does R contain itself?" There is no consistent answer. If R does not contain itself, then it is a normal set— by the definition of what a normal set is —and therefore it qualifies for membership in R, because R contains all normal sets. In other words, if R does not contain itself then it does contain itself. On the other hand, if R does contain itself, then it is not "normal'' and therefore it does not qualify for membership in R. So if R does contain itself, then it does not contain itself.
What a logical predicament! No wonder that Frege was upset. (He was so upset that he uttered the famous lament, "Arithmetic is tottering"! Of course, as Frege understood, arithmetic wasn't tottering, only his attempt to axiomatize it was.)
The same paradox can be stated without using the word set. There is, for example, the "barber paradox": There is a barber who shaves all the men in town and only those men who do not shave themselves. Does the barber shave himself?
Russell's paradox is an example of the contradictions that can arise as a result of what is called "self-reference." A set containing itself is self-referential: if one tried to define it by listing all of its members, one would have to list the set itself in its own definition. This is like a word appearing in its own definition in the dictionary. It ends up chasing its tail. Not all self-reference is necessarily illegitimate. For example, "concept" is a concept. "Abstract" is abstract. "Meaningful" is meaningful. But there are other kinds of self-reference that are clearly improper. A well-known example is the statement, "This statement is false." If it is true then it is false, and if it is false then it is true.
Because of paradoxes like Russell's, mathematicians became aware that mathematical ideas and ways of reasoning that seemed at first glance inoffensive and clear could contain hidden traps and inconsistencies, especially if infinite sets were involved. And therefore a movement for greater carefulness and logical rigor grew up among mathematicians. One of the leaders of this move-
________________________________________ APPENDIX C 281
ment was David Hilbert. Hilbert's proposal for achieving greater rigor was to completely "formalize" mathematics.
I have already explained, in the first section of chapter 22, what formalizing a branch of mathematics entails. Mathematical statements are written in a definite system of symbols, and one reduces all of the kinds of mathematical reasoning one is interested in doing to a precise set of rules for manipulating those symbols. One of the advantages of this way of doing things is that it leaves no room for confusion, or conceptual errors, or subtle ambiguities, or vagueness. In fact, as long as the rules of one's "formal system" are consistent and one adheres to them, there is no room for error at all. In this way absolute rigor can be achieved in mathematics.
A vital question, of course, is whether the rules of the formal system are actually consistent. Consistency, as I said in the second section of chapter 22, means simply that it is impossible to derive both a proposition, P, and its contrary, -P, from the axioms. (Henceforth I will use capital letters to refer to propositions, and the symbol -i to mean "not." In other words the negation of the proposition P is the proposition -P.) Hilbert hoped that if a branch of mathematics were completely formalized, methods would be developed that would allow mathematicians to check that its rules and axioms were completely self-consistent. In that way, mistakes like Frege's could be avoided, and all branches of mathematics could be built on solid foundations.
Suppose, for example, one wanted to check that the rules of arithmetic were self-consistent. One could formalize arithmetical reasoning, and then check that the rules of formalized arithmetic never allowed one to derive a contradiction. Of course, this would lead to a further question: were the methods of reasoning that one used to prove that arithmetic was consistent, themselves consistent? One could try to formalize those rules, of course, and check their consistency. But then the same question would arise again. Were the methods of reasoning one used to check the consistency of those rules, themselves consistent? How can one avoid going on like this forever in an endless regress?
The only way is to prove that the formal system one is interested in is consistent using only methods of reasoning that are available within that formal system. Then one will have both proven the system's consistency and at the same time shown that the steps of reasoning used to do this were themselves consistent. All doubts about consistency would then be laid to rest forever. This is basically the problem that Hilbert set for the world of mathematics.
Formalizing mathematics may sound like a dry and unexciting thing, but it brings other benefits to the mathematician besides logical rigor. The theorems that the mathematician proves also gain in generality. We saw an example of this in the first section of chapter 22, where we proved a little theorem about addition: a + b + c = c + b + a. While ostensibly this was a theorem about addition,
282 APPENDIX C__________________________________________
we saw that it remained true if the symbols are reinterpreted to mean other things. For instance, if + is interpreted to be the sign for multiplication the proof still goes through, so that it also yields a theorem about multiplication. When mathematics is formalized, the theorems that are proven can often be applied in a wide variety of contexts. The same theorem, for instance, might be interpreted as saying something about lines and points, for example, or about numbers.
However, what is gained in rigor and power by formalization is lost in meaning. For, even though the strings of symbols of a formal system can be given various interpretations, it is not really necessary that they be given any interpretation at all. In fact, one can easily invent formal systems without any interpretation in mind. In some fundamental sense, mathematics that has been formalized has been drained of meaning. To make this clearer, imagine a person who has "learned Latin" in the sense that he knows which words are nouns, verbs, adverbs, and so on; knows how to conjugate the verbs and decline the nouns and adjectives; knows proper spelling; and can put together sentences that satisfy all the rules ot grammar and syntax —and yet does not know what any of the words mean. This may sound crazy, but, in fact, computer programs that translate from one language to another are in precisely this situation.
In mathematics conceived of in this purely "formalistic" way. mathematical statements do not "mean" anything. Nor can one say that a mathematical statement is "true" or "false" in the same way that statements about the real world are true and false. All that really matters is whether a proposition —a string of symbols—can be obtained from the axioms by use of the rules. It becomes a sort of game, like chess. In chess a "legal" position is one that can be obtained from the starting position by making moves that are in accordance with the rules. An "illegal" position is one that cannot. No one would regard chess positions as "true" and "false" in any ordinary sense.
Those who take this stance on questions of meaning and truth in mathematics are called "formalists." Such a stance is summed up in Bertrand Russell's famous remark that "pure mathematics is the subject in which we do not know what we are talking about, or whether what we are saying is true." Only a minority of mathematicians and philosophers of mathematics take this extreme view of tilings.1 Indeed, Godel's Theorem is generally agreed to have created difficulties for the formalist viewpoint.
In any event, it was in answer to Hilbert's challenge that Godel started the investigation that culminated in his great theorem. As we saw, what he showed was that in any consistent formal system that contains at least basic logic and arithmetic there are "undecidable" propositions: propositions which cannot be proven or disproven using only the rules of inference available in that system. And among those undecidable propositions is one that, in effect, asserts that the system itself is consistent. In other words, a final mathematical demonstration
____________________ APPENDIX C 283
of the consistency of any formal system that contains at least basic logic and arithmetic is forever out of reach.
Godel in essence showed the inherent limitations of formal systems. If they are consistent, then they are unable to prove their own consistency. And if one has a set of axioms that is consistent, then it is necessarily "incomplete" because it leaves many propositions "undecidable." Godel’s Theorem was the death of Hilbert's program of completely formalizing mathematics. No set of axioms, no formal system of rules, will ever be enough to capture all of mathematical truth.
How Godel Proved His Theorem
It is easy to get a rough idea of how Godel proved what he did, but the actual proof is mind-twistingly subtle. I will give the rough idea first, and then sketch out (in an only slightly less rough fashion) how the proof was actually carried out. Those who would like to know more about the proof of Godel's Theorem should turn to the excellent popular account written in 1958 by Ernest Nagel and James R. Newman entitled Godel’s Proof.2 The explanation here is basically a re-presentation of the account given in Nagel and Newman's book.
A Rough Idea of the Proof
Let us suppose we have a formal system, which we can call F. We will assume that this system is "sound." This is a stronger assumption than mere consistency. A system is sound if all the statements provable in the system are true, and not merely consistent with each other. (As G. K. Chesterton noted, a lunatic can have a perfectly self-consistent but false set of beliefs.) We are assuming that F is sound because it is easier to make the argument with this stronger assumption. Later we will make do with the weaker assumption of consistency.
Let us suppose that in the formal system F there is a statement which says, 'This statement is not provable in F." ("Provable in F" means provable using the rules of inference of F.) In other words, we have a statement, which we will call G, that says "G is not provable in F." Notice that G says something about itself—that is, it is self-referential. I will return to this point later.
Now let us assume, hypothetically, that G is provable in F. That means one can go ahead and prove G in F. What would that imply? Well, first of all, because F is sound, anything that is proved within F must be true. Since G has been proved in F, then G must be true. But what G asserts is precisely that G is not provable in F. So it must be really true that G is not provable in F. However, that contradicts the assumption with which we started at the beginning of this paragraph. We have landed in a contradiction. Since our starting assumption
284 APPENDIX C ______________________________ _
led to a contradiction, it must have been false. That is to say, G must not be provable in F after all.
Thus, I have given a "proof by contradiction" which demonstrates the fact that G is not provable in F. But I have done more. Because the thing that I have proven (namely, that G is not provable in F) is precisely the thing that G itself asserts, I have succeeded in proving that G is true. So, in one fell swoop I have shown both that G is true and that it cannot be proven within the formal system F. This result is all one really needs for the purposes of understanding the Lucas-Penrose argument (see chapter 22, page 213), but we can go further. Let us do so.
Now suppose hypothetically, contrary to what we assumed hypothetically before, that we can disprove G within F. That is, suppose we can prove the contrary statement, -G, using the rules of F. Then -G must be true — because F is sound. But what -G says is precisely that G is provable in F (the contrary of what G said). So we have the situation that G is provable in F (just demonstrated), and that -G is provable in F (assumed at the beginning of this paragraph). But since F is sound, that means that both G and -G are true, which is impossible, since a thing and its contrary cannot both be true. So again we reach a contradiction. Thus, the assumption made at the beginning of this paragraph was false. In other words, G cannot be disproved in F.
Since we showed (two paragraphs ago) that G is not provable in F, and have now shown that it is also not disprovable in F, we have shown that G is "undecidable" in the formal system F. That means the system of axioms of F is "incomplete." But the most interesting fact is that, though G is undecidable in F, we have nevertheless been able to show that G is true.
There are two things wrong with this account of Godel's proof. The first is that we used the very strong assumption that F is sound, whereas Godel (for most of his results) was able to get by with assuming only that F is consistent. But more seriously, we have used what appear to be "self-referential" statements; and we know that such statements are of doubtful propriety. The reader will recall the statement, "This statement is false." That kind of statement, which refers to itself, is known to lead to logical trouble. Are we any better off using statements like “This statement is unprovable in F"?
The answer is that statements like "This statement is unprovable in F" can be made logically acceptable if one is very careful about what one is doing. I will now attempt to give some idea of what being "very careful" means.
A Somewhat Less Rough Idea
The reason why the statement "This statement is unprovable in F" is not acceptable as it stands is that it confuses statements of two types. Suppose the formal system F is arithmetic. Then statements in F are statements about numbers and
____________________________________________APPENDIX C 285
their relationships to each other. Examples of such statements are "2 + 3 = 5" and "if x < y, then y > x." On the other hand, consider the statement "2 + 3 = 5 is provable in F." This is not a statement about numbers, but a statement about a statement about numbers. Statements about numbers and their properties we can call "mathematical statements," while statements about mathematical statements we can call "meta-mathematical statements." They are different kinds of statements. Strictly speaking the same statement cannot be a mathematical statement and a meta-mathematical statement.
We supposed that we had a statement, which said, "G is unprovable in F." If G is a mathematical statement, then "G is unprovable in F" is a meta-mathematical statement. So the statement G and the statement "G is unprovable in F" are different kinds of statements. Therefore, one cannot have the situation assumed earlier where G is the statement "G is unprovable in F." So our "rough idea" of Godel's proof was a bit of a cheat.
In view of this, let us modify the earlier argument as follows. LetG be a statement about numbers; that is, a mathematical statement. And let K be the meta-mathematical statement, "G is unprovable in F." The problem just discussed would arise if we said that the mathematical statement G and the meta-mathematical statement K were one and the same statement; so we will not do that. Suppose, instead, that we somehow yoke together the two statements G and K so that they stand or fall together. That is, if one is true then so is the other, and if one is false then so is the other. How this yoking is to be done we will see later. With such a yoking, we can carry through essentially the same proof as before, as we shall now see, but without having committed the sin of self-reference.
The first step is to suppose that G is provable in the system F. That means we can go ahead and prove G in F. Then because we assume F is sound, it follows that G is true. But since G and K "stand or fall together," it follows that K is true also. But K is the meta-mathematical statement "G is unprovable in F," and so, since K is true, it must actually be the case that G is unprovable in the system F. However, this directly contradicts the assumption with which we started at the beginning of this paragraph, namely that G is provable in F. That starting assumption has led us to a contradiction, and therefore must be false. Thus G is actually unprovable in F, which is to say that K is true. But as G and K stand or fall together, G is also true. We have thus shown both that G is unprovable in F and that it is nevertheless true. This is the result we want, and we have achieved it without using self-referential statements.
How to Do the Yoking
All of this was accomplished because of the yoking together of G and K. The question, then, is how to do the "yoking"? To do this Godel used a concept very
286 APPENDIX C__________________________________________
common in mathematics called "mapping." Two things that are not the same can be "mapped onto" each other if they have the same or similar structures. For example, if I have ten circles of unequal areas and ten stones of unequal weight, I can map statements about the relative areas of the circles onto statements about the relative weights of the stones. Thus the statement, "It circle A is larger than circle B, and circle B is larger than circle C, then circle A is larger than circle C" can be mapped onto the statement, "If stone A is heavier than stone B, and stone B is heavier than stone C, then stone A is heavier than stone C."
What mapping allows us to do is relate statements that are about different things, but which reallv, in a sense, say the same thing and therefore stand or fall together. What Godel had to do, then, was to map mathematical statements and meta-mathematical statements into each other. In particular, since he was talking about arithmetic, he had to create a mapping between statements about numbers and statements about statements about numbers. That means he had to create a mapping between numbers and statements about numbers.
To get a crude idea of how this might be done, let us first invent our own very-simple, and very silly, formal system. Let there be in it just three symbols: A, B, and C. The grammatical rules will also be simple: any string of A's, B's, and C's in any order will be a proper "statement" in the system. So, for example, "ACBBAC" is a proper statement. The rules of inference will be somewhat peculiar: one statement can be derived from another if it has the same "numerical weight." The numerical weight of a statement is defined to be the sum of the weights of its letters, where A, B, and C have the weights 1, 2, and 3, respectively. So the numerical weight of the statement "ACBBAC" is 1 + 3 + 2 + 2+1 + 3 = 12. Finally, I choose the only axiom of the system to be the statement "ABC." (Note that the axiom has a numerical weight of 1 + 2 + 3 - 6.) Let us call this formal system "alphabetics."
It is easy to see that, since the one and only axiom has the numerical weight 6, and since the rule of inference allows a statement to be derived from another if and only if it has the same numerical weight, then all statements of weight 6 can be derived from the axiom and are therefore "theorems" —that is, they are provable within alphabetics. Moreover, only statements of weight 6 are theorems. Suppose, now, we consider some alphabetic statement, S7 which has numerical weight s. (So S is a string of A's, B's, and C's, while s is just a number.) Then the statement "S is provable in alphabetics"—which is a "meta-alphabetical" statement—is equivalent to the statement "s = 6"—which is a statement about numbers. That is, we have mapped a meta-alphabetical statement into an arithmetical statement in such a way that if one is true then so is the other.
Now, what Godel did was something similar but vastly more difficult. He took the formal system consisting of logic and arithmetic — which is much more complicated than our silly made-up example of alphabetics —and invented a way
__________________________________________APPENDIX C 287
of assigning numbers to the statements of this system, just as we assigned "numerical weights." This allowed him to map meta-arithmetical statements into arithmetical statements, in such a way that if one is true then so is the other. Then he was able, in an exceedingly clever way, to find a particular meta-arithmetical statement, "G is unprovable in arithmetic," which got mapped into the arithmetical statement G itself!
Putting It All Together
Now let us put this all together. Let F be a system containing arithmetic and simple logic. And let us only assume that this system is consistent. (We will not need the stronger statement that F is "sound.") Let arithmetical statements be denoted by capital letters, and the meta-arithmetical statements into which they are mapped be denoted by the same letters with "primes" after them. That way we will not get them confused. Let us consider the arithmetical statement G, and the meta-arithmetical statement into which it is mapped, G’. Suppose G is so cleverly constructed that G' is the statement "G is not provable in F." Of course, the arithmetical statement -G (which says the opposite of G) will be mapped into –G’ which says "G is provable in F."
Suppose that G is provable in F. But that is just what -G' says. That would mean that the meta-arithmetical statement -G' is true. But if -G' is a true statement about statements, then -G (which it is mapped into) is a true statement about numbers, because they are yoked together by the mapping. So far we have that -G is a true statement about numbers; but is it provable in F?
Not all true statements about numbers are necessarily provable in F. However, there are some kinds of statements about numbers that if true are necessarily provable in F also. For example, consider the statement, 'There are no prime numbers between 23 and 29." If that is true, then I can certainly prove it using the methods of arithmetic and logic. All I have to do is check all the numbers, 24, 25, 26, 27, and 28, and show that each is not prime. What Godel was able to do was show that the statement -G is the kind of statement about numbers which if true is also provable in F. That brings us to the result that -G is provable in F. So now we have that -G is provable in F, and also that G is provable in F—which was assumed at the beginning of the previous paragraph. But that both G and -G are provable in F contradicts the assumption that F is consistent. Having run into a contradiction, we know that one of our assumptions must have been wrong. Therefore, either F is not consistent, or G is not provable in F.
It follows that if F is consistent, then G is not provable in F, which in turn means that G' is true. By the yoking, this means that G is also true. Therefore, if F is consistent there are propositions (among others G) which are not provable within F but which we can nevertheless see to be true.
288 APPENDIX C_________________________________________
To show that G is not only unprovable in F, but actually undecidable, requires more work. In his original paper, Godel had to use a stronger assumption than the consistency of F to do this. He had to use something called "ω- consistency." But in 1936, an American logician named Rosser showed that the consistency of F is enough to complete the proof.