不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

哥德尔不完全性定理的接纳过程(原文) - John W. Dawson Jr.

已有 625 次阅读 2022-11-14 05:23 |个人分类:解读哥德尔不完全性定理|系统分类:科研笔记

The Reception of Gödel’s Incompleteness Theorems

John W.Dawson, Jr. 


Die Arbeit über formal unentscheidbare Sätze wurde wie ein Erdbeben empfunden; insbesondere auch von Carnap (Popper, 1980). Kurt Gödel’s achievement in modern logic…is a landmark which will remain visible far in space and time (John von Neumann).1 It is natural to invoke geological metaphors to describe the impact and the lasting significance of Gödel’s incompleteness theorems. Indeed, how better to convey the impact of those results—whose effect on Hilbert’s Programme was so devastating and whose philosophical reverberations have yet to subside—than to speak of tremors and shock waves? The image of shaken foundations is irresistible. Yet to adopt such seismic imagery is to suggest that the aftermath of intellectual upheaval is comparable to that of geological cataclysm: a period of slow rebuilding, preceded initially by widespread confusion and despair, or perhaps determined resistance; and though we might expect Gödel’s discoveries to have provoked just such reactions, according to most commentators they did not. Thus van Heijenoort states ‘although [Gödel’s paper] caused some momentary surprise, its results were soon widely accepted’ (van Heijenoort, 1967, p. 594). Similarly, Kreisel has averred that ‘expected objections never materialized’ (Kreisel, 1979, p. 13), and Kleene, speaking of the second incompleteness theorem (whose proof was only sketched in Gödel’s (1931)), has even claimed ‘it seems no one doubted it’ (Kleene 1976, p. 767).

found discoveries in the history of logic and mathematics was assimilated promptly and almost without objection by Gödel’s contemporaries—a circumstance so remarkable that it demands to be accounted for. The received explanation seems to be that Gödel, sensitive to the philosophical climate of opinion and anticipating objections to his work, presented his results with such clarity and rigour as to render them incontestable, even at a time of fervid debate among competing mathematical philosophies. The sheer force of Gödel’s logic, as it were, swept away opposition so effectively that Gödel abandoned his stated intention of publishing a detailed proof of the second theorem (1931, p. 198). On the last point there can be no dispute, as Gödel stated explicitly to van Heijenoort that ‘the prompt acceptance of his results was one of the reasons that made him change his plan’ (van Heijenoort, 1967, footnote 68a, p. 616). 


We may question, however, to what extent Gödel’s subjective impression reflected objective circumstances. We must also recognize the hazard in assessing the cogency of Gödel’s arguments from our own perspective. To be sure, the exposition in (Gödel, 1931) now seems clear and compelling; the proofs strike us as detailed but not intricate. But did it seem so at the time? After all, arithmetization of syntax was then a novel device, and logicians were not then so accustomed to the necessity for making precise distinctions between object- and metalanguage. Indeed, J. Barkley Rosser (who himself contributed to the improvement of Gödel’s results) has observed that only after Gödel’s paper appeared did logicians realize how careful they had to be (cf. Grattan-Guinness, 1981, footnote 3, p. 499); precisely because of Gödel’s results we no longer share the formalists’ naive optimism, and so we are likely to be more receptive to Gödel’s ideas. Our faith in the efficacy of logic as a tool for overcoming intellectual resistance should also be tempered by consideration of the reception accorded other ‘paradoxical’ results. For example, the Löwenheim Skolem theorem, first enunciated by Löwenheim in 1915 and established with greater precision and broader generality by Skolem in a series of papers from 1920 to 1929, is certainly less profound than Gödel’s discovery (with which, however, it is still sometimes confused)—yet it generated widespread misunderstanding and bewilderment, even as late as December 1938. (See, in particular, the discussion in Gonseth, 1941, pp. 47–52.) 


In what follows, I shall examine the reaction to Gödel’s theorems in some detail, with the aim of showing that there were doubters and critics, as well as defenders and rival claimants to priority. (Of course, there were also some who accepted Gödel’s results without fully understanding them.)1. 1930: KÖNIGSBERG宣布 


Elsewhere (Dawson, 1984) I have described in detail the circumstances surrounding Gödel’s first public announcement of his incompleteness discovery. In summary, the event occurred during a discussion on the foundations of mathematics that took place in Königsberg, 7 September 1930, as one of the final sessions of the Second Conference on Epistemology of the Exact Sciences organized by the Gesellschaft für empirische Philosophic. At the time, Gödel was virtually unknown outside Vienna; he had come to the conference to deliver a twenty minute talk on the results of his dissertation, completed the year before and just then about to appear in print. In that work, Gödel had established a result of prime importance for the advancement of Hilbert’s programme: the completeness of first-order logic (or, as it was then called, the restricted functional calculus); so it could hardly have been expected that the day after his talk Gödel would suddenly undermine that programme by asserting the existence of formally undecidable propositions. As Quine has remarked, ‘[although] completeness was expected, an actual proof of completeness was less expected, and a notable accomplishment. It came as a welcome reassurance…. On the other hand the incompletability of elementary number theory came as an upset of firm preconceptions’ (Quine, 1978, p. 81).


