GÖDEL, TURING AND WITTGENSTEIN

This paper came about as a result of reading Hodges’s article on Turing in The Great Philosophers of the World (Weidenfeld and Nicholson, 2000), in which he argues that Turing was as much a philosopher as a mathematician. I was quite convinced by this view, and merely wanted to add to it something I have already pointed out, in my (incomplete) article on Wittgenstein’s MSS 130-138, namely that if Wittgenstein did not exert further influence on Turing after the 1939 lectures, he certainly remembered his arguments with him in those lectures and modified his views correspondingly. However, rather than embroil myself in discussing their respective contributions to mathematical philosophy, I should like to devote myself principally to another person who deserves to be viewed as being as much a philosopher as a mathematician, Gödel, and only discuss Turing and Wittgenstein in relation to him as occasion arises.

In 1952 I studied the opening pages of a paperback edition of Gödel’s Consistency of the Continuum Hypothesis, as I shall describe ahead. In 1962 I read Gödel’s 1931 paper On formally undecidable propositions and translated its opening section (mainly prose). In 1968 or thereabouts, during one of my last meetings with Imre Lakatos, he warned me that it was as important to study Gödel’s ‘completeness’ theorem (1929 and 1930) as his incompleteness theorem (the above-mentioned 1931), but unfortunately I did not take his advice. It was only this year, 2000, that, prompted by Hodges’s remarks about Turing, I borrowed from the London Library the three volumes of the complete Gödel (a fourth is in preparation), edited at Princeton and published by Oxford. It was chastening to discover how little I had understood Gödel and how much more to read there was than the two pieces I knew already. (Incidentally, I shall make use of the editors’ italicised dates to identify Gödel’s works and their similar system of identifying the works of other mathematicians, as listed in the References of the three volumes. I shall also follow their convention of using single square brackets when these are Gödel’s and double ones editorially. I will draw attention to other textual points as need arises.)

To consider the ‘completeness’ papers first, there are actually three of these, 1929 being Gödel’s doctorate thesis, 1930 a revision of it, both in Volume I, and *1930c, the text of a lecture delivered at Königsberg on the 6th of September 1930 which ends with an anticipation of his 1931, still in preparation. (The 1931 paper was also announced, using Gödel’s own abstract, 1930b, by Hahn at the Vienna Academy of Science on the 22nd of October 1930.) The Königsberg lecture is to be recommended to non-specialists as a first thing to study, especially for its summary of the way the completeness problem for propositional calculus had already been solved, the solution serving as a partial pattern for Gödel’s own completeness solution.

Gödel goes on (in the Königsberg lecture) to say that the next step beyond the propositional calculus is the restricted functional calculus (first-order predicate calculus, as it would be called now --- see page 17 of Volume I, in Feferman’s ‘life and work’ introduction). This involves propositional variables and the propositional connectives, function variables (ie variables for predicates), with variables for individuals and quantification over them, but not quantification over variables for functions (predicates and relations). Extended functional calculus allows quantification over functions, and it is this calculus, applied to mathematics, that Gödel (in his 1931) was about to prove incomplete. The difference between the two (completeness and incompleteness) theorems lies as much in a radically different formulation of the problems in question as in the absence or presence of functional quantification. Of these differences, however, the second needs to be discussed first, and it will require a rather long textual aside.

In the opening paragraph of his 1930, Gödel speaks of Principia Mathematica, contrasting the propositional calculus based on its propositional axioms (already shown by Bernays in his 1926 to be complete) with its next stage in complexity, the ‘restricted functional calculus’. Now as Dreben and van Heijenoort point out in their Introductory Note to 1929, 1930 and 1930a (the latter being Gödel’s abstract for 1930), the distinction between restricted and extended functional calculus goes back to Frege’s Begriffschrift (his 1879, reprinted by Georg Olms, 1964). This was Frege’s first presentation of the calculus he used in his two-volume Grundgesetze, and it uses a notation visually quite distinct from Principia Mathematica’s, which is derived from Peano’s notation. This difference is actually trivial, and an examination of Begriffschrift is very rewarding. On page 19, under §11, one finds general quantification introduced for argument variables, with a remark made almost in passing that in the composite sign “φ(A)”, the function-symbol “φ” can just as properly be regarded as an argument of the whole thing as A can be regarded as an argument of φ. Nothing is made of this possibility until §28 on page 68, where one suddenly sees a capital German F (for “Funktion”) in a quantification marker, and a footnote referring back to §11. In other words, this quantified F corresponds to the free φ above. (Using distinct founts for free and bound --- ie quantified --- variables is a grammatical error of Frege’s which, fortunately, subsequent mathematicians and logicians have ignored.)

