Wittgenstein On Godel

A NOTE ON WITTGENSTEIN’S ‘NOTORIOUS PARAGRAPH’ ABOUT THE GÖDEL THEOREM Juliet Floyd, Boston University Hilary Putnam, Harvard University I imagine someone asking my advice; he says: “I have constructed a proposition (I will use ‘P’ to designate it) in Russell’s symbolism, and by means of certain definitions and transformations it can be so interpreted that it says: ‘P is not provable in Russell’s system.’ Must I not say that this proposition on the one hand is true, and on the other hand is unprovable? For suppose it were false; then it is true that it is provable. And that surely cannot be! And if it is proved, then it is proved that it is not provable. Thus it can only be true, but unprovable.” Just as we ask, “‘Provable’ in what system?,” so we must also ask, “‘True’ in what system?” “True in Russell’s system” means, as was said, proved in Russell’s system, and “false in Russell’s system” means the opposite has been proved in Russell’s system.--Now what does your “suppose it is false” mean? In the Russell sense it means, “suppose the opposite is proved in Russell’s system”; if that is your assumption you will now presumably give up the interpretation that it is unprovable. And by “this interpretation” I understand the translation into this English sentence. --If you assume that the proposition is provable in Russell’s system, that means it is true in the Russell sense, and the interpretation “P is not provable” again has to be given up. If you assume that the proposition is true in the Russell sense, the same thing follows. Further: if the proposition is supposed to be false in some other than the Russell sense, then it does not contradict this for it to be proved in Russell’s system. (What is called “losing” in chess may constitute winning in another game.)1 We believe that this “notorious paragraph”2 contains a philosophical claim of great interest which has been almost entirely missed in the brouhaha about whether Wittgenstein “misunderstood” the Gödel (1st) Incompleteness Theorem. The purpose of this note is to “detach” that claim, so to speak, from that disputed question (although the fact that Wittgenstein’s critics seem to have missed it must surely be relevant to the dispute). The claim is simply this: if one assumes (and, a fortiori if one actually finds out) that ¬P is provable in Russell’s system one should (or, as Wittgenstein actually writes,

one “will now presumably”) give up the “translation” of P by the English sentence “P is not provable”. To see that Wittgenstein is “on to” something here, let us imagine that a proof of ¬P has actually been discovered. Assume, for the time being, that Russell’s system (henceforth “PM”) hasn’t actually turned out to be inconsistent, however. Then, by the 1st Incompleteness Theorem, we know that PM is ω-inconsistent. But what does ωinconsistency show? ω-inconsistency shows that a system has no model in which the predicate we have been interpreting as “x is a natural number” possesses an extension which is isomorphic to the natural numbers. But why did we “translate” P as “P is not provable in PM”? Well, P has the form: ¬(∃x)(NaturalNo.(x).Proof(x,t)), where “t” abbreviates a numerical expression whose value calculates out to be the Gödel number of P itself, “Proof” abbreviates a predicate which is supposed to define an effectively calculable relation which holds between two natural numbers n,m just in case n is the Gödel number of a proof whose last line is the formula with Gödel number m, and “NaturalNo.(x)” is the predicate of PM we interpret as “x is a natural number”. But in discovering that PM is ω-inconsistent we have discovered that: 1

“NaturalNo.(x)” cannot be so interpreted. In all admissible interpretations of PM (all interpretations which fit at least one model of PM), there are entities which are not natural numbers (and, a fortiori, not Gödel numbers of proofs).

2

Those predicates of PM (e.g., “Proof(x,t)”) whose extensions are provably infinite, and which we believed to be infinite subsets of N (the set of all natural numbers), do not have such extensions in any model. Instead, they have extensions which invariably also contain elements which are not natural numbers. 2