To judge from the (edited) transcript of the discussion published in Erkenntnis (Hahn et al., 1931), none of the other participants at Königsberg had the slightest inkling of what Gödel was about to say, and the announcement itself was so casual that one suspects that some of them may not have realized just what he did say. In particular, the transcript gives no indication of any discussion of Gödel’s remarks, and there is no mention of Gödel at all in Reichenbach’s post-conference survey of the meeting (published in Die Naturwissenschaften 18:1093–4). Yet two, at least, among those present should have had foreknowledge of Gödel’s results: Hans Hahn and Rudolf Carnap. Hahn had been Gödel’s dissertation adviser. He chaired the discussion at Königsberg, and it was presumably he who invited Gödel to take part. Of course, Gödel may not have confided his new discovery to him—indeed, Wang has stated that ‘Gödel completed his dissertation before showing it to Hahn’ (Wang, 1981, footnote 2, p. 654)—but in introductory remarks to the dissertation that were deleted from the published version (at whose behest we do not know), Gödel had explicitly raised the possibility of incompleteness (without claiming to have demonstrated it). Perhaps Hahn just didn’t take the possibility seriously


In any case, Gödel did confide his discovery to Carnap prior to the discussion at Königsberg, as we know from Aufzeichnungen in Carnap’s Nachlass. Specifically, on 26 August 1930, Gödel met Carnap, Feigl, and Waismann at the Cafe Reichsrat in Vienna, where they discussed their travel plans to Königsberg. Afterward, according to Carnap’s entry for that date, the discussion turned to ‘Gödels Entdeckung:


Unvollständigkeit des Systems der PM; Schwierigkeit des Widerspruchsfreiheitbeweises’. Three days later another meeting took place at the same cafe. On that occasion, Carnap noted ‘Zuerst [before the arrival of Feigl and Waismann] erzählt mir Gödel von seiner Entdeckungen.’ Why then at Königsberg did Carnap persist in advocating consistency as a criterion of adequacy for formal theories?


That he might have done so just to provide an opening for Gödel seems hardly credible. It seems much more likely that he simply failed to understand Gödel’s ideas. (As it happens, a subsequent note by Carnap dated 7 February 1931, after the appearance of Gödel’s paper, provides confirmation: ‘Gödel hier. über seine Arbeit, ich sage, dass sie doch schwer verständlich ist.’) Later, of course, Carnap was among those who helped publicise Gödel’s work; but Popper’s remark quoted at the head of this article seems to be an accurate characterisation of Carnap’s initial reaction.


One of the discussion participants who did immediately appreciate the significance of Gödel’s remarks was John von Neumann: after the session he drew Gödel aside and pressed him for further details. Soon thereafter he returned to Berlin, and on 20 November he wrote Gödel to announce his discovery of a remarkable [bemerkenswert] corollary to Gödel’s results: the unprovability of consistency. In the meantime, however, Gödel had himself discovered his second theorem and had incorporated it into the text of his paper; the finished article was received by the editors of Monatshefte November 17.3


2. 1931: PUBLICATION AND CONFRONTATION 


In January 1931 Gödel’s paper was published. But even before then, word of its contents had begun to spread. So, for example, on 24 December 1930, Paul Bernays wrote Gödel to request a copy of the galleys of (1931), which Courant and Schur had told him contained ‘bedeutsamen und überraschenden Ergebnissen’. Gödel responded immediately, and on 18 January 1931, Bernays acknowledged his receipt of the galleys in a 16-page letter in which he described Gödel’s results as ‘ein erheblicher Schritt vorwärts in der Erforschung der Grundlagenprobleme’.


The Gödel-Bernays correspondence is of special interest (in the absence of more direct evidence) for the light it sheds on Hilbert’s reaction. In the same letter of 18 January, Bernays discussed Hilbert’s ‘recent extension of the usual domain of number theory’—his introduction of the ω-rule—and von Neumann’s belief that every Unitary method of proof could be formalized in Gödel’s system P.Bernays himself saw Gödel’s theorem as establishing a disjunction: either von Neumann was right, and no finitary consistency proof was possible for the systems Gödel considered, or else some finitary means of proof were not formalizable in P—a possibility Gödel had expressly noted in his paper. In any case, Bernays felt, one was impelled [hingedrängt] to weaken Gödel’s assumption that the class of axioms and the rules of inference be (primitively) recursively definable. He suggested that the system obtained by adjoining the ω-rule would escape incompleteness yet might be proved consistent by finitary means. But (according to Carnap’s Aufzeichnung of 21 May 1931) Gödel felt that Hilbert’s programme would be compromised by acceptance of the ω-rule.