In his Introduction to 1929, however, Gödel goes into a little more detail, and specifies *1 and *10 of Principia Mathematica as giving the axiom system of the ‘restricted functional calculus’ (occupying pages 91-97 and 138-150 of the 1962 Paperback Edition). Presumably this should include *11, which deals with with functions of two rather than one free variable. It is not until *12, on the heirarchy of types and the axiom of reducibility, that anything that could be called quantification over functions occurs, and unlike the Begriffschrift, where the first occasion hits the eye, some textual digging is required. This is because the Introduction to the Second Edition of 1925 (completed 1927), occupying xlvi pages and reprinted in the Paperback Edition of 1962, is not an introduction in the proper sense but merely a commentary on what changes Russell would have made to the Second Edition if he had had time to make them. Consequently, one is liable to find symbols and expressions in it that have not been defined in it, and one has to look for them in the original Introduction. For our present purposes (of comparing the restricted with the extended predicate calculus) these begin to appear on page 14 under the heading “Propositional functions”, and the first of them is a circumflex over a variable. Russell’s example is what in modern terms we would call the predicate “x is hurt”, which expresses a proposition (true or false) when x is given a particular value (a person or animal capable of being hurt) but until this is done is ‘left in the air’, as we might say ourselves. Russell tidies up this state of affairs by distinguishing between a propositional function which he writes as “x is hurt” (please read a bold x as an ordinary one with a circumflex) and the original “x is hurt”, which he calls an ambiguous value of that function (ie the predicate ‘left in the air’). More generally (he goes on) φx is an ambiguous value of the propositional function φx, and “when a definite signification a is substituted for x, φa is an unambiguous value of φx”.

On the same page (15), Russell introduces universal and existential quantification over individual variables, symbolised by “(x).φx” and “Ex.φx” respectively. On page 16, under the heading Apparent variables, the bound x in “(x).φx” is compared with the bound x in integral notation, where

“∫_a^b Φ(x)δx”

has an a and b which can take particular values but an x which cannot. In the introduction to the Second Edition, however, he says twice (on pages xiii and xviii) that there is no need for the distinction between real and apparent (free and bound) variables and that it can be dropped. He does not, in fact, drop it, but continues to use the respective notations, even in that Introduction of 1925. One has to assume that what Russell wishes to drop is, rather, his explanation of the difference, the details of which are by no means easy to understand, and I leave historians of mathematical logic to investigate and elucidate them.

The next item that a modern reader might need an explanation for comes on page 23, and is the same symbol, a circumflex, used in a new way. Having distinguished a predicate φx from its propositional function ¢x, Russell introduces x(φx) --- or equally z(φz), for since the x is bound and can take no value, any other letter that takes no value will do as well --- as the class determined by the function φx (the class of those things that φ, one might say, or to give one of his examples, “if φx is ‘0 < x < 1’, z(φz) will be the class of proper fractions”). Gödel, in his 1944 criticism of Russell, appears to assimilate Russell’s two circumflex notations, and would take (see page 120 of Volume II) the class z(φz) and the function φz as identical. This is certainly not my reading of Russell.

The final item which I need to mention to introduce the ‘extended functional calculus’ of Principia also has two uses. It is an exclamation mark, and its uses are introduced separately on pages 29 and 51. On page 29:

A class is said to exist when it has at least one member: “a exists” is denoted by “E!a”. Thus we put

E!a. = . (Ex). xea Df

[[and thus we can make an existential assertion out of the name or designator of any class except the null class, which in normal set theory is taken to exist, though of course it cannot attract the existential quantifier “Ex” for its non-existent members. Incidentally, the reader needs to be warned that I have used a standard E where Russell uses a back-to-front one, and that on the very next page he introduces a logical distinction between the two forms.]]

Page 51 comes in Chapter II of the original Introduction, on logical types, where what was already said (starting on page 14) on propositional functions is repeated, and with it the concept of universal quantification (“for any x”). This reiteration is required because Russell is aiming at setting up distinctions between orders of propositional functions. A simple example of this might seem to be the difference between “x is prime” (giving rise to a Russell propositional function x is prime) and “x is human”, giving rise to x is human --- but while common sense might see these as different orders, numbers and people alike are for Russell individuals, and the concept of order he has in mind is that between, say, x is in pain and what circumflexion would make out of “x is a propositional function whose arguments range over animals and people”. Of these, only x is in pain is termed a first-order function, and to express this concept a new notation is required. For this purpose, “φ!x” will indicate a first-order predicate such as “x is in pain” and “φ!x” will denote the first-order propositional function derived from “φ!x” by, as it were, circumflexion.

