Gödel's Results on the Completeness
and Consistency of Mathematics

by Cameron C. Pitcairn

 

     Anyone who has had some contact with mathematics sooner or later hears a rumor to the effect that back in the-1930's a man named Kurt Gödel proved that there are statements in mathematics which are in principle undecidable, i.e., statements which can neither be proved nor disproved. Furthermore, he showed that there is no way of proving that mathematics is consistent. Now I have deliberately stated these things in a very rough form because this is the form in which most people have heard about them. So much I had heard as a graduate student, but I never had an opportunity in any of my courses to study_ these matters.

     Of course, if you hear about something like this and give it some thought, there are several natural reactions. The first reactions: "How in the world did he prove something like that?" The second reaction (which logically ought to be the first) is: “What, exactly, did Gödel prove? What were his hypotheses and his conclusions?” Further reflection on the proposition, "There are undecidable statements in mathematics", entangles the casual reader in paradox. In my own thinking, I can remember, the paradox took the following form.

Consider Goldbach’s conjecture, which is the conjecture that any even integer greater than 2 is the sum of two primes.  For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 5 + 5, 12 = 7 + 5, and so on. You can keep on testing even integers until you get tired, and then you can write a computer program to test several million for you, and you will not find a counterexample to the conjecture. Naturally, a lot of effort has been devoted to the search. for a proof of the conjecture, but even though no one has found a counterexample, neither has anyone produced a proof. And so the question arises: Goldbach's conjecture perhaps an undecidable proposition?  Supposing that it is in fact undecidable, what would that imply? It would imply that 128, for example, is not a counterexample to the conjecture, for if it were, that fact would be easily provable in a finite number of steps; the proof would consist simply of finding the sum of every pair of primes less than 128 and observing that no sum was equal to 128. Such a proof would constitute a disproof of Goldbach's conjecture, contradicting our assumption that the conjecture is undecidable. But the same argument applies not only to 128 but also to any other definite integer as well.  Hence, if Goldbach’ s conjecture is undecidable, then no integer provides a counterexample.  But if no integer provides a counterexample, then the conjecture must be true for every integer, i.e., the conjecture s true. If Goldbach's conjecture is undecidable, ten it is true! Is this possible?  Can there be a statement which is known to be true and yet which cannot be proved?

(Paradoxes like this arise partly because our ordinary manner of. thinking is not precise enough. Essentially what Gödel did was to apply a seemingly paradoxical approach in such a precise way that he avoided all semantical fuzziness and logical contradiction).

For some time, then, I have casually wondered:  What did Gödel prove?  How did he prove it?  What implications or suggestions do his results have for mathematics or for philosophy in general?  Since I do not know much about the subject, I decided that the best way to learn about it was to agree to give a talk about it, and thus be forced to learn something about it. I therefore present myself to you today, not as an expert in logic or the foundations of mathematics, but rather as a fellow inquirer who may be able to share something of interest with you.

     I will mention briefly the mathematical history which led up to Gödel’s theorem. For a broader perspective, I strongly recommend that you read Joel Pitcairn's 1956 address to the Swedenborg Scientific Association. *1

      Toward the end of the last century, mathematicians seemed on the verge of establishing solid foundations for mathematics in the theory of sets. This was a welcome development, because sets are in some sense more transparent to our intuition than numbers and other mathematical objects. Founding mathematics on the theory of sets, it was felt, would

give mathematics a solid, certain philosophical basis--or at any rate, as solid and certain as anyone could reasonably expect. But then the para­ doxes started cropping up. Bertrand Russell and others showed that the naive approach to set theory gave rise to logical contradictions, and such inconsistency, of course, is fatal to any putative system of mathematics. Ways were therefore sought to avoid the paradoxes and at the same time to put mathematics on a secure footing.

      One approach to the problem of foundations was to reduce all of mathematics to the formal manipulation of mathematical symbols, where this manipulation is conceived of as proceeding according to a well­ defined set of rules without regard to any possible meaning which might be given to those symbols. Although some of those propounding this approach may have believed that mathematics "really is" nothing but the systematic manipulation of meaningless symbols, such a belief is by no means implicit in the approach itself. From one point of view, this approach may be seen as an attempt to build a modal of mathematics