Somewhat later Gödel sent Bernays an offprint of the incompleteness paper, enclosing a copy for Hilbert as well. In his acknowledgement of 20 April, Bernays confessed his inability to see why a truth predicate could not be formally defined in number theory—he went so far as to propose a candidate for such a definition—and why Ackermann’s consistency proof (which he had accepted as correct) could not be formalized there as well. By 3 May, when he wrote Gödel once more, Bernays had recognised his errors, but the correspondence remains of interest, not only because it exposes Bernays’ difficulties in assimilating the consequences of Gödel’s theorems, but because it furnishes independent evidence of Gödel’s awareness of the formal undefinability of the notion of truth—a fact nowhere mentioned in (1931).


Gödel’s formal methods, as employed in the body of (1931), thus seem to have served their purpose in securing the acceptance of his results by three of the leading formalists. But at the same time, even among those who appreciated the value of formalization, Gödel’s precise specification of the system P raised doubts as to the generality of his conclusions.6 On the other hand, those opposed to formal systems could point to Gödel’s results as reason for dismissing such systems altogether.


Partly to obviate such objections, Gödel soon extended his results to a wider class of systems (in (1930/31) and (1934)), and in the introduction to (1931) he also gave informal proofs of his results based on the soundness of the underlying axiom systems rather than on their formal consistency properties. Undoubtedly, he hoped this informal précis would help his readers to cope with the formal detail to follow; but all too many read no further. Ironically, because of the misinterpretations it subsequently spawned, the introduction to (1931) has been called that paper’s ‘one ‘‘mistake”’ (Helmer, 1937). During 1931, Gödel spoke on his incompleteness results on at least three occasions: at a meeting of the Schlick circle (15 January), in Karl Menger’s mathematics colloquium (22 January), and, most importantly, at the annual meeting of the Deutsche Mathematiker-Vereinigung in Bad Elster (15 September), where, in Ernst Zermelo, he encountered one of his harshest critics.


At issue between the two men were profound differences in philosophy and methodology. In his own talk at Bad Elster (abstracted in Zermelo, 1932), Zermelo lashed .out against ‘Skolemism, the doctrine that every mathematical theory, even set theory, is realizable in a countable model’—a doctrine that Zermelo regarded as an embodiment of Richard’s antinomy


For Zermelo, quantifiers were infinitely conjunctions or disjunctions of unrestricted cardinality; and since the truth values of compound statements were therefore determined by transfinite induction on the basis of the truth values assigned to the Grundrelationen, Zermelo argued that this determination itself constituted the proof or refutation of each proposition. There were no ‘undecidable’ propositions, simply because Zermelo’s infinitary logic had no syntactic component. Consequently, Zermelo dismissed Gödel’s ‘attempt’ to exhibit undecidable propositions, saying that Gödel ‘applied the “finitistic” restriction only to the “provable” statements’ of his system, ‘not to all statements belonging to it’,7 so that Gödel’s result, like the LöwenheimSkolem theorem, depended on (unwarranted) cardinality restrictions. It said nothing about the existence of ‘absolutely unsolvable problems in mathematics’.



In his published remarks, Zermelo did not fault the correctness of Gödel’s argument; he merely took it as evidence of the untenability of the “finitistic” restriction’. But on 21 September, immediately following the conference, Zermelo wrote privately to Gödel to inform him of ‘an essential gap’ [eine wesentliche Lücke] in his argument. (See Dawson (1985) for the full text of this letter.) Indeed, Zermelo argued, simply by omitting the proof predicate from Gödel’s construction one would obtain a formal sentence asserting its own falsity, yielding thereby ‘a contradiction analogous to Russel[l]’s antinomy’. Zermelo’s letter prompted a further exchange of letters between the two men (published in Grattan-Guinness (1979)), with Gödel patiently explaining the workings of his proof, pointing out the impossibility of defining truth combinatorially within his system, and emphasising that the introductory pages of his paper (to which Zermelo had referred) did not pretend to precision, as did the detailed considerations later on. In reply, Zermelo thanked Gödel for his letter, from which, he said, he had gained a better understanding of what Gödel meant to say; but in his published report he still failed utterly to appreciate Gödel’s distinctions between syntax and semantics.


3. RECOGNITION, AND CHALLENGES TO PRIORITY 