Now until a particular predicate-value is given to φ, “φ!x” is waiting for values to be assigned at two levels. One is what, after assignment, will be φ itself, and by the exclamation mark convention it has got to be a first-order predicate (and can be referred to as φ!z), whereupon “φ!x” will be waiting for a further assignment, namely to x, before it can count as a particular sentence expressing a particular proposition. It is only at this point (at the foot of page 51) that Russell introduces the word “predicate”, which I have been using already because I assume that readers are familiar with it (and almost immediately he reverts to speaking of functions again). What is important for his exposition is that he now has an ontology of --- as we might say --- ‘first-order predicate values’, and not only for assigning as values to such symbols as “φ” but to be subject to quantification in notations corresponding to “for any first-order predicate” or “for some first-order predicate”. This possibility is then extended to second-order predicates and so, presumably, ad infinitum.

That is the situation that requires the axiom of reducibility to tidy it up, one of the aims of which (on page 57) is to allow a definition of identity. As Russell points out, we cannot say “if, with all values of φ, φx implies φy, then x and y are identical” because if we wish to speak of all values of φ we must confine ourselves to predicates of one order. The axiom of reducibility declares (on page 56) that for any function φ, of whatever order, there is a first-order function Y such that, for any x, φx and Yx are equally true or equally false. Russell expresses the above symbolically by printing “Y!x” for “Yx” to indicate that Y is first-order, and for general quantification he uses Peano’s convention of printing a miniature x as a subscript to the equivalence sign. He is now ready to give, at the foot of page 57, his definition of identity, with general function-quantification over first-order functions, as

x = y . = : (φ) : φ!x . É . φ!y Df

on the grounds that his axiom ensures that for any other order of function or predicate a first-order function serving the same purpose will always exist. This definition is repeated on page 168 in chapter *13 on identity, with the code index *13.01. As I have already said, *11 (starting on page 151) is part of the ‘restricted predicate calculus’ preliminary to Principia Mathematica, and I leave as an exercise for the reader the possibility of finding in *12 (starting on page 161) Russell’s more formal introduction of the axiom of reducibility, and simple examples of quantification over predicates or functions. I should like to add here that, just as Frege’s two-dimensional notation is only trivially different from Peano’s and Russell’s linear notations, so the latter’s dots for brackets (taken from Peano) is only a trivial difference from modern notation, and requires no great persistence to get used to it.

To return to the differences in formulation and strategy that separate 1929, 1930

and *1930c from 1931 and its many follow-up articles and lectures: in the completeness papers Gödel asks if every correct (valid) formula follows from the axioms of Principia Mathematica (in 1930a, the abstract) or, alternatively (in 1930 itself), if there could exist true propositions (provable, perhaps, using other axioms and rules of inference) “that cannot be derived in the system under consideration”. Valid means true for any assignment of values to its free variables, and in the Königsberg lecture, *1930c, Gödel uses the term “tautology” for the same concept, and procedes to explain it via the well-known concept of a tautology in propositional calculus (“a propositional formula is said to be ‘tautological’ if, under any assignment of truth values to the propositional variables that occur in it, it always receives the truth value ‘true’”).

Now everyone who has used propositional calculus in practice knows how easy it is to satisfy oneself by using truth tables whether any given propositional formula is indeed a tautology: if it is, an unbroken line of T’s appears in the final column. The question for formal mathematics is not whether such a formula is a tautology, but whether its being so follows from the axioms and rules of inference laid down in Principia Mathematica. Bernays (I rely here on Gödel’s account in *1930c) did not use this truth table technique (invented independently by Post and Wittgenstein) as his decision procedure but another, which brilliantly kills two birds with one stone. This is to use de Morgan’s laws and ‘multiply out’ successively into “a certain normal form, from which it is then immediately evident whether it is a tautology. Since this decision procedure thus uses only the de Morgan rules and the substitution law, and since --- as one readily sees --- these two principles follow from the axioms above, the decision procedure can be cast into the formal framework: in other words, for every tautological formula it furnishes at the same time [[my italics, on behalf of the birds]] a proof from the axioms and rules of inference above”.

From this strategy provided by Bernays one might expect Gödel to begin by showing how to recognise by some similar decision procedure whether a given ‘restricted predicate calculus’ formula is a tautology, and then demonstrate that its being so follows from the appropriate axioms and rules of inference. He does not do this for the very simple reason, which he must already have suspected, that no such decision procedure exists. He had to content himself with a theoretical question: granted that a formula is valid, is it provable within its system?