In short, the “translation” of P as “P is not provable in PM” is untenable in this case – just as Wittgenstein asserted! This does not, however, affect the correctness of Gödel’s proof, for nothing in that proof turns on any such translation into ordinary prose.3 Wittgenstein’s aim is not to refute the Gödel theorem but to “by-pass” it.4 In addition, we may point out that if PM is actually inconsistent, and not merely ω-inconsistent, then it has no “admissible interpretations” – which is not to deny that in various contexts, and for various reasons, we may want to correlate its sentences with sentences in English.

But surely Wittgenstein couldn’t have known about that stuff! But is it believable that Wittgenstein could have known about the “numerical insegregativity”5 of ω-inconsistent systems? Are we not being overly charitable in giving this as Wittgenstein’s reason for saying that if one assumes that ¬P is provable in Russell’s system, one “will now presumably give up the interpretation” of P by the English sentence “P is unprovable”? The answer is that we have testimony (and not from a particularly sympathetic source!) that Wittgenstein thought about what are now called nonstandard models of the natural numbers, and connected them with the Gödel theorem. In 1957 R.L. Goodstein wrote, Wittgenstein with remarkable insight said in the early thirties that Gödel’s results showed that the notion of a finite cardinal could not be expressed in an axiomatic system and that formal number variables must necessarily take values 3

other than natural numbers; a view which, following Skolem’s 1934 publication, of which Wittgenstein was unaware, is now generally accepted.6 And in 1972 Goodstein wrote, I do not think Wittgenstein heard of Gödel’s discovery before 1935; on hearing about it his immediate reaction, with I think truly remarkable insight, was to observe that it showed that the formalization of arithmetic with mathematical induction and the substitution of numerals for variables fails to capture the concept of natural number, and the variables must admit values which are not natural numbers. For if, in a system A, all the sentences G(n) with n a natural number are provable, but the universal sentence (∀n)G(n) is not, then there must be an interpretation of A in which n takes values other than natural numbers for which G(n) is not true (in fact in 1934, Th. Skolem had shown that this was the case, independently of Gödel’s work).7 Interestingly, Goodstein entirely missed the connection between this “remarkable insight” and the claim we are discussing--which may not only been taken to be contained in Appendix I, §8 of RFM, but also as constituting virtually the whole of §10 of the same Appendix! 8 But, as is well known, the remarks on Gödel’s theorem were written as notes for Wittgenstein himself, and there was no reason for their author to state explicitly everything that he knew in connection with them. The fact is, that Wittgenstein did understand – “with remarkable insight” – that “variables must necessarily take on values other than the natural numbers.” (Indeed, this must be the case whether PM is ωinconsistent or not; the point about ω-inconsistency is that if PM is ω-inconsistent, then there is no interpretation under which PM’s theorems come out true in which the formal number variables take only only the natural numbers as values.) We know this not only from Goodstein, but also from remarks made by Wittgenstein’s student Alister Watson in a 1938 paper in Mind.9 Watson explicitly states that his interpretation of the Gödel incompleteness result “owes much to lengthy discussions with a number of people, especially Mr. Turing and Dr. Wittgenstein”. He then forwards an argument very similar 4

to the one we sketched above about the effect of ω-inconsistency on the power of any recursively axiomatized system of arithmetic to fully express the notion of natural number. He does this, he says, in order to show that the intuitive argument about the true but unprovable proposition P “obscures rather than illuminates the point” of Gödel’s theorem.10 This, as we have just argued, was Wittgenstein’s point as well in the “notorious” paragraph.

But even so….. Even though, as we explained, the purpose of this note is to examine the valuable and still relatively unappreciated point that Wittgenstein makes in §8 (and also in §10) of Appendix I of RFM -- i.e., that the “translation” of the famous Gödel sentence P as “P is unprovable in PM” is not cast in stone, but is something that we have to give up in certain contexts -- rather than to discuss in detail the dispute(s) about whether Wittgenstein (1) “understood” the Gödel theorem, and (2) whether his philosophical remarks about it have any value, we would be remiss if we did not at least comment on the question of the bearing of the unappreciated point on at least the second of those disputes. (The reader who has followed us this far should have no doubts about whether Wittgenstein understood the Gödel theorem, and hence about the position to take with respect to the first dispute!) The principle source of the question as to the cogency of Wittgenstein’s discussion are the words in the notorious §8, “’True in Russell’s system’ means, as was said: proved in Russell’s system, and ‘false in Russell’s system’ means: the opposite has been proved in Russell’s system” (emphasis added). Isn’t Wittgenstein aware that 5