out of certain symbols and certain formal rules governing those symbols. As with any model, there is no claim (or at least, no necessary claim) that the model is identical with the- thing being modeled, and, as with any model, the thing being modeled has certain features which the model ignores. It is always the hope and intent of the model builder that his model is adequate in spite of--or perhaps because of--the things which it ignor.es. (It was Gödel’s accomplishment to show that no formal model of mathematics can be entirely adequate.)

      If a formal system of symbols is set up, there has to be some way of talking about that system. If. we agree to call such a system "mathematics", then the things we say about that system are collectively called ''metamathematics". The distinction is between statements in mathematics and statements about mathematics, and this is a very necessary distinction if we are to see things clearly.

      A formal system of mathematics can be constructed from the following symbols. *2 In order to motivate the introduction and use of these symbols, and make the exposition intuitively easier to follow, I have given the ''meaning" of each symbol, but you must r ember that the for­ mal rules governing the system make no reference whatever to the meaning of the symbols, and, strictly speaking, neither should we; the system is one from which all meaning has been abstracted.

 

 

Symbol            Meaning                                              Symbol            Meaning

~                      not                                                       0                      zero

V                     or                                                         s          successor of (an integer)

→                    implies                                                (

€                      there exists                                          )           punctuation

=                      equals                                                  ,

 

     In addition to the above symbols, there must be symbols to serve as names of variables. A countable infinity of these will do nicely.

      In addition to a set of symbols, our formal system requires a set of rules to tell us which collections of symbols '1make sense" and which do not. Our rules might tell us, for example, that "O = O" is a collection of symbols which "makes sense", whereas "= = (" is not. Those collections of symbols which conform to these rules are called formulas of the formal system; they correspond to statements in everyday language which are grammatically correct (but not necessarily true). In this paper I will use interchangeably the phrases "formula", "mathematical statement", and "statement within formal mathematics".

      I will not give in detail the rules for constructing formulas, but content myself with the following single example of such a rule: If a given collection of symbols is a formula, then the collection of symbols obtained by writing "~(", followed by the given collection, followed

by ")", is also a formula. (If, for example, we know that "0=0" is a formula, the rule just enunciated allows us to conclude that "~(0=0)"   is a formula. In other words, the negation of a formula is also a formula.)

Notice that our system does not include any numbers other than O. However, the successor function enables us to define all of the natural numbers. For example, “1” is defined to represent "sO", "2" is defined to represent "s1", which in turn represents "ssO", and so on.

From the formal point of view, a symbol like 11211 merely represents an abbreviation for the set of symbols "ssO", and any formula which contains defined symbols like "2" can in principle be rewritten to include only primitive symbols like "s" and "0".

      It turns out that not only the natural numbers but all the ordinary mathematical concepts--such as addition, multiplication, prime numbers, and so on--can be defined (ultimately) in terms of our ten primitive symbols, together with our countable number of variables.

      To finish our formal system, we must include a mechanism for distinguishing the "true" statements from the others. We can start with certain specified statements, called "axioms", and give a set of mechanical rules for deriving sequences of formulas, where each formula is either

an axiom, or else depends (by some definite rule of symbol manipulation) on the formulas which precede it in the sequence. Such a sequence of formulas is called a "proof", and in fact is a model of what we intuitively mean by the word "proof". Each statement follows from the statements before it in some well-defined way. Since the "rules of inference" are strictly mechanical, we can talk about a "proof" in this system without any recourse to psychological certainty or other such vague and debatable concepts.

      The last statement of a proof is, of course, called "theorem" (or, equivalently, a "provable statement") of the system. If I assert that a certain formula of the system is provable, I mean that there exists a proof in the system which has that formula as its last formula. Although the question of whether given formula is or is not provable may be problematical, once a proof has been discovered it is easy to verify that the proof is correct simply by following the rules of inference.

      In 1904, David Hilbert propounded the following goal for mathematicians: first to show that all of known mathematics could be mirrored in a formal system, and then to how, by finite constructive methods of reasoning applied to the formal system, that the system is consistent. A system is said to be consistent if there is no theorem of the system whose negation is also a theorem of the system. For example, in a consistent system it is not possible to prove both "0=0" and "~ (0=0)". In fact, to say that the system is inconsistent is equivalent to saying that every statement in the system is provable. *3

      Principia Mathematica, by Bertrand Russell and Alfred North Whitehead, set forth a formal system, of the sort envisioned by Hilbert, which            · attempted to account for all of mathematics. In the 19201 s, other results encouraged mathematicians to believe that Hilbert's goal was very close to attainment. A proof of the consistency of formal mathematics, by finite constructive methods, seemed "just around the corner."  Then in 1931 came the bombshell: Gödel proved that if the formal system embodied in Principia Mathematica is consistent, then its consistency cannot be proved by any method which is acceptable as a method of proof within Principia Mathematica. Gödel’s proof, moreover, applies not only to Principia Mathematica, but to any formal system which is sufficiently powerful to include the natural numbers (and a fortiori to any system which claims to encompass all of mathematics):- This disheartening result is an almost immediate consequence of the fact, which Gödel proved in the same paper, that any such formal system is incomplete, in the sense that if the system is consistent, then there exists a statement in the system which is not provable within the system and whose negation is not provable within the system. (Such a statement is called undecidable.) Gödel proved that undecidable statements exist by constructing an example of one. *4