Here I need to make an aside about decision procedures, and why they played such an important part in the ideas propounded by Hilbert and taken up by Gödel. Used as we are to the implications of the 1931 results (the inexhaustibility of mathematics, as Gödel expresses it in his *1957, or to quote Kleene --- see page 345 of Volume I --- its “inexhaustible scope for ingenuity”) we wonder how Hilbert could ever have supposed that, outside simple cases like the predicate calculus and digital computation, decision procedures always needed to play a part in the more abstruse branches of mathematics. As Professor Smiley put it to me when I raised this point, the Hilbert dream was, given the state of mathematical knowledge in the twenties, a reasonable one in that it hoped, first, that an algorithmic procedure might exist to decide whether a given problem was soluble, and then, perhaps, another such procedure might actually solve it --- but either procedure could be expected to be so laborious that any sensible working mathematician would look for answers that required mathematical imagination, insight and ingenuity. Hilbert will have felt that the mere knowledge of the existence of such procedures would be a reassurance that all was well with mathematics, however much he must have realised that in practice imagination, insight and ingenuity could never be dispensed with.

Before leaving Gödel’s completeness work, I should like to mention something that intrigues me about the three formulations of the proof (1929, 1930 and *1930c). In all three Gödel specifies the extra rule of inference (quoted here from page 21 of Volume III): “If a formula A(x) contains the free variable x, then from it the formula (x) A(x) may be inferred”. This looks like saying “from the formula x is prime, it may be inferred that for any x, x is prime”. In the Introduction to The Consistency of the Continuum Hypothesis Gödel says something similar but does not make a rule of inference of it: “ ‘For all x’ is also expressed by free variables in definitions and theorems’.” Frege, at the very beginning of the Begriffschrift, says that variables, as distinct from constants (for which he gives as examples +, - , Ö , 0 , 1 , 2 ), are to be used to express generality, as in (a+b)c = ac + bc. If one makes such a rule for the basic grammar of one’s formal system, one is entitled to apply the above-quoted rule of inference. This would not normally be a useful arrangement: “x is prime” is an example of a formula which Gödel calls erfüllbar --- it can be made to express a true proposition by assigning some values to its variable. And Russell, on page 20 of his introduction to Principia’s Chapter I, has

(3) If we can assert φy, where y is a real [[ie free]] variable, then we can assert (x). φx; ie what holds of any, however chosen, holds of all [[my italics]].

Just why Gödel found the arrangement useful in 1929, 1930 and *1930c I cannot say and would be grateful for illumination.

The problem that now arises for me is how to introduce 1931 itself as a logical enterprise that will result in mathematics being demonstrated to be inexhaustible. In their Introductory note to 1929, 1930 and 1930a, Dreben and van Heijenoort (pages 44 to 59 of Volume I) use the term “semantic completeness” for what Gödel had succeeded in proving in those papers, on the grounds that it has to be meaningful to ask whether a given formula is valid and then, on the assumption that it is, to show that it would be provable if it were; but they use the term “syntactic completeness” for what Bernays had proved of propositional calculus. You will remember that while influenced by the Bernays strategy Gödel had to move outside it to achieve his own completeness proof. Now, in disproving completeness in his 1931, he reverts to the concept of syntactic completeness. Instead of asking whether, in the new field of extended predicate calculus, a formula is provable if it is valid (a semantic requirement, involving all possibilities of value-assignment) he asks whether, taking as it were a given formula out of a hat, and not even asking, let alone knowing, whether it is valid or not, that formula, or alternatively its negation, can be proved. If a formula cannot be proved and its negation cannot be proved either it is said to be undecidable.

Gödel approaches his task from a purely syntactical point of view. A formula, for this question to be asked of it, has to be well-formed, that is to say it has to comply with certain syntactical requirements which deal with grammatical form but not with content. Following Hilbert, the problem of investigating whether a given well-formed formula had been satisfactorily proved according to specified rules of inference going back to ‘primitive’ formulas which were accepted as needing no proof, and by extension the question of whether a formula was at least capable of being proved, was given the status of being metamathematical, for which “proof-theoretical” might be a more readily understood term. Nevertheless, “metamathematical” does express a very important point. In investigating a formula’s proof-theoretical qualities we are asking questions about mathematics, even though we shall inevitably find ourselves applying mathematical techniques in doing so.