arithmetical propositions have a meaning and truth value independent of what system they are formalized in? Is he just identifying “truth” and “provability” out of some misguided combination of formalist and constructivist/finitist motives? Etc., etc….. The answer is that one cannot simply ignore the direction (implicit in the words we italicized) to look at what was said before about “true in Russell’s system”. Just one paragraph before (§7), there appear the remarks which clearly set the stage for the notorious remark: 7. But may there not be true propositions which are written in this symbolism, but are not provable in Russell's system?" -- 'True propositions', hence propositions which are true in another system, i.e. can rightly be asserted in another game. Certainly; why should there not be such propositions; or rather: why should not propositions -- of physics, e.g. -- be written in Russell's symbolism? The question is quite analogous to: Can there be true propositions in the language of Euclid, which are not provable in his system, but are true? -Why, there are even propositions which are provable in Euclid's system, but are false in another system. May not triangles be -- in another system -- similar (very similar) which do not have equal angles? -- "But that's just a joke! For in that case they are not 'similar' to one another in the same sense!" -- Of course not; and a proposition which cannot be proved in Russell's system is "true" or "false" in a different sense from a proposition of Principia Mathematica.11 If one reads this paragraph with care, one will observe two things: first, that Wittgenstein is telling us that we should look on PM as a “system” in the sense in which a system of non-Euclidean geometry is a “system” of geometry – a sense in which the same sentence (Satz) can be true in one system and false in another. And second, that this paragraph does not deny that a proposition which cannot be proved in Russell’s system (Wittgenstein obviously means one which cannot be decided, i.e., proved or disproved) can, in some sense be “true” or “false” (outside the system) – he only asserts that this is a “different sense” from the sense in which it is true or false as a “proposition of Principia Mathematica.” We will now comment on each of these points in turn. 6

(1) Wittgenstein’s targets in much of Part I of RFM are Frege and Russell, not as mathematical logicians but as philosophers of mathematics and logic. These philosophers emphatically did not see themselves as providing a mere notation into which one could transcribe the propositions that mathematicians actually utter, write, and publish in ordinary “mathematical prose”, i.e., in English or French or German or….. They saw themselves as providing a freestanding “ideal language” or “concept-language”, what Quine has called a “first grade conceptual scheme”, which in some sense supercedes ordinary language. Moreover, in providing such a scheme they saw themselves as providing mathematics with a foundation. Ordinary language might be necessary to “lead someone into” the ideal language, but the “elucidations” we offer for this purpose in ordinary language are, so to speak, a ladder that we can throw away.12 Frege explicitly argues that ordinary language sentences that we use to explain the ideal notation do not and cannot capture the precise content of the ideal notion.13 It would be utterly foreign to this spirit to explain the truth of a formula of Principia Mathematica by merely writing down an English sentence, and saying this is what it means for P to be true. To confess that this is what one has to do would be to abandon the claim for the foundational status of a system such as Principia Mathematica entirely. (So that when Wittgenstein writes in §8: “And by ‘this interpretation’ I understand the translation into this English sentence,” he is already denying that this notion of an “interpretation” which can only be indicated in English by helpful “hints”14 and which does not in principle require any dependence on informal mathematical language, makes any real sense.) Instead, Wittgenstein is suggesting, there is a sense in which a formalism can be free-standing, but it is not the sense of a Begriffschrift or an ideal language. It can be 7