Despite (or perhaps because of) Zermelo’s reputation as a polemicist, his crusade against ‘Skolemism’ won few adherents, and his criticisms of Gödel’s work seem to have been disregarded. In the spring of 1932 Karl Menger became the first to expound the incompleteness theorem to a popular audience, in his lecture Die neue Logik (published by Franz Deuticke in 1933 as one of ‘fünf Wiener Vorträge’ in the booklet Krise und Neuaufbau in den exakten Wissenschaften; see Menger (1978) for an English translation). The following June Gödel submitted (1931) to the University of Vienna as his Habilitationsschrift, and in January 1933 he accepted an invitation to spend the academic year 1933–34 at the newly established Institute for Advanced Study in Princeton


On 11 March 1933, Gödel’s Dozentur was granted. That same day Paul Finsler in Zürich addressed a letter to Gödel requesting a copy of (1931). He was interested in Gödel’s work, he said, because it seemed to be closely related to earlier work of his own (Finsler, 1926). He had already glanced fleetingly at Gödel’s paper, and he acknowledged that Gödel had employed ‘a narrower and therefore sharper formalism’. It was ‘of course of value’, he conceded, ‘actually to carry out [such] ideas in a specific formalism’, but he had refrained from doing so because he felt that he had already established the result in a way that ‘went further in its application to Hilbert’s programme’. 


Gödel recognised the challenge for what it was, and in his reply of March 25 he characterised Finsler’s system as ‘not really defined at all’ [überhaupt nicht definiert], declaring that Finsler’s ideas could not be carried out in a genuinely formal system, since the antidiagonal sequence defined by Finsler (on which his undecidable proposition was based) would never be representable within that same system. Finsler retorted angrily that it was not necessary for a system to be ‘sharply’ defined in order to make statements about it; it was enough that ‘one be able to accept it as given and to recognize a few of its properties’. He could, he said, ‘with greater justice’ object to Gödel’s proof on the grounds that Gödel had not shown the Peano axioms that he employed to be consistent (Gödel’s second theorem notwithstanding!). He saw that the truth of Gödel’s undecidable sentence could only be established metamathematically and so concluded that there was ‘no difference in principle’ between his and Gödel’s examples.


Van Heijenoort has analysed Finsler’s paper in detail, concluding that it ‘remains a sketch’ whose ‘affinity [with Gödel’s paper] should not be exaggerated’ (1967, pp. 438–40). In effect, whereas ‘Gödel put the notion of formal system at the very center of his investigations,’ Finsler rejected such systems as artificially restrictive (prompting Alonzo Church to remark dryly that such ‘restricted’ notions have ‘at least the merit of being precisely communicable from one person to another’) (Church, 1946). Instead, especially in his (1944), Finsler attempted to show the consistency of the assertion that there were no ‘absolutely undecidable’ propositions.


In contrast, Emil Post directed his efforts toward showing that there were absolutely unsolvable problems in mathematics. Early on, nearly a decade before Gödel, Post realised that his methods could be applied to yield a statement undecidable within Principia whose truth could nevertheless be established by metamathematical considerations. Hence, Post concluded, ‘mathematical proof was [an] essentially creative [activity]’ whose proper elucidation would require an analysis of ‘all finite processes of the human mind’; and since the implications of such an analysis could be expected to extend far beyond the incompleteness of Principia, Post saw no reason to pursue the latter.8 Concern for the question of absolute undecidability thus led Finsler, Post and Zermelo, in varying directions, away from consideration of particular formal systems. Unlike Finsler and Zermelo, however, Post expressed ‘the greatest admiration’ for Gödel’s work, and he never sought to diminish Gödel’s achievement. Indeed, Post acknowledged to Gödel that nothing he had done ‘could have replaced the splendid actuality of your proof, and that ‘after all it is not ideas but the execution of ideas that constitute[s]…greatness.’ Post’s ‘Account of an anticipation’ was not submitted until 1941 and (after being rejected) only finally appeared in print in 1965, eleven years after Post’s death.9 It is worth noting Gödel’s own opinion of the notion of absolute undecidability, as expressed in the unsent letter draft cited above in footnote 5:


As for work done earlier about the question of formal decidability of mathematical propositions, I know only a paper by Finsler…. However, Finsler omits exactly the main point which makes a proof possible, namely restriction to some well-defined formal system in which the proposition is undecidable. For he had the nonsensical aim of proving formal undecidability in an absolute sense. This leads to [his] nonsensical definition [of a system of signs and of formal proofs therein]…and to the flagrant inconsistency that he decides the ‘formally undecidable’ proposition by an argument…which, according to his own definition…is PM a formal proof. If Finsler had confined himself to some well-defined formal system S, his proof…could [with the hindsight of Gödel’s own methods] be made correct and applicable to any formal system. I myself did not know his paper when I wrote mine, and other mathematicians or logicians probably disregarded it because it contains the obvious nonsense just mentioned (Gödel to Yossef Balas, 27 May 1970).