In a lecture (*1931?) printed in Volume III (pages 30-31 to 34-35) Gödel uses the phrase “a detour through metamathematics” (“auf dem Umweg über die Metamathematik”) to describe his procedure. (This lecture, which may have been delivered to a meeting of the Vienna Circle on 15.1.31, elsewhere on 15.9.31 and in English at Washington DC on 20.4.34, roughly corresponds, as a summary of 1931, to the Königsberg lecture as a summary of 1929 etc.) In 1931 itself he uses the phrase “for metamathematical considerations” (“für metamathematische Betrachtungen”). I remember this phrase (or at least the idea behind it) from my reading of 1931 in1962, but I over-interpreted its significance. Gödel constructed a formula, which he summarised as [R(q) ; q], which, in its unabbreviated form, is proved by him, by ‘metamathematical considerations’, to be unprovable. By further metamathematical considerations he argues (without claiming proof) that his formula is actually true. Ahead I translate, rather freely, Gödel’s sketch of how he does this, in his prose Section 1. In 1962 I believed that in presenting his argument for the formula’s truth Gödel was rising quite outside mathematics and viewing it from a perspective of intuitive truth.

Now there is no doubt that Gödel did indeed believe in intuitive mathematical truth, and I would not for a moment dispute his right to do so. Ramsey (in the opening pages of his own 1931) has a beautiful argument that settles this once and for all: we can use the mathematical truth that 2+2 = 4 to argue that if it is two miles to the station and two miles on to the Gogs, it is four miles to the Gogs via the station --- and you do not need to know that the Gogs are low hills somewhat more than two miles from Cambridge station to agree with him. Nevertheless, my belief that the concept of intuitive mathematical truth was essential to Gödel’s argument was false. If it had been, an inescapable dilemma would have arisen. For suppose a formal mathematician sets up a formal mathematical system and declares that in that system there is no concept of truth beyond that of provability. Suppose, moreover, entirely plausibly, that this formal system has the richness required for a proposition corresponding to Gödel’s [R(q) ; q] to be constructed in it, and thus allowing Gödel to demonstrate, metamathematically, its unprovability. Then, a further argument that this new [R(q); q] is not only unprovable but intuitively true could simply never get started.

All is not lost, however. Suppose that a metamathematician arrives to argue that in her view (a difference of sex will be useful for clarity here) there is a possibility in between these two extremes. She proposes, like Hilbert, a two-level concept of mathematics and metamathematics. The ground floor, so to speak, will consist of meaningless but easily definable symbols, namely 1, 1+1, 1+1+1 etc, together with other symbols required to construct and control well-formed formulas corresponding to what in informal mathematics we accept as arithmetical assertions. The first floor enables metamathematicians like herself to investigate the proof-theoretical properties of whatever can be achieved by the formal mathematician on his ground floor. Above her there may well be possibilities of constructing further floors from which various kinds of intuitive mathematicians can investigate the intuitive truth of what the metamathematician asserts and, from their vantage points, tell the formal mathematician that whether he likes it or not the formulas which he writes or types can, by them, be interpreted as expressing concepts or making assertions with intuitive meaning --- but to make such claims is not the business of our metamathematician. Her only concern is to argue that the formal mathematician, on his ground floor, and however little he believes in the intuitive meaning of what he is doing, cannot deny the metamathematical justness of her own work in checking his work, or deny the proof-theoretical validity of her claims. He readily admits her right to declare his own version of [R(q); q] unprovable --- indeed he finds her judgement on this point extremely interesting --- but he draws the line at admitting her claim that it is true. No, she says, she is not claiming that it is intuitively true (though the people on the floors above her may claim this), she is only claiming that it is metamathematically true. And since her activities are only a check on his own activities in respect of rules which he himself has propounded, he cannot gainsay her.

In his 1931 Gödel goes one important step further than my imaginary metamathematician. He transforms his findings by use of a numerical code, in such a manner that nearly all of them can be propounded on the ground floor. What was metamathematical thereby becomes mathematical --- indeed, numerical --- and the working takes place unequivocally on the ground floor. The most important exception to this is the argument that the fully written out form of [R(q); q] (or our formalist’s equivalent) is true. This argument has to take place on the metamathematical first floor --- but since this argument is conducted solely by reference to formal rules propounded for ground floor working, the formalist has still no redress.

(A mathematician called Alfred Errera made a formalist claim denying intuitive truth in his 1952 --- see the Volume II References --- and is mentioned by Gödel in footnote 38 to his 1964 on Cantor’s continuum hypothesis. This formalist claim entails complications that are not relevant here, and I discuss them ahead.)

In lectures delivered at Princeton from February to May 1934 (1934 in Volume I), Gödel makes a point at the beginning of Section 4 that makes it clear that he did not regard the metamathematical as being on a level with the intuitive. “For the considerations which follow, the meaning of the symbols is immaterial, and it is desirable that it be forgotten. Notions which relate to the system considered purely formally may be called metamathematical.” This does not mean that metamathematical assessments cannot be given a meaning, and indeed, Gödel himself has been criticised for giving them too much meaning in his prose asides: what needs to be emphasised is that the validity of the 1931 incompleteness theorem in no way depends on such intuitive interpretations.