free-standing regarded simply as a formal system. But then the only sense of “truth” we will have available is: being a theorem of the system.15 And in that case, why shouldn’t it be the case that one and the same “proposition” should be “true in Russell’s system” and false in a different system? Indeed, something of this kind does happen. If there are only finitely many individuals, then for some natural number x, x=Sx (imagine this written out in the formal notation) is a theorem of Principia Mathematica, while There are only finitely many individuals and for every natural number x, x≠Sx (imagine this likewise written out in formal notation) is a consistent proposition (model theoretically as well as prooftheoretically) in Zermelo set theory. Or to change the example, the formula (∃x)(x∈x) (“some set belongs to itself”) is “true in Quine’s system” (Mathematical Logic) and “false in Zermelo’s system”! Today, of course, few if any philosophers think that a formal system provides a foundation for either the content or the truth of mathematical propositions. But one of us [HP] remembers a delightful philosophical conversation between C.G. Hempel and one of Reichenbach’s graduate students in Reichenbach’s living room in 1950 at which the older attitude and the newer attitude memorably clashed. Hempel was defending Quine’s skepticism with respect to the analytic-synthetic distinction, and the graduate student said plaintively, “Quine’s arguments may show that the analytic-synthetic distinction makes no sense in natural language. But why doesn’t it make clear sense in a formalized language?”, and Hempel replied, “Every formalized language is ultimately explained in some natural language. The disease [Hempel meant the unclarity of the analytic-synthetic distinction] is hereditary.” Here Hempel – like Wittgenstein in RFM – was denying that 8

a formal system could provide us with a standard of truth or clarity that is in principle inaccessible to a natural language. (2) What if someone were to have said to Wittgenstein, “When I say that P is true in Russell’s system, what I mean is simply that its translation into English – any one of its mathematically equivalent translations, including ‘P is unprovable in PM’ – is true?” We believe that Wittgenstein would have pointed out that the notion of truth is eliminable here.16 To understand “P is true in PM” as meaning “The English sentence ‘P is unprovable in PM’ is true” (or more colloquially, as meaning “It is true that P is unprovable in PM”), would amount (as we see by “disquoting”) just to understanding “P is true in PM” as short for “P is unprovable in PM”, or understanding P itself (in PM) as short for “P is unprovable in PM”. In short this just is to accept what Wittgenstein calls “the translation into this English sentence.” And this is something, we have shown, Wittgenstein did discuss in the notorious paragraph – “with remarkable insight”. That the Gödel theorem shows that (1) there is a well defined notion of “mathematical truth” applicable to every formula of PM; and (2) that if PM is consistent, then some “mathematical truths” in that sense are undecidable in PM, is not a mathematical result but a metaphysical claim. But that if P is provable in PM then PM is inconsistent and if ¬P is provable in PM then PM is ω-inconsistent is precisely the mathematical claim that Gödel proved. What Wittgenstein is criticizing is the philosophical naiveté involved in confusing the two, or thinking that the former follows from the latter. But not because Wittgenstein want to simply deny the metaphysical claim; rather he wants us to see how little sense we have succeeded in giving it.

9

1

Ludwig Wittgenstein, Remarks on the Foundations of Mathematics (revised edition,

Cambridge, MA: MIT Press, 1978), hereafter “RFM”, I Appendix III §8. 2

So-called by Juliet Floyd in her “Prose versus Proof: Wittgenstein on Gödel, Tarski and

Truth”, forthcoming, Philosophia Mathematica. Floyd gives a detailed reading of this notorious paragraph in her earlier “On Saying What You Really Want to Say: Wittgenstein, Gödel and the Trisection of the Angle”, in Jaakko Hintikka, ed., From Dedekind to Gödel: Essays on the Development of the Foundations of Mathematics (Dordrecht, Kluwer Academic Publishers, 1995), pp. 373-425. 3

In introductory remarks to his 1931 paper Gödel did sketch an argument using intuitive