Especially as applied to Finsler’s later work, the epithet ‘obvious nonsense’ is well-deserved—(Finsler 1944) in particular is an almost pathological example of the confusion that can arise from failure to distinguish between use and mention—and Gödel was undoubtedly sensitive to any rival claim to priority for his greatest discovery. Nevertheless, the passage quoted above is uncharacteristically harsh, and insofar as it ridicules the idea of ‘proving formal undecidability in an absolute sense’ it seems to ignore Gödel’s own remarks in 1946 before the Princeton Bicentennial Conference, in which he suggested that, despite the incompleteness theorems, ‘closer examination shows that [such negative] results do not make a definition of the absolute notions concerned impossible under all circumstances.’ In particular, he noted that ‘by a kind of miracle’ there is an absolute definition of the concept of computability, even though ‘it is merely a special kind of demonstrability or decidability’; and in fact, the incompleteness theorems may be subsumed as corollaries to the existence of algorithmically unsolvable problems. 


Finsler, of course, had no such thing in mind in 1933, nor did Gödel. But what of Post? Had he not been hampered by manic-depression, might he have pre-empted Gödel’s results? In any case, Gödel contributed far less than Post to the development of recursion theory, even though he gave the first definition of the notion of general recursive function (in (1934), following a suggestion of Herbrand). Until Turing’s work (1936/37), Gödel resisted accepting Church’s thesis (see Davis (1982) for a detailed account), and we may well wonder whether Gödel’s focus on specific formalisms did not tend to blind him to the larger question of algorithmic undecidability.


Gödel repeatedly stressed the importance of his philosophical outlook to the success of his mathematical endeavors; perhaps it may also have been responsible for an occasional oversight. (See Kleene (1981a) and (1981b) for recent accounts of the origins of recursive function theory and Feferman (1985) for another view of Gödel’s role as a bystander.)


4. ASSIMILATION AND LATER CRITICISM 


After his I AS lectures in the winter and spring of 1934, Gödel returned to Vienna and turned his attention to set theory. By the fall of 1935, when he returned briefly to the IAS, he had already succeeded in proving the relative consistency of the axiom of choice. In the meantime, however, he had also once had to enter a sanatorium for treatment of depression. Back in America, he suffered a relapse that forced him to return to Austria just two months after his arrival. He re-entered a sanatorium and did not resume teaching at the University of Vienna until the spring of 1937.


During this period of incapacitation, Gödel’s incompleteness results were improved by Rosser (1936) (who weakened the hypothesis of ω-consistency to that of simple consistency) and extended, as already noted, through the development of recursion theory by Church, Kleene and Turing. By 1936, then, the incompleteness theorems would seem to have taken their place within the corpus of firmly established mathematical facts. 


In that year, however, the correctness of Gödel’s conclusions was challenged in print by Charles Perelman (1936), who asserted that Gödel had in fact discovered an antinomy. According to Perelman, if the soundness of the underlying axiom system were assumed (as Gödel had done in his informal introductory remarks), Gödel’s methods could be employed to prove two false equivalences, namely


Dem(qFq) = Dem(qFq)

and 

Dem(qFq) =  Dem(Fq)


where ‘Fq’ denotes Gödel’s undecidable sentence and ‘Dem’ denotes Gödel’s provability predicate (called ‘Bew’ in Gödel (1931)). The second statement is obviously a contradiction, and Perelman proposed to exorcise it by the radical expedient of rejecting the admissibility of the set of Gödel numbers of unprovable sentences. Perelman’s equivalences display a rather obvious conflation of objectand metalanguage, and, as Kleene noted in his review of (Perelman, 1936), if expressed without abuse of notation, ‘the first of them is not false, and the second is not deducible’ (Kleene, 1937a)—indeed, properly formulated, the first equivalence is just the statement that ‘Fq’ is formally undecidable. It would thus be tempting to dismiss Perelman as a crank, were it not that his arguments were apparently taken quite seriously by many within the mathematical community—so much so, in fact, that two individuals, Kurt Grelling and Olaf Helmer, felt obliged to come to Gödel’s defence.


Grelling was among those who had travelled with Gödel to Königsberg in 1930. On 2 February 1937, he wrote Gödel to advise him of Hempel’s report that ‘angesehene Mathematiker’ in Brussels and Paris were being ‘taken in’ [hereingefallen] by Perelman’s arguments. If Gödel were not already planning to publish a rebuttal, Grelling requested permission to do so on his behalf. Gödel did not in fact enter into the controversy, and Grelling’s article (1937/38) appeared at about the same time as Helmer’s (1937).