The problem of Gödel’s culpability in this respect arises from the way he interprets his [R(q); q] in his introductory Section 1 of 1931. Before he introduces that notation he refers to a formula F(v) with one free variable v, which, interpreted according to the meaning of the terms of [[Gödel’s ingenious arithmetical coding for]] PM [[the formal system propounded in Principia Mathematica]] says: v is a provable formula. (To see how a variable can be interpreted as as a formula, let alone one which has itself as argument, you must look up the details of Gödel’s coding, with some help, I hope, from what follows here.) Next, Gödel says that he is going to construct a proposition [[a formula whose free variable has been given a particular value]], referred to as A, such that neither A nor ~-A is provable, which is to say that it is undecidable. This A is then constructed, or rather a sketch is given of how to construct it, under the guise of [R(q); q], whose q is just such a variable that has been given a particular value, with the metamathematical meaning that [R(q); q] itself is not provable. But, under the guise of A, we have already been promised that neither A nor ~-A is provable, and that in the form of [R(q); q] it will be telling the metamathematical truth.

Now in his introductory note, Kleene, on page 128 of Volume I, says that [R(q); q] (in the guise of A) says “I am unprovable (in S)” (namely in PM, the formal system of Principia Mathematica), which is a significant stage more anthropomorphic than what Gödel has been criticised for saying in his Section 1. This anthropomorphic formulation, however, must have been current before the war, because Wittgenstein, in notebooks written in the late thirties, repeatedly attacks it. I cannot believe that, if Wittgenstein had troubled to read the complete 1931, he would have done anything but complain of Gödel’s own misrepresentation of what it achieved; but he seems to have been under the impression that his attacks constituted a criticism of the paper as a whole. To back my suspicions I have a friend’s word for it (McLean-Inglis), who in turn has the word of Kreisel for it, that Wittgenstein never did read anything but Section 1. However, in my newly rediscovered copy of Wittgenstein und der Wiener Kreis, I find (on page 27) that in July 1935 he wrote Schick a long letter about Gödel’s 1931, preserved by Schlick’s daughter. This must surely by now be in the Bergen CD edition, and would settle the question if anyone would kindly look it up for me. In the lecture which Gödel may have delivered to the Vienna Circle (*1931?), and which Wittgenstein could well have heard about, Gödel did not use any formulation of this kind, whether less anthropomorphic or more.

It is well known that Gödel derived part of his strategy for his incompleteness proof from two paradoxes, the classical ‘liar’ paradox of Epaminedes and a less famous one invented by Richard. In the Princeton lectures (1934 in Volume I) Gödel expounds the former paradox as follows. “Suppose that on 4 May 1934, A makes the single statement ‘Every statement which A makes on 4 May 1934 is false’.” In his 1931 he gives more attention to the Richards paradox, which is explained briefly and clearly in Mostowski’s Sentences undecidable in formalised arithmetic, North Holland Publishing Corporation Amsterdam, 1952 (23/6 if you want to time travel to buy it). Avoiding a dogmatic claim that no sentence can meaningfully refer to itself, Gödel then sets out his ingenious but extremely simple arithmetical code, in 1931’s Section 2, of which a serious reader should attempt at least the first four pages, ie up to page 157. (The incompleteness theorem itself, VI, is formulated on page 173 and the proof is completed on page 177, with important observations made in the remainder of the section.)

Having mentioned Gödel’s Theorem VI, his principle statement of incompleteness, I must mention a second theorem propounded in 1931. This, Theorem XI, is stated at the top of page 193 in Section 4, and discussed on that page and the next, but strictly speaking it is not a theorem at all because Gödel does not prove it. He only promises to do so, and as time went on he left its formal proof (based on Turing’s 1937, as Gödel acknowledges in the note added to 1931 and the longer postscript to 1934) to other people. XI states that in any formal system P [[of sufficient richness for the 1931 results to hold --- and P, incidentally, is now PM with Peano’s axioms added]] which is consistent [[implies no contradictions]], a formal assertion that P is in fact consistent will always be unprovable within P’s rules. (If P is not consistent it will fall to pieces, because from a contradiction any proposition is formally provable.)