In the next few minutes, I want to give you some idea of how Gödel went about constructing his example of an undecidable statement, although his construction was more involved and delicate than I have time to indicate here.

      One of the ancient paradoxes is the paradox of the liar. A man says, "I am telling a lie right now."      Is he telling the truth or not? Another paradox of more recent vintage, propounded by Jules Richard, is as follows: Consider the set of all predicates in the English language which describe properties of integers:  for example, "is prime", "has two prime factors", "is greater than fifteen and less than twenty-one", and so on. Since each such predicate consists of a finite number of letters, we can arrange all such predicates in some definite order--for example in order of increasing length, and alphabetically among predicates of the same length.  Such an ordering gives rise to a numbering of the predicates, with the first predicate in the list bearing the number 1, the second bearing the number 2, and so on. We now define a number n to be Richardian if and only if n does not satisfy the predicate whose number is n. (For example, "is prime" may be predicate number 1000 on our list; if this is the case, then 1000 is Richardian, because "1000 is prime" is false.) Consider now the predicate "is Richardian", and suppose it to be predicate number r on our list. Is r Riehardian? If r is Richardian, then r satisfies the predicate "is Richardian", and hence r is not Richardian. Conversely, if r is not Richardian then r is Richardian.

       An essential feature of Richard's paradox, as of the liar's paradox, is that it involves statements which (directly or indirectly) refer to themselves.

      Recall that Gödel’s Incompleteness Theorem says that any sufficiently rich consistent formal system contains an undecidable statement.  Essentially, the way Gödel proved this was to construct a statement which says of itself that it is not provable. Now, strictly speaking it is not possible for a statement within mathematics to refer to itself, since such statements are not about statements but about numbers (and other mathematical objects). Statements about statements belong to metamathematics. Gödel surmounted this obstacle by demonstrating a correspondence whereby certain statements in metamathematics (which are statements about mathematical statements) can be translated into statements in mathematics (which are statements about numbers).  He showed that for each formula and for each sequence of formulas in formal mathematics, we can compute a corresponding integer (now called the Gödel number of the formula or the sequence), and this is done in such a way that if we are given the Gödel number of any formula (or sequence of formulas), we can, by factoring the number into primes, compute the original formula (or sequence of formulas).

      How are these Gödel numbers used? Gödel showed how to translate certain metamathematical statements, which are statements about formulas, into mathematical statements which assert that the Gödel numbers of those formulas belong to certain sets, and this translation is done in such a way that provable mathematical statements represent true metamathematical statements.

In particular, Gödel constructed a mathematical statement, G, which corresponds to the metamathematical statement "G is not provable." Now if G is provable, then the metamathematical statement, "G is not provable", is true, which is a contradiction. If ~G is provable, then the metamathematical statement, "G is provable", is true, but we have just seen that G cannot be provable. Hence neither G nor ~G is provable, i.e., G is undecidable.

      Note, by the way, that G, though not provable, is nonetheless true. This may sound like a contradiction; but recall that "provable" here means "formally provable within the system by means of a given set of axioms and rules of inference." The metamathematical reasoning