Grelling began his reply to Perelman by giving an informal outline of Gödel’s proof, drawing a careful distinction between arithmetical statements and their metamathematical counter-parts. Through the process of arithmetisation, he explained, a metamathematical statement Q′ was associated to Gödel’s arithmetical statement Q, in such a way that to any formal proof of Q there would correspond a metamathematical proof of Q′; but, he asserted, a metamathematical proof or refutation of Q′ would lead directly to a metamathematical contradiction (‘Sowohl ein Beweis von Q′ als auch eine Widerlegung würde unmittelbar auf einen Widerspruch führen’) (Grelling, 1937/ 38, p. 301), and so Q itself must be formally undecidable. Grelling went on to analyse Perelman’s formal arguments, especially his claims that


Dem(nFn) .⊃. Dem(Dem(nFq))

(1)

and 

Dem(nFn) .⊃. Dem(Dem(nFn) 

(2)


were provable in Gödel’s system. Without commenting on the abuse of notation involved (whereby ‘Dem’ should correspond to Gödel’s metamathematical predicate ‘Bew’, not to the Gödel number of its arithmetical counterpart), he (correctly) accepted (1) as demonstrable, while rejecting (2).


Helmer, on the other hand, stressed Perelman’s notational confusion, pointing out that’ “Dem” is a predicate applicable to numbers only,’ so that ‘if formula (1) is to be significant, the expression “Fn’’ must denote a number and not a sentence’. One might therefore construe ‘Fn’ ‘as a designation of the number correlated [via arithmetisation] to the sentence resulting from the substitution of “n” at the argument-place of the nth predicate in the syntactical denumeration of all the numerical predicates’, but even so, Helmer argued, formula (1) ‘[could] not possibly be legitimated’ (Helmer, 1937).


The articles of Grelling and Helmer were criticised in their turn by Rosser and Kleene in reviews published in the Journal of Symbolic Logic (Rosser (1938) and Kleene (1937b)). Rosser noted that ‘[Grelling’s] exposition of the closing steps of Gödel’s proof’ did not agree with his own understanding of it, and that Grelling’s statement quoted above to the effect that Q′ was metamathematically undecidable was ‘indubitably false,… since in a preceding sentence he says that Q′ is a metamathematical theorem’. Here, however, we may quibble: Grelling does not say that Q′ is a metamathematical theorem—he refers to it merely as ‘ein metamathematischer Satz’, which in this context simply means a statement or proposition; rather, Grelling’s statement is ‘indubitably false’ precisely because Q′ is a metamathematical theorem (in the sense that metamathematical arguments show Q to be true in its intended interpretation). As to Helmer, Kleene agreed that the source of Perelman’s errors lay in his failure to distinguish between formulas and their Gödel numbers, but he also noted Helmer’s failure ‘to distinguish as consistently between…metamathematical statements and formal mathematical sentences as between those and…syntactical numbers’ of the latter. At the same time he affirmed the basic legitimacy of Perelman’s equivalance (1), ‘Helmer notwithstanding’. 


The controversy sparked by Perelman’s paper exposes not only the fragility of the earlier acceptance of Gödel’s results, but also the misunderstandings of those results by their would-be defenders. Thus Grelling and Helmer, while criticising Perelman’s confusion between object- and metalanguage, were themselves not always careful about syntactic distinctions. Grelling saw a metamathematical contradiction where none existed, and Helmer wrongly traced Perelman’s error to a formula that is in fact provable (though not so easily as Perelman thought); while Rosser, by mistranslating ‘Satz’, failed to recognise the real source of Grelling’s misunderstanding. Only Kleene emerged from the debate untarnished (‘clean’).


For a more detailed account of Perelman’s claims and their refutation, the reader may turn to chapter 3, section 5 of Ladrière’s book (1957). That source also includes a discussion of two other, still later objections to Gödel’s work by Marcel Barzin (1940) and Jerzy Kuczyński (1938). Neither of their challenges seems to have received much notice at the time, so I shall devote little attention to them here, except to note that their criticisms, unlike Perelman’s, were based on Gödel’s detailed formal proof rather than his informal introductory arguments; like Perelman, however, both Barzin and Kuczyński thought Gödel had discovered an antinomy. (In essence, Barzin confused formal expressions with their Gödel numbers, while Kuczyński, to judge from Mostowski’s review (1938), overlooked the formal antecedent ‘Wid(κ)’ in Gödel’s second theorem.)


5. LINGERING DOUBTS 



In 1939, the second volume of Hilbert and Bernays’ Die Grundlagen der Mathematik appeared, in which, for the first time, a complete proof of Gödel’s second incompleteness theorem was given. Whether because of its meticulous treatment of syntactic details or because of Hilbert’s implied imprimatur, the book at last seems to have stilled serious opposition to Gödel’s work, at least within the community of logicians.


Outside that community it is difficult to assess to what extent Gödel’s results were known, much less accepted or understood. It seems likely that many working mathematicians either  remained only vaguely aware of them or else regarded them as having little or no relevance to their own endeavors. Indeed, until the 1970s, with the work of Matijasevic and, later, of Paris and Harrington, number theorists could (and often did) continue to regard undecidable arithmetical statements as artificial contrivances of interest only to those concerned with foundations.


Among the few non-logicians (at least to my knowledge) who took cognizance of Gödel’s work in writings of the period was Garrett Birkhoff. In the first edition of his Lattice Theory (1940) he observed (p. 128) that ‘the existence of “undecidable” propositions…seems to have been established by Skolem [n.b.] and Gödel’. In a footnote, however, he qualified even that tentative acceptance, noting that ‘Such a conclusion depends of course on prescribing all admissible methods of proof…[and] hence…should be viewed with deep skepticism.’ In particular, he believed that ‘Carnap [had] stated plausible methods of proof excluded by Gödel’. In the revised edition (1948), the corresponding footnote (p. 194) is weakened to read ‘The question remains whether there do not exist perfectly “valid” methods of proof excluded by [Gödel’s] particular logical system’; but the reference to Skolem is retained in the text proper, and an added sentence (p. 195) declares that the proof of the existence of undecidable propositions ‘is however non-constructive, and depends on admitting the existence of uncountably many ‘‘propositions”, but only countably many “proofs”’. Clearly, Birkhoff had not actually read Gödel’s paper. His statements echo those of Zermelo, but he does not cite Zermelo’s report.


Of still greater interest are the reactions of two philosophers of stature: Ludwig Wittgenstein and Bertrand Russell. Wittgenstein’s well-known comments on Gödel’s theorem appear in Appendix I of his posthumously published Remarks on the Foundations of Mathematics (extracted in English translation on pp. 431–435 of Benacerraf and Putnam (1964)). Dated in the preface of the volume to the year 1938, they were never intended to be published and perhaps should not have been—but that, of course, is irrelevant to the present inquiry. Several commentators have discussed Wittgenstein’s remarks in detail (see, for example, the articles by A.R.Anderson, Michael Dummett, and Paul Bernays, pp. 481–528 of Benacerraf and Putnam (1964)), and nearly all have considered them an embarrassment to the work of a great philosopher. Certainly it is hard to take seriously such objections as ‘Why should not propositions…of physics…be written in Russell’s symbolism?’; or ‘The contradiction that arises when someone says “I am lying”…is of interest only because it has tormented people’; or The proposition “P is unprovable” has a different sense afterwards [than] before it was proved’ (Benacerraf and Putnam, 1964, pp. 432 and 434). Whether some more profound philosophical insights underlie such seemingly flippant remarks must be left for Wittgenstein scholars to debate; suffice it to say that in Gödel’s opinion, Wittgenstein ‘advance [d] a completely trivial and uninteresting misinterpretation’ of his results (Gödel to Abraham Robinson, 2 July 1973).


As to Russell, two passages are of particular interest here, one published and one not, dating respectively from 1959 and 1963. The former, from My Philosophical Development (p. 114), forms part of Russell’s own commentary on Wittgenstein’s work: In my introduction to the Tractatus, I suggested that, although in any given language there are things which that language cannot express [my emphasis], it is yet always possible to construct a language of higher order in which these things can be said. There will, in the new language, still be things which it cannot say [my emphasis again], but which can be said in the next language, and so on ad infinitum. This suggestion, which was then new, has now become an accepted commonplace of logic. It disposes of Wittgenstein’s mysticism and, I think, also of the newer puzzles presented by Gödel.


It might be maintained that in this passage Russell is making the same point that Gödel himself stressed in his (1930/31), that by passing to successively higher types one can obtain a transfinite sequence of formal systems such that the undecidable propositions constructed within each system are decidable in all subsequent systems. Contrary to Russell, however, Gödel emphasised that each of the undecidable propositions so constructed is already expressible at the lowest level. The second passage is taken from Russell’s letter to Leon Henkin of 1 April 1963: 

It is fifty years since I worked seriously at mathematical logic and almost the only work that I have read since that date is Gödel’s. I realized, of course, that Gödel’s work is of fundamental importance, but I was puzzled by it. It made me glad that I was no longer working at mathematical logic. If a given set of axioms leads to a contradiction, it is clear that at least one of the axioms must be false. Does this apply to school-boys’ arithmetic, and, if so, can we believe anything that we were taught in youth? Are we to think that 2+2 is not 4, but 4.001? Obviously, this is not what is intended.


You note that we were indifferent to attempts to prove that our axioms could not lead to contradictions. In this, Gödel showed that we had been mistaken. But I thought that it must be impossible to prove that any given set of axioms does not lead to a contradiction, and, for that reason, I had paid little attention to Hilbert’s work. Moreover, with the exception of the axiom of reducibility which I always regarded as a makeshift, our other axioms all seemed to me luminously self-evident. I did not see how anybody could deny, for instance, that q implies p or q, or that p or q implies q or p.


…In the later portions of the book…are large parts consisting of…ordinary mathematics. This applies especially to relation-arithmetic. If there is any mistake in this, apart from trivial errors, it must also be a mistake in conventional ordinal arithmetic, which seems hardly credible.


If you can spare the time, I should like to know, roughly, how, in your opinion, ordinary mathematics—or, indeed, any deductive system—is affected by Gödel’s work.


A curious ambiguity infects this letter. Is Russell recalling his bewilderment at the time he first became acquainted with Gödel’s theorems, or is he expressing his continuing puzzlement? Is he saying that, intuitively, he had recognised the futility of Hilbert’s scheme for proving the consistency of arithmetic but had failed to consider the possibility of rigorously proving that futility? Or is he revealing a belief that Gödel had in fact shown arithmetic to be inconsistent? Henkin, at least, assumed the latter; in response to Russell’s closing request, he attempted to explain the import of Gödel’s second theorem, stressing the distinction between incompleteness and inconsistency. Eventually a copy of Russell’s letter made its way to Gödel, who remarked that ‘Russell evidently misinterprets my result; however he does so in a very interesting manner…’ (Gödel to Abraham Robinson, 2 July 1973).


6. CONCLUSIONS 


In so far as it refers to the acceptance of Gödel’s results by formalists, the received view appears to be correct. Gödel’s proofs dashed formalist hopes, but at the same time they were most persuasive to those committed to formalist ideals. In other quarters, the incompleteness theorems were by no means so readily accepted; objections were raised on both technical and philosophical grounds. Especially prevalent were the views that Gödel’s results were antinomial or were of limited generality. Cardinality restrictions, in particular, were often perceived to be responsible for the phenomenon of undecidability. Gödel succeeded where others failed because of his attention to syntactic and semantic distinctions, his restriction to particular formal systems, and his concern for relative rather than absolute undecidability. He anticipated resistance to his conclusions and took pains to minimise objections by his style of exposition and by his avoidance of the notion of objective mathematical truth (which was nevertheless central to his own mathematical philosophy). Though aware of criticisms of his work, he shunned public controversy and considered his results to have been readily accepted by those whose opinion mattered to him; nevertheless, his later extensions of his results display his concern for establishing their generality. In the long run, the incompleteness theorems have led neither to the rejection of formal systems nor to despair over their limitations, but, as Post foresaw, to a reaffirmation of the creative power of human reason. With Gödel’s theorems as centrepiece, the debate over mind versus mechanism continues unabated.


Note

In the draft of a reply to a graduate student’s query in 1970, Gödel indicated that it was precisely his recognition of the contrast between the formal definability of demonstrability and the formal undefinability of truth that led to his discovery of incompleteness. That he did not bring this out in (1931) is perhaps explained by his observation (in a crossed-out passage from that same draft) that ‘in consequence of the philosophical prejudices of [those] times…a concept of objective mathematical truth…was received with greatest suspicion and widely rejected as meaningless.’ For a fuller discussion of Gödel’s avoidance of semantic issues, see Feferman (1985). Re Tarski’s theorem on the undefinability of truth, see Tarski (1956), especially the bibliographical note, p. 152; footnote 1, pp. 247–8; the historical note, pp. 277–8; and footnote 2, p. 279. In those notes Tarski makes clear his indebtedness to Gödel’s methods, relinquishing, so it would seem, any claim to priority for Gödel’s own results (except for the prior exhibition of a consistent yet ω-inconsistent formal system).


原文(S.G. Shanker (ed.), Gödel’s Theorem in Focus, Croom Helm 1988, https://pdfslide.net/documents/godels-theorem-in-focus-philosophers-in-focus.html





https://blog.sciencenet.cn/blog-2322490-1363594.html

上一篇:哥德尔不完备性定理的接纳过程(译文) - John W. Dawson Jr.
下一篇:罗素回应哥德尔定理(译文)
收藏 IP: 77.201.68.*| 热度|

2 强涛 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2023-2-6 04:34

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部