As to Gödel’s responsibility for other people’s misunderstandings, his own ‘less anthropomorphic’ remark than Kleene’s comes in Section 1, in the penultimate and in the final paragraphs, namely (and respectively): “for the undecidable proposition [R(q);q] states . . . that [R(q);q] is not provable” and “From the remark that [R(q);q] says about itself that it is not provable, it follows at once that it is true, for [R(q);q] is indeed unprovable (being undecidable)”. I shall now try to give a paraphrased translation of the last three paragraphs of Section 1, doing my best to avoid the misleading phraseology. Also, at the very beginning, I avoid a term which I do not believe Gödel used elsewhere. This is “Klassenzeichen” or “class sign”, which derives from Russell’s doctrine that a cardinal number is the class of all classes of that cardinality. Here, a class sign is “a formula of PM with exactly one free variable, that variable being of the type of the natural numbers (class of classes)”, or in brief a numerical predicate. Thus (and excusing myself from inverted commas for three paragraphs):

We assume that the numerical predicates have been arranged in a sequence in some way [[an idea taken from Richard]], we denote the nth by R(n), and we observe that the concept ‘numerical predicate’, as well as the ordering relation R, can be defined in the system PM. Let a be any numerical predicate; by [a ; n] we denote the formula that results from the numerical predicate a when its free variable is replaced by the sign denoting the natural number n. The ternary relation x = [y ; z] is also seen to be definable in PM. We now define a class K of natural numbers in the following way:

n e K ≡ ~ Bew [R(n) ; n] (1)

(where Bew x means: x is a provable formula). Since the concepts that occur in the definiens can all be defined in PM, so can the concept K constructed from them; that is, there is a numerical predicate S such that the formula [S ; n], interpreted according to the terms of PM, states that the natural number n belongs to K. Since S is a numerical predicate, it is identical with some R(q); that is, we have

S = R(q)

for a certain natural number q. We now show that the proposition [R(q);q] is undecidable in PM [[at which point, in a footnote, Gödel points out that “[R(q);q]” is not even shorthand for but is merely a “metamathematical description” of an undecidable proposition which he still has to construct formally]]. For let us suppose that the proposition [R(q);q] were provable, then it would also have to be true. But in that case, according to the definition given above, q would belong to K, that is, by (1), ~Bew [R(q);q] would hold, which contradicts the assumption. If, on the other hand, the negation of [R(q);q] were provable, then ~qeK, that is, Bew [R(q);q] would hold. But then [R(q);q], as well as its negation, would be provable, which again is impossible.

The analogy of this conclusion with the Richard paradox leaps to the eye. It is closely related to the’Liar’ too; for the undecidable proposition [R(q);q] states that q belongs to K, from which it follows, by (1), that [R(q);q] is not provable. We therefore have a proposition whose proof-theoretical interpretation is that no proof exists for it in the [[‘ground floor’]] system PM [[and as a footnote immediately points out, the further linguistic interpretation that no proof of its own meaning exists only arises accidentally out of the details of Gödel’s cunning variable-manipulation]]. The method of proof just explained can clearly be applied to any formal system that, first, when interpreted according to metamathematical content, has at its disposal sufficient means of expression to define the concepts in the train of ideas above, and in which, second, every provable formula is correct in respect of its metamathematical content. [[Note that this has the form ‘if provable it is correct’, not ‘if correct it is provable’.]] The following rigorous execution of the proof [[sketched]] above will aim, among other things, at replacing the second of those requirements [[‘if provable, correct’]] by a purely formal one that is much weaker [[less demanding]].

From the remark that [R(q) ; q] asserts [[in effect]] its own unprovability, it follows at once that [R(q);q] is correct, for [R(q);q] really is unprovable (having been shown already to be neither provable nor disprovable). Thus, the proposition that was undecidable in the system PM has been indeed decided, by metamathematical considerations. The precise analysis of this remarkable circumstance leads to surprising results concerning consistency proofs for formal systems, results that will be discussed in more detail in Section 4 (Theorem XI).