which tells us that G is true does not constitute a "proof" in this sense, nor can it be mirrored by any proof within the system.

      Let us now carry the argument a step further. Let us call the formal system under discussion "S". In our previous remarks we have sketched a proof of the metamathematical statement:  "If S is consistent, then G is not provable."  Gödel showed that this statement can be represented by a statement H within the system S. H, in other words, is equivalent to "C implies G", where C is the statement "S is consistent." H is, in fact, provable in the system S. Now suppose that C is provable in S.  The rules of inference allow us to combine the provable statements C and H to arrive at a proof of G. We already know, however, that if the system S is consistent then G is not provable. We conclude that if the system S is consistent, then C is not provable in S.  In other words, no proof that S is consistent can be mirrored by a proof within S. This is Gödel’s famous result on the consistency of mathematics.

      And so what? I would certainly hesitate to say that a result like this proves something about philosophy, but it may suggest a lot of interesting ideas. The remarkable thing about this proof is that it beats the formalists at their own game. The formalists proclaim that mathematics is nothing but a meaningless collection of symbols, but Gödel showed that there is always something beyond: there are statements which we know are true and which are not accounted for by the formal system, and this holds no matter how much we enlarge the system. In a sense, Gödel showed that there is a higher degree of mathematics which you cannot achieve by manipulating symbols. His methods, moreover, were unimpeachable from any point of view.

      Gödel himself appeared to be a thoroughgoing Platonist. He wrote: "Classes and concepts may … be conceived as real objects …. It seems to me that the assumption of such objects is quite as legitimate as the assumption of physical bodies and there is quite as much reason to believe in their existence. They are in the same sense necessary to obtain a satisfactory system of mathematics as physical bodies are necessary for a satisfactory theory of our sense perceptions, and in both cases it is impossible to interpret the propositions one wants to assert about these entities as propositions about the “data”, i.e., in the latter case the actually occurring sense perceptions. *5

     Joel Pitcairn suggests an analogy with the Heisenberg uncertainty principle; in the one case we have a trade-off between position and momentum, and in the other case we have a trade-off between completeness and consistency. *6 (You can have a consistent system, or you can have

a complete system, but you cannot have both.)

     Starting another line of thought, we might wonder whether it will ever be possible to construct a computer to perform the functions of a mathematician (whatever they are!). One way of interpreting Gödel’s results is to say that any system which consists simply of the manipulation of symbols according to a given set of rules is incapable of taking in all of mathematics. Since a computer is, after all, essentially a mechanical realization of just such a system, we might plausibly conclude that no computer is capable of replacing the creative mathematician. This might also suggest that the way in which the human mind works is in some respects very different from the way in which a computer works.

      In the eighteenth century, David Hume demonstrated in a fairly conclusive way that the empirical method of science cannot be rationally justified simply on the basis of observation. The empirical method depends fundamentally on the inductive principle, i.e., the principle that the world will behave in the future as it has been observed to behave in the past. Since no amount of observation can confirm the inductive principle, unless we assume the principle in some form to begin with, it follows that to believe the principle at all is an act of faith.  There is no way by which one can pull himself by his bootstraps up from the level of sensory data to the discretely higher level of empirical reasoning. Similarly, to believe in the consistency, and hence the meaning, of mathematics requires an act of faith. "Suppose," wrote Frank DeSua, "we loosely define a religion as any discipline whose foundations rest on an element of faith, irrespective of any element of reason which may be present. Quantum mechanics for example would be a religion under this definition. But mathematics would hold the unique position of being the only branch of theology possessing a rigorous demonstration of the fact that it should be so classified." *7

      I want to conclude this talk by suggesting the applicability of the doctrine of discrete degrees. Joel Pitcairn has pointed out that many of the confusions which plague modern philosophy stem from a failure to take into account the. separation which exists between that which thinks and that which is thought about, and he asserts that this "is an instance of the confusion of discrete degrees, and in our opinion no truly adequate philosophy of science can be possible which does not depend explicitly on the doctrine of discrete degrees." *8

This may seem like a rather sweeping statement, but it is justified by the following from Divine Love and Wisdom: "A knowledge of degrees is like a key for uncovering and penetrating into the causes of things.

Without this knowledge hardly anything of cause can be known; for, without it, objects and subjects of both worlds seem so simple, as if there were nothing in them beyond that which meets the eye; when yet, compared to the things which lie hidden within, what is thus seen is as one to thousands, nay rather to tens of thousands. The interiors which do not lie open can in no wise be laid bare except by a knowledge of degrees; for exteriors move towards interiors and through these towards inmosts, by degrees; not by continuous, but by discrete degrees." *9

     I would suggest that what I have been talking about today provides us with an example of discrete degrees, metamathematics being a discrete degree above formal mathematics--or perhaps it would be more accurate to say that the meaning of mathematics is a discrete degree above the symbols of mathematics. Gödel achieved his results by separating the two levels--avoiding confusion between them--but then relating them to each other and exploiting the connection. The doctrine of discrete degrees is a large one, and I do not have the time here to go into it deeply, but it seems to me to throw a very powerful light on our subject, and our subject may in turn serve as a confirmation of the doctrine. *10

      Closely connected with' the idea of discrete degrees is the idea of discrete levels of the human mind. Rational Psychology refers to the "pure intellect", which is that faculty of the mind which grasps truth whole, the faculty which looks at a thing and knows immediately (i.e., without mediation) that it is true. It is a faculty discretely higher than the faculty which allows us to manipulate symbols; the pure intellect is, I suggest, the faculty which invests those symbols with meaning. I cannot help feeling that Gödel’s results lend powerful confirmation to the existence—I might almost say, the logical necessity-­ of such a faculty. *11