versions of the notions of truth and proof. But he was quite explicit that this heuristic sketch plays no essential role in the proof he gives with “full precision” in the body of the paper. See "On formally undecidable propositions of Principia mathematica and related systems I" (Kurt Gödel: Collected Works Volume I, eds. S. Feferman, et.al. (New York: Oxford University Press, 1986), pp. 147-151, especially p. 147 n. 6, p. 151 paragraph 2, p. 173 n. 41. 4

See RFM VII §19: “My task is, not to talk about (e.g.) Gödel’s proof, but to by-pass it.”

5

A term introduced by Quine to refer to the model-theoretic fact that ω-inconsistent

systems have no model in which the “integers” of the model are (isomorphic to) the natural numbers. See his “On ω-inconsistency and the so-called axiom of infinity”, in Selected Logic Papers (enlarged edition, Cambridge, MA, Harvard University Press, 10

1995) pp. 114-120; compare Set Theory and Its Logic (revised ed., Cambridge, MA, Harvard University Press, 1969), pp. 305-306. 6

R.L. Goodstein, "Critical Notice of Remarks on the Foundations of Mathematics", Mind

1957: 549-553; see p. 551. 7

R.L. Goodstein, “Wittgenstein’s Philosophy of Mathematics”, in A. Ambrose and M.

Lazerowitz (eds.), Ludwig Wittgenstein: Philosophy and Language (London: Allen & Unwin, 1972), pp. 271-286, esp. p. 279. 8

RFM I App. III §10: “But surely P cannot be provable, for, supposing it were proved, then the proposition that it is not provable would be proved.” But if this were now proved, or if I believed -- perhaps through an error -- that I had proved it, why should I not let the proof stand and say I must withdraw my interpretation “unprovable”?

Compare Goodstein’s dismissal of Wittgenstein’s RFM remarks on Gödel, "Critical Notice of Remarks on the Foundations of Mathematics", p. 551, “Wittgenstein’s Philosophy of Mathematics”, p. 279. 9

Alister Watson, “Mathematics and Its Foundations”, Mind 47 (1938), pp. 440-451.

Thanks to Judson Webb for calling our attention to this important paper. According to Andrew Hodges, Turing’s biographer, discussions were held between Watson, Turing and Wittgenstein in the summer of 1937, when Turing returned for a season to Cambridge between his years at Princeton (Alan Turing: The Enigma, New York: Touchstone, 1983, pp. 109, 136). The “notorious” paragraph RFM I Appendix III §8 was penned on 23 September 1937, when Wittgenstein was in Norway (see the Wittgenstein 11

papers, CD Rom, Oxford University Press and the University of Bergen, 1998, Item 118 (Band XIV), pp. 106ff). According to G.H. von Wright, in correspondence with JF, Wittgenstein praised Watson’s paper very highly on more than one occasion--something Wittgenstein did not very often do with colleagues’ work. 10

Watson, “Mathematics and Its Foundations”, pp. 446-447: If we assume for the moment that this axiomatic system is indeed a good basis for arithmetic, we shall have to conclude that the formula is not provable, and therefore, since this is just what it says, that it is true, For if it were provable, it would be false, and the system would be incorrect. This method of putting the argument, however, obscures rather than illuminates the point. Suppose we assume the falsity of the formula, we cannot, of course, derive a contradiction, for this would amount to a proof of the formula. Instead, we reach the following peculiar situation, which is called by Gödel an ωcontradiction (ω is the “ordinal number” of a sequence). We find that there is a function of a cardinal variable, say f(n), such that (all on the basis of the falsehood of Gödel’s formula) (n)f(n) can be disproved, and yet we can convince ourselves that we can prove in turn f(0),f(1),f(2) and so on. In other words, we apply mathematical induction to the proofs of the system, and obtain f(0), and from a proof of f(n) for any particular value of n, a proof for n+1. Why should we object to an ω-contradiction? Why should we not still say that Gödel’s formula may be false? The answer is that if we do this we shall feel 12

compelled to say that the cardinal numbers cannot be all the values of the variable n, if f(n) can be true for each particular value of n, and yet (n)f(n) be false... Thus the notion of a cardinal variable, i.e. of a number in the everyday sense, is something that cannot be completely expressed in the axiomatic system.. We note that although Watson is right that if we assume the falsity of Gödel’s formula i.e., if we assume “(∃x)(NaturalNo.(x).Proof(x,t))” then (n)f(n) can be disproved (taking “f(n)” to be ¬(NaturalNo.(n).Proof(n,t))”) and yet “we can prove in turn f(0),f(1),f(2) and so on”, the usual proof of this ω-inconsistency does not proceed by “applying mathematical induction to the proofs of the system”. Rather, one employs the fact that if PM is inconsistent that it is (trivially) ω-inconsistent, and if it is consistent, then by the already proven facts that (i) PM would be inconsistent if any natural number n were the Gödel number of a proof of the formula with Gödel number t “, and (ii) “Proof(n,t))” represents the recursive relation “n is a proof of the formula with Gödel number t” and “NaturalNo.(0)”, “NaturalNo.(1)”, “NaturalNo.(2)”….. are all (trivially) provable, it follows that for each numeral n, “¬ (NaturalNo.(n).Proof(n,t)” is provable in PM, i.e., that there are proofs of f(0), f(1),f(2)….. We see no way to use mathematical induction in the way Watson suggests. However this error is irrelevant to the point Watson was making. 11

RFM I App. III §7.

12

Wittgenstein invoked Frege’s term “elucidation” (Erläuterung) in the final lines of the

Tractatus, where the image of the ladder appears. In “Logic in 13

Mathematics”(Posthumous Writings, eds. H. Hermes et.al., trans. P. Long, R. White (University of Chicago Press, 1979), p. 207) Frege had written: Definitions proper must be distinguished from illustrative examples (Erläuterungen). In the first stages of any discipline we cannot avoid the use of ordinary words. But these words are, for the most part, not really appropriate for scientific purposes, because they are not precise enough and fluctuate in their use. Science needs technical terms that have precise and fixed meanings, and in order to come to an understanding about these meanings and exclude possible misunderstandings, we give Erläuterungen illustrating their use. Of course in so doing we have again to use ordinary words, and these may display defects similar to those which the examples are intended to remove. 13

This goes not only for what Frege takes to be his primitive or undefinable notions (e.g.,

function, concept), but also for ordinary language notions replaced in the language of Begriffsschrift. See Frege, Collected Papers on Mathematics, Logic, and Philosophy (ed. B. McGuinness, trans. M. Black et.al., Blackwell, 1984), pp. 193-4, 300, 302; Posthumous Writings pp. 207, 214, 235; Grundgesetze der Arithmetik I (Hildesheim, Georg Olms, 1966) Appendix 2, n. 1 (p. 240). 14

Compare Frege, “On Concept and Object”, Collected Papers p. 194.

15

After the appearance of semantics with Tarski, one can add another sense: holding in

all models of the system. If we take this to mean all Henkin models, then even in the case of a higher-order language like PM, this will coincide with being a theorem. However, it is a further question whether Tarski’s model-theoretical account of truth-definitions for 14

formalized languages exhibits a correct analysis of our intuitive notion of truth. On this point, see Floyd, “Prose versus Proof: Wittgenstein on Gödel, Tarski and Truth”, op.cit, where Floyd argues against Mark Steiner’s charge (in “Wittgenstein As His Own Worst Enemy: The Case of Gödel’s Theorem”, forthcoming, Philosophia Mathematica) that the “notorious” section 8 constitutes an unwitting (and unsuccessful) attempt on Wittgenstein’s part to rule out a Tarski-style semantical proof of Gödel’s theorem. So far as we know, Wittgenstein never mentioned Tarski’s work on truth definitions. See also H. Putnam, “A Comparison of Something with Something Else” in his Words and Life (Cambidge, MA: Harvard University Press, 1994), on the claim that Tarski analyzed the concept of truth. 16

Cf. H. Putnam, Lecture III in Part I (The Dewey Lectures) of his The Threefold Cord:

Mind, Body and World, for a discussion of the senses in which Wittgenstein was and wasn’t a “disquotationalist”.

15