Readers may find the numbering code explained in Section 4 more easy to understand in the Princeton lectures, where Gödel is less sparing with primitive signs. (He adds “&” and “É” to the propositional connectives “~” and “v”, adding the existential quantifier “S” to the general quantifier “P”, and including the identity sign “=” and an epsilon --- not for class membership but for Hilbert’s ‘least number such that ...’ concept. It is important to note that this difference in primitive signs will result in a difference of code-numbers between 1931 and 1934. In particular, as I have pointed out, the q of “[R(q);q]” is not a variable, free or bound, but refers to a particular code-number --- which for 1934 will differ from 1931. In contrast, “[R(q);q]” itself will have no code-number in either 1931 or 1934, since it is abbreviated and cannot qualify for one. (Chaos would result if abbreviated and unabbreviated formulas were to compete for coding.)

At the foot of page 157 in 1931, just where I suggested that amateurs might abandon detail, a convention is introduced that needs to be mentioned. In 1934 Gödel explains his number coding so clearly that he does not need this convention. Nevertheless, 1931 cannot be ignored because in 1934 the essential proof is only sketched, and so the convention used in 1931 needs elucidating. It is immediately visible on the page because it uses small capitals. In his original German Gödel had used italics, emphasis being indicated in standard German by spaced lettering. The capitals of the Princeton edition are used for expressions (some already introduced, some to be defined) referring to metamathematical concepts: but the new expressions in capitals do not denote those concepts, they denote the corresponding code-numbers. One might well say that they express the metamathematical concepts, except that they also express something else, namely the relation between these concepts and their code. Gödel’s own phraseology is misleading here: he says that they denote this relationship. Clearly, they in fact denote, and are intended by Gödel to denote, the code-numbers themselves. An example of this can be seen in definition 17 of 1931, which, using previously defined symbols, defines Z(n) and gives as a prose equivalent “Z(n) is the NUMERAL denoting the number n”. Translating out of capitals, this becomes “Z(n) is the code-number for the numeral denoting the number n”.

The definitions that follow in 1931 correspond fairly closely to those in 1934 to start with. 1931’s 8, 9 and 10 correspond to 1934’s 6 and 7 including a note replacing 9. This becomes important in understanding the respective definitions 10 and 7, which deal with brackets. In both coding systems a left-hand bracket is coded as 12 and a right-hand bracket as 13, and one would have thought that was that, but 1934’s note and 1931’s definition 9 point out that the code-number for a sequence consisting of the single number x is 2 to the x, making the code-number for a left-hand bracket 2 to the 12 and for a right-hand bracket 2 to the 13. The paucity of definitions in 1934 may be partly explained by Gödel’s more extravagant use of primitive symbols, but more significant is his difference in strategies. Having given a formal proof of his Theorem VI in 1931, he can now give only a sketch (which comes in Section 7), and as to his Theorem XI, he still gives only a sketch. This leaves him free to deal with XI first, and he tailors his definitions to that end. 1931’s definition 42 defines Ax(x) and gives it the meaning that x is the code-number of an axiom. So does 1934’s 15, but it deals with the axioms much more simply. Then, the 1934 16 and 17, dealing with proof, correspond to 1931’s 44 and 45, but 46’s definition of Bew(x), enabling it to state that x is the code number of a provable formula, is omitted from 1934, along with the important admission that that definition is the first of 1931’s not to be recursive. Instead, the coding-and-definition Section 4 of 1934 ends with a formal proposition expressing the freedom of the system in question from contradiction.

This formula is repeated towards the end of Section 5, on recursive functions and their coded representation, along with a sketch of how to prove that this contradiction-denying formula cannot be proved formally within its system --- unless the system is indeed contradictory, in which case anything can be proved in it. Theorem XI having thus been sketched, Gödel’s VI is, as I have said, sketched in Section 7, which I have also mentioned as giving Gödel’s translation of the liar paradox. Section 8, finally, deals with Diophantine polynomials as equivalent to undecidable propositions, which, not a general myself, I would classify as caviar to the general (who will be able to find a whole article on the subject, with a most informative introductory note by Davis, in Volume III, coded as *193?). That is followed by the 1964 Postscriptum, which I have mentioned already for its tribute to Turing.

A propos of Turing (and Church, who also played a part in tidying up Gödel’s results) there is on page 342 of Volume I, in Kleene’s Note to 1934, a remark that the work of those two mathematicians “established the undecidability of the first-order predicate calculus”. This does not contradict Gödel’s result of 1929 and 1930 because that was a matter of semantic undecidability, while Turing and Church worked entirely in the realm of the syntactical. Nevertheless, the superficial contradiction is a disturbing one, and I should be grateful if a specialist would explain it away more convincingly than I can.

As an envoi to this first section of my paper, I should like to express my awareness that professional mathematical logicians may not respond to my grammatical and textual approach to Gödel’s work. I am told that modern mathematicians are simply not trained on original texts. Anyone studying Gödel’s Theorems IV and XI at a university will use modern text books which make it plain at each stage which of his moves was mathematical and which metamathematical. This is precisely what I am trying to do here by my comments on the texts, in the hope that non-professionals will thereby find a way into Gödel’s world of ideas, and thence into the world of general mathematics. In my view this is a complex world which deserves to have room for the philosophy, history and grammar of mathematics. Naturally, there are many mathematicians whose abilities do not require such an introduction to their subject, and who would find it the opposite of helpful if anyone tried to draw their attention to the approach. Nevertheless, there must be many potential mathematicians who would quickly realise that they had mathematical talent if they could only be tempted in such a manner as I have sketched. I hope this work of mine (to be concluded in 2001) will help them.