"Those whose thought or rational analysis more closely approaches this pure intellect have an instantaneous sight and recognition of many propositions as being true or false, and this without posteriori demonstration from effects, experience, artificial logic, and the scholas­ tic sciences. Frequently, indeed, this is so much the case that they are indignant that the mind should wish to demonstrate things which in themselves, are clearer, more sure, truer, and higher than any demonstration. Attempts at such demonstrations they consider as so many twilight shadows which do not enlighten but rather obscure. Of such sort are we when we become pure intelligences or souls, for then we shall laugh at literary sports as the sports of infants, and at the whole syllogistic logic as a child's game of even and odd." *12

 

A good note on which to end, I think.

 

August 14, 1979

 

NOTES

 

     1. Joel Pitcairn, "The Foundations of Mathematics," The New Philosophy, LIX (July, 1956), PP• 79-91.

     2. The particular formal system presented here is taken from Ernest Nagel and James R. Newman, Gödel’s Proof (New York: New York University Press, 1958).

     3. The principle that in an inconsistent system every statement is provable is an easy consequence of elementary logic. According to my recollection, this principle was once enunciated in a popular lecture by Bertrand Russell as: "If I assume the truth of just one false statement, I can prove anything."  Someone in the audience called out, "Two plus two equals three. Prove you are the Pope.11    Russell replied, "If two plus two equals three, then, by subtracting two from both

sides of the equation, we have two equals one. The set consisting of Bertrand Russell and the Pope contains just two elements, that is

to say (since two equals one), it contains just one element. Since Russell and the Pope are elements of a set containing- just one element, they are identical; therefore, I am the Pope!"

      4. Gödel’s paper, translated into English, is reprinted in Jean van Heijenoort, ed., From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 ( Cambridge, Y ss.: Harvard University Press, 1967), pp. 592-617. A leisurely exposition for the layman may be found in Nagel and Newman, op. cit. A brief but incisive sketch of the proof is given in Nic las Bourbaki, Theory of Sets (Reading, Mass.: Addison-Wesley, 1968), pp. 339-341. - --

      I should note here that Gentzen subsequently gave a proof of the consistency of arithmetic. This does not' contradict Gödel’s result, since Gentzen used a method of proof, namely transfinite

induction, which is not allowable within the formal system which he was

considering. Roughly speaking, we can interpret Gödel’s result

as saying that any proof of the consistency of mathematics must use methods which are of a ''higher order" than any methods of proof which are allowed within mathematics, and of course the validity of these "higher order" methods will be at least as suspect as the validity

of mathematics itself, so that such a proof doe s little if anything to

put the foundations on a firmer footing.

      5. Kurt Gödel, "Russell's Mathematical Logic," in Philosophy of Mathematics: Selected Readings, ed. by Paul Benacerraf and Hilary Putnam (Englewood Cliffs, N.J.: Prentice-Hall, 1964), p. 220.

6. Joel Pitcairn, op. cit. p. 89.

      7. Frank DeSua, "Consistency and Completeness - - A Résumé,"     The American Mathematical Monthly, LXIII ( May, 1956),p. 305.

     8. Joel Pitcairn, review of The Scientific A venture by Herbert Dingle, The New Philosophy, LVII (October, 1954), p. 257.

9. Divine Love and Wisdom, number 184.

10. For more concerning the doctrine of discrete degrees, see Divine Love and Wisdom, number 256, Arcana Coelestia numbers 3691 and 5114, and many other passages, especially in Divine Love and Wisdom.

11. Cf. Joel Pitcairn, “The Foundations of Mathematics,” op. cit. pp. 80-81.

12 Swedenborg, Rational Psychology, number 133.