Talk:Gödel's incompleteness theorems/History
history section
[edit]Re discussion of a history section per Wvbailey, above: I like the idea of a history section, but I've always thought of Gödel's incompleteness theorems as representing the end of a historical period rather than the beginning of one. Consider van Heijenoort's book "From Frege to Gödel" ending where it does, for example. I'd guess the history section could speak briefly about the development of formalized math (Frege to Principia), then discuss some antecedents to Gödel's theorems (e.g. Thue's (hmm, or Dehn's?) work on the word problems for semigroups and groups (I'm not sure what the stories are with these); Post's independent semi-discovery of diagonalization), then talk a bit about the Hilbert program, mention Gödel's correspondence with Herbrand, mention Gödel's presenting the first incompletness theorem at Königsberg(?) and his meeting with von Neumann there, von Neumann independently discovering the second incompleteness theorem but being scooped by Gödel a second time, and von Neumann's seminar about the incompleteness theorems back at the Hilbert school.
I think after the incompleteness theorems, things changed completely, and not much remains to be said in this article. Most things that do come to mind are already mentioned: Rosser's theorem, Gentzen's consistency proof, the (negative) solution of the Entscheidungsproblem, the essential undecidability of Robinson arithmetic, and Chaitin's version of the incompleteness theorem. I guess something could be said of the fate of Part II of Gödel's paper (which was never written), e.g. that the second incompleteness theorem was generally accepted right away even though a fully-worked-out proof didn't come til later, and that Turing (ordinal logic) and Feferman (iterated reflection) pursued the idea of iterating the consistency statement into the transfinite, and found that you can't actually beat the first incompleteness theorem that way. 66.127.55.192 (talk) 07:41, 16 February 2010 (UTC)
---
The above is interesting and I'm unfamiliar with some of it (e.g. the semigroup stuff). Here's my thoughts on the matter up to the mid-1960's, where my knowledge sputters to a halt. For the following the fundamental secondary source is Davis 2000, but there are corroborating sections to be found in Dawson 1997 ("Logical Dilemmas"), in the commentary of van Heijenoort 1967, and commentary of Davis 1965 ("The Undecidable"), in Hodge's biography of Turing (Hodges 1983).
The trick is to tie all of this together into a coherent narrative string: "this happened, then this happened, then this happened . . . voila! Goedel's Incompleteness theorems.
Where exactly the notion of "metamathematics" derives from is unclear. Is it the Vienna Circle discussions? Goedel's take on what happened to Hilbert's "program" (as published in Dial.) would be interesting to read; see the 1937 entry, an addendum to his 1934 Princeton Lectures.
- 1888, 1889 -- Dedekind and Peano axiomitize arithmetic
- 1890's -- Hilbert's successful axiomatization of geometry (proof of the consistency of geometry? cf Davis 200:116) encouraged his personal belief that all of mathematics could be axiomized and then proven complete;
- 1900-- he announces his 2nd problem, but no one quite knows what it means for 20 years (cf Davis:115)
- late 1890's-early 1900's --The discovery of the antinomies in Frege and Cantor -- in response theoreticians split into factions -- set theorists (Zermelo et. al.), Formalists (Hilbert et. al.), the Logicists (Whitehead-Russell); "constructivists/intuitionists" (Weyl, Poincare, Brouwer); cf Dawson 1997:48-49 and footnote 5 p.49.
- 1910-1925: The collapse of the Logicistic program -- Russell finally abandones his theory of types and axiom of reducibility in the 2nd edition of Principia (ca 1925; it's there, in the introduction, Russell throws down the towel.)
- 1920 -- Post's PhD thesis proves the propositional calculus is complete; the notion of derivability (provability) versus "truth" is changing (cf good discussion in Dawson:51)
- 1923ff -- Hilbert is beset upon by Brouwer and in response modifies his "program"-- the problem of finitism in his proof theory which Hilbert "never defined precisely"(Dawson 1997:50), Brouwer's rejection of completed infinity and the LoEM; Hilbert's student Weyl defects to the Brouwer camp: (e.g. cf Davis 100:114).
- 1924 -- Goedel attends university in Vienna, he changes his studies from physics to mathematics (cf Davis 2000:110)
- 1926-: At the encouragement of his teacher Hans Hahn, student Goedel attends the Vienna Circle discussions. Here the attendees discuss Wittgenstein and PM (cf Davis 2000:111); Goedel rejects their empiricism and finitistic leanings. He is introduced to the notion of metamathematics (by inference: cf Davis 2000:111).
- 1926: Finsler's Formal proofs and undecidability (cf van Heijenoort 1967:438ff). Via diagonalization he presents a proposition known to be false but formally undecidable; Goedel claims not to have read the paper or heard of Finsler. Finsler argues against Goedel's 1931 to the end of Finsler's life. (papers to be found in Dawson's compilation of Goedel's nachlass).
- 1925-1926, 1927 [? multiple papers and addresses -- 1925 "On the Infinite" van H:367ff, 1927 "The Foundations of Mathematics" van H:464ff; cf Dawson:48]. Hilbert presents his finitistic "proof program" (cf Dawson:49) for his "restricted functional calculus" (no quantifiers, choice functions instead, cf Dawson:50) in particular his 1927 address (cf van Heijenoort:464ff, with Bernays Appendix van H:485ff, and Brouwer's rebuttal cf van H:490).
- 1928: Hilbert persists in his quest for a completness proof of arithmetic; he (Hilbert and company e.g. Bernays, Ackermann) define better what his 2nd problem entails -- Hilbert's address at [Bologna?] where he precisely addresses the questions of (1) completeness of mathematics, (2) consistency of mathematics, (3) decidability of mathematics. (cf Hodges 1983:91).
- 1928- Hilbert-Ackermann's text questions whether or not 1st-order predicate calculus is complete [Davis:111, Dawson:52]
- 1930: Student Goedel succeeds in answering the Hilbert-Ackermann question. His PhD thesis proves the Completeness Proof for first order predicate calculus. (Davis claims Goedel rejects the finitistic philosophy promulgated by the Vienna Circle and this allows him "room to maneuver" in particular w.r.t. his Completeness Proof of 1930, cf Davis 2000:110, 114-115).
- 1930-1931: Goedel is now equipped with Hilbert's restricted "system" (Peano arithmetic axioms + PM's axioms of logic + (primitive-)recursion theory, cf van H's commentary p. 592-593). He shifts the question from the notion of "truth" and "falsehood" to that of "provability" (cf commentary van H:138). 1930: Hahn presents Goedel's summary paper of his incompletness results, August 1930 he appears at the Konigsberg conference day 3 he shyly presents his findings: 1931 his "On Formally Undecidable Propositions" is published (Davis 2000:122-123 gives a vivid account of this).
- 1931ff- "So, at least as originally imagined, Hilbert's program was dead!" (Davis 2000:120). Hilbert was angry (I'll have to hunt for this quote), but still persistent. But Goedel's proof is quickly accepted; Von Neumann realizes its import right off. (Davis 2000:122-123).
- 1934- Goedel visits Princeton and presents his lectures that simplify his 1931 paper, plus he proposes the notion of "general" (Herbrand-Goedel-etc recursion), in response to the discovery of the Ackermann function. He rejects Church's "thesis" that the lambda-definability is equivalent to "effective calculability"; he is less skeptical about "Herbrand's definition of recursiveness" (cf Dawson 1997:99).
- 1936- Church uses both lambda-calculus and recursion to answer Hilbert's "decision problem" in the negative: mathematics is not "decidable". In a different manner, Turing will also answer this same question in his 1937.
- 1937- Rosser eliminates Goedel's need for omega-consistency (cf Rosser's paper in Davis 1965:231-235, and Goedel's 1964 commentary in Davis 1965:73) where he also observes "the proof carries over almost literally to any system containing, among its axioms and rules of inference, the axioms and rules of inference of number theory. As to the consequences for Hilbert's program see my paper in Dial. 12(1958), p. 280 and the material cited there. See also: G. Kreisel, Dial. 12(1958), p. 346" (ibid p. 73).
- 1937- Turing's proof is published.
- 1952- Kleene formally presents the notion of "metamathematics" in his text, together with what has become classical (mu-)recursion
- 1963- Goedel accepts Turing's work as the only "precise and unquestionably adequate definition of formal system" (cf van Heijenoort:616 in particular footnote 70).
- 1964- Goedel again accepts only Turing's work as a definition of formal system, and this time he overtly rejects the lambda calculus and his own "general recursion" (cf Postscriptum in The Undecidable -- Davis 1965:71-73, in particular first starred footnote on p. 72).
Bill Wvbailey (talk) 18:23, 16 February 2010 (UTC)
- Do we have an article Timeline of mathematical logic? Does Wikipedia have timelines at all? I think that the content you just wrote would be very nice as an article, unless there is some outright prohibition on timelines. It would be a good link from the article on mathematical logic as well as this article. — Carl (CBM · talk) 19:09, 16 February 2010 (UTC)
- Since it seems we do indeed have a timeline article, even though I can't find a policy about them: do you mind if I copy your material there and add the references to the bottom? — Carl (CBM · talk) 19:16, 16 February 2010 (UTC)
- Please do. The stuff I used is from the following sources:
- Jean van Heijenoort, 1967, From Frege to Gödel: A Source Book in Mathematical Logic, 1979-1931, 3rd printing 1976, Harvard University Press, Cambridge, MA, ISBN 0-674-32449-8 (pbk.). Here are found the papers of Finsler, Post, Gödel, etc.
- Andrew Hodges, 1983, Alan Turing: The Enigma, Sikmon and Schuster, NY, ISBN 0-671-49207-1
- Martin Davis, 2000, Engings of Logic: Mathematicians and the Origin of the Computer, W. W. Norton & Company, NY, ISBN 0-393-32229-7 pbk.
- John W. Dawson, Jr, 1997, Logical Dilemmas: The Life and Work of Kurt Gödel, A K Peters, Wellesly, MA, ISBN: 1-56881-256-1
- Alfred North Whitehead and Bertrand Russell, Principia Mathematica To *56: Second Edition 1927 reprinted 1962, Cambridge at the University Press, Cambridge UK. No ISBN. With respect to his abandoment of the axiom of reducibility, see "Introduction to the Second Edition" page xiii, and especially the last section, VII Mathematical Induction pages xliii-xlv.
- John W. Dawson, Jr [Here my research fails; the books were missing from the library and I got this off the internet somehow]. This is from one of Dawson's volumes of Goedel's works re Finsler -- commentary by Dawson starts at page 406-407. "In his letter to Yossuf Balas (see page 9 of this volume) Gödel attested that he was unaware of Finsler's paper at the time he wortoe his own 1931. But when Finsler brought the paper to his attention he immediately recognized its shortcomings . . . Finsler reacted angrily to Gödel's letter, and his subsequent papers, particularly 1944, reveal a persistent inability to understand the issues involved. Like Gödel he was a stauch Platonist,; unlike Gödel, however, he failed to appreciate the value of formalization and never grasped the fundamental distinction between use and mention that is central to the modern conception of logic." (page 406). Various letters appear 407ff.
BillWvbailey (talk) 20:52, 16 February 2010 (UTC)
(edit conflict) I think most of the timeline above isn't really relevant to the history of the incompleteness theorems (at least for a short treatment like an article section). I guess we could mention Finsler. I'd forgotten about that but sort of remember that there wasn't much to it. Of course the timeline relevant to more general history of logic and using material from it in another article is good. For the Thue and Dehn stuff, see:
Here are a couple of interesting articles about Post: [1][2]
- RE length: I dunno . . . depends on the reader's background that they bring to the article. It seems too much for this article; it would have to be pruned. Carl's suggestion to put it into a timeline and then have the article reference the timeline might be a way out.
- RE Post: I'll dig into your references. Here is something interesting that follows after the above quote from Dawson's Gödel volumes (page 407 of volume ??) that says: "For another putative anticipation of Gödel's incompleteness discovery see Post 1994, as well as Post's correspondence with Gödel in volume V." I'm familiar with Post's crazy "Absolutely Unsolvable Problems and Relatively Undecidable Propositions: Account of an Anticipation" (rejected 1941, published finally in Davis 1965:340) but this paper has to do with Post's claim to anticipating Church's 1936 An unsolvable problem of elementary number theory, not anticipating Gödel's work. So Post claiming to anticipate Goedel is news to me.
- RE Finsler: Dawson's discovery of the Finsler-Goedel correspondence etc is the best stuff. But there's an interesting chapter by Herbert Breger titled "A restoration that failed: Paul Finsler's theory of Sets" in: Donald Gillies, editor, 1992, Revolutions in Mathematics, Clarendon Press, Oxford UK 1992, ISBN 0-19-853940-1 (hardback). It goes into a lot of detail about Finsler's "extreme Platonism" with some commentary about Goedel etc on page 257. BillWvbailey (talk) 20:52, 16 February 2010 (UTC)
- I can't seem to find an online copy of "Emil Post and His Anticipation of Gödel and Turing", by John Stillwell, Mathematics Magazine, Vol. 77, No. 1 (Feb., 2004), pp. 3-14 (from talk:Emil Leon Post). If you can access it, maybe it would have something. It's best to not spend much space on this Post/Finsler stuff though. It's enough to just mention it and include a wikilink. Re the timeline: it's interesting and important stuff about the history of logic in general, and we should certainly use it someplace. It's just that this article is on the narrower subject of one particular pair of theorems. 66.127.55.192 (talk) 21:07, 16 February 2010 (UTC)
I wish my brain was big enough to read J-Y Girard. He divided 20th-century logic into 3 periods (Locus Solum, p. 4 [3]):
- 1900-1930, the time of illusions: Naive foundational programs, like Hilbert's refuted by Gödel's theorem
- 1930-1970, the time of codings: Consistency proofs, monstrous ordinal notations, ad hoc codings, a sort of voluntary bureaucratic self-punishment
- 1970-2000, the time of categories: [basically what I think of as a computer science-y approach to logic].
So the first of these periods was delimited by Principia at one end and the incompleteness theorems at the other. But, perhaps we can't really call Girard a mainstream source about that sort of question ;) 66.127.55.192 (talk) 19:25, 16 February 2010 (UTC)
- This article by Hao Wang might be useful, though perhaps its contents are also in Wang's 1997 book already mentioned in the article references. 66.127.55.192 (talk) 23:19, 17 February 2010 (UTC)
- Ivor Grattan-Guinness, The Search for Mathematical Roots 1870-1940: Logics, Set Theories, and the Foundations of Mathematics from Cantor through Russell to Gödel. Princeton Univ. Press. ISBN 0-691-05858-X. -- looks promising. 66.127.55.192 (talk) 10:13, 18 February 2010 (UTC)
- Dawson, John W. Jr. (1984). "The Reception of Godel's Incompleteness Theorems". Proceedings of the Biennial Meeting of the Philosophy of Science Association, Vol. 1984,. Vol. Volume Two: Symposia and Invited Papers. The University of Chicago Press on behalf of the Philosophy of Science Association. pp. 253–271. JSTOR 192508.
{{cite conference}}
:|volume=
has extra text (help); Unknown parameter|booktitle=
ignored (|book-title=
suggested) (help)
- I am sorry for repeating myself--- but you are not right about Hilbert being naive--- Hilbert's program was not refuted by Godel's theorem, just the admittedly naive implementation of it by some of Hilbert's followers.
- Hilbert wanted to prove the consistency of infinitary systems like set theory using "finitary" (meaning symbol manipulation) means. Godel's theorem does not preclude doing this, but it does show that the method of "finitary" proof will have to involve large countable ordinals and computation. Gentzen implemented Hilbert's program in a satisfactory way for PA, and others have extended this to ordinal analysis of higher theories (as I am sure you know--- I just wanted to emphasize how modern Hilbert's thinking was. It is important to read Hilbert himself, not what people say about him).
- Other than the slight to Hilbert, I agree with your timeline. I don't understand what "categories" has to do with anything, though. Do you mean category theory categories? What does that have to do with foundations? Do you mean topoi? I don't get it.Likebox (talk) 04:23, 18 February 2010 (UTC)
- It's not my timeline; it's by Jean-Yves Girard, a brilliant and important but rather idiosyncratic logician, a lot of whose writings seem like far-out science fiction. Yes, category theory categories. He gave a longer explanation that I didn't bother typing, but you can look at the pdf I linked. Re categories: I don't think he means anything like topos theory. He means the Curry-Howard correspondence as analyzed from the 1960's exposed a relationship between logic and categories. He is not disrespectful of Hilbert. He says Hilbert had a beautiful idea that was unattainable. He does repeatedly disrespect Tarski, for reasons I don't quite comprehend. (edited) 66.127.55.192 (talk) 10:04, 18 February 2010 (UTC)
- Other than the slight to Hilbert, I agree with your timeline. I don't understand what "categories" has to do with anything, though. Do you mean category theory categories? What does that have to do with foundations? Do you mean topoi? I don't get it.Likebox (talk) 04:23, 18 February 2010 (UTC)
- Sorry I haven't responded promptly. You've uncovered lots of interesting sources that I've haven't had a chance to investigate. I'm disappeared somewhere in the White Mountains; I'll be back to it in a few days. BillWvbailey (talk) 22:21, 18 February 2010 (UTC)
---
RE whatever happened to the follow-up paper ("Part II") that Goedel expected to publish but didn't and why not: The following comes from a paper by Feferman (and harks back to Dawson's biography):
- "7Part II of Gödel (1931) never appeared. Also promised for it was a full proof of the
second incompleteness theorem, the idea for which was only indicated in Part I. He later explained that since the second incompleteness theorem had been readily accepted there was no need to publish a complete proof. Actually, the impact of Gödel’s work was not so rapid as this suggests; the only one who immediately grasped the first incompleteness theorem was John von Neumann, who then went on to see for himself that the second incompleteness theorem must hold. Others were much slower to absorb the significance of Gödel’s results (cf. Dawson 1997, pp. 72-75.) The first detailed proof of the second incompleteness theorem for a system Z equivalent to PA appeared in Hilbert and Bernays (1939)." (page from http://math.stanford.edu/~feferman/impact.pdf.
BillWvbailey (talk) 01:30, 23 February 2010 (UTC)
History -- Stephen C. Kleene in Feferman et. al.
[edit]I got a cc of Feferman et. al. (editors), 1986, Kurt Gõdel: Collected Works, Volume I, Oxford University Press, Oxford and New York, ISBN 13: 978-0-195-14720-9. On pages 126-128 Kleene presents a condensed history of what led up to Goedel's taking on his proofs (mostly re Hilbert's "program"). This is followed by a 7-part description of the proofs (not trivial, not easy for a layman), and then a very interesting discussion of Hilbert's notion of "finitary proof" and some history in this regard, on pages 138-141. The history abbreviates (but agrees with) what I wrote in the timeline. I'll write a precis here when I have a bit more time. What I'd recommend is anyone interested in the history pursue Kleene's treatment (pages 126-141) of this book and also Grattain-Guiness as noted by our mystery editor above (the Vienna Circle + the encouragement of Hans Hahn are very important elements in this story). Bill Wvbailey (talk) 16:04, 27 February 2010 (UTC)
- It might be good to use some of that in the article about the Hilbert program. I don't think it's worth mucking with intricate legalistic analysis of what a finitary proof is or what Hilbert thought it was. The point to remember is that Hilbert himself wasn't a finitist and neither was his opponent Brouwer. Hilbert wanted a minimal foundational system not because he needed to be convinced by it, but in order to quiet anyone else's objections to the infinitary math that Hilbert liked (Cantorian set theory, classical logic). Brouwer didn't go for set theory or classical logic, but I believe he accepted what we now call Heyting arithmetic even though it is infinitary. So Hilbert didn't much care what the outer boundary of finitism was, as long as he was well inside its parameters. Simpson's article that CBM linked someplace explains that pretty well. 75.62.109.146 (talk) 08:13, 28 February 2010 (UTC)
Here's the promised precis of the beginning pages (126-127) of Kleene's commentary before Goedel's 1931 in Feferman et. al. 1986, Kurt Goedel Collected Works Volume I Publications 1929-1936:
- In his 1918 and 1921, [does he mean his 1923 “proof theory” paper and his address of 1925 published 1926 per Dawso:49?] David Hilbert addressed the paradoxes that arose in Cantorian set theory [and Frege’s logical system] with a two-part proposal. First, a suitable portion of mathematics should be formalized into a system (call it S) such that deductions “consist simply of mechanical manipulations of the formal objects, with no reliance on their meanings”; second, this formal system S requires proof to be “(simply) consistent, i.e. that no two sequences of its formulas exist of which one is a proof in S of a formula A and the other its negation ~A.” This formal system would become “a new branch of mathematics (to be called “proof theory” or “metamathematics”). Investigations in Hilbert’s “program” “called for using only the most secure methods . . . usually translated as “finitary””.
- After he finished his 1929 doctoral dissertation "The completeness of the calculus of logic" Goedel set himself proving Hilbert's challenge -- to prove the consistency of analysis "pursuant to Hilbert's program). (Kleene's commentary preceding Goedel's 1931 in Feferman et. al. 1986:126-129)
There is more to come. BillWvbailey (talk) 22:43, 3 March 2010 (UTC)
Timeline of more-immediate events surrounding Goedel's incompleteness theorems
[edit]Not to panic -- this is meant for reference/guidance and not for publishing "as is". With the exception of Tarski, all the major players make their appearance -- Hilbert, von Neummann, Bernays, Zermelo, Finsler, Kleene & Rosser, Post. The following is derived from Dawson 1997 (biography of Goedel) Chapter IV “Moment of Impact” (1929-1931). Some of Grattain-Guiness is derived from this (cf parenthetic note to 9.2.3 in Grattain-Guiness 2000:509), as are parts of Davis 2000 (for example see sources in the footnotes for his chapter 6 “Goedel Upsets the Applecart” on pages 224-233). In turn, Dawson along with Davis and Grattain-Guiness are relying heavily on the assembled papers by Feferman, Kleene, et. al. in ‘’Kurt Goedel Collected Works Volume I Publications 1929-1936’’. Bill Wvbailey (talk) 15:57, 6 March 2010 (UTC)
G-G is an abbreviation for Grattain-Guiness:2000 The search for Mathematical Roots 1870-1940. Bill Wvbailey (talk) 16:09, 8 March 2010 (UTC). Davis 2000 is his Engines of Logic. Bill Wvbailey (talk) 18:28, 8 March 2010 (UTC)
Influences leading to Goedel's incompleteness results
[edit]- 1928 - International Congress in Bologna Italy, Hilbert delivers an address that both outlines his "proof theory" and defends it against the assult of Brouwer. With regards to Hilbert's second problem, Ackermann and von Neumann seemed to be making progress toward the "finitary consistency proof for PA" [Davis 2000:116. Hilbert's system is Peano Arithmetic fortified with a set of logical axioms derived from Principia Mathematica and what is now known as primitive recursion: the use of substitution and modus ponens with a limited induction axiom]. However, it will turn out that the restrictions placed on their "system" render the Ackermann-von Neumann proof inadquate to encompass all of PA.
- 1928-1030 - in Vienna, Brouwer lectures on intuitionism, argues for "languagelessness clearly, and near the end he distinguished a notion of 'correct theories', in which the law of excluded middle iwas forbidden as opposed to 'non-contradictory' theories where it was allowed. "Both Carnap and Goedel were impressed by the pessimistic idea that there might be unsolvable problems in mathematics (Koehler 1991a, drawing upon Carnap's diary)" (G-G:504)
- 1926-1930 - Hahn invites his young student Goedel to the Vienna Circle as organized by Schlick its founder; in 1924 " . . . a group of philosphers and scientists continuing in the empriricist-positivist tradition of Mach and Helmholz. Of relevance, this group also included Carnap (Davis 2000:110. Davis observes that Carnap studied under Frege, was a "leading figure in the philosophical tendancy called logical positivism.). (cf a concise history of this invitation-only gathering in G-G 2000:507-508 and his section 8.9 The Rise of Austria in the 1920s: The Schlick Circle. (G-G:497). Carnap would contribute by mail (G-G:507). "Positivism and reductionism were held to govern both epistemology and ontology, and metaphysics was disliked; father figures included Mach and espeically Russell, and Wittgenstein's Tractatus exercised both positive and negative influence (G-G:498; Davis 2000:111 observes that both the work of both Russell and Wittgenstein were discussed in these meetings, and he opines that while Russell's logicism and Wittgenstein's "emphasis on the problems of speaking about language from within language" must have influenced Goedel, "he found himself out of symapathy with much of what he heard" (Davis:111)).
- 1930- Carnap's rejecting "metaphysics". G-G opines that while he rejected the metaphysics of Hegel and Heidegger and his "repulsion is understandable", his own "stance [is] an opposite stupidity which came to weaken VC philosophy (G-G:514).
- 6 July 1929: Goedel’s dissertation (On Completeness of the Calculus of Logic) -- the topic derived from an unproven thesis as mentioned as such in the text of Hilbert/Ackermann (cf G-G:504) -- is formally approved. Dawson opines that “Goedel had already begun to think along the lines of his incompletness discovery
- 22 October 1929: revision of Goedel’s dissertation is received, but it will be a year (on 19 September 1930) before it is published (Dawson:60).
- 6 February 1930: Goedel is granted his PhD. But he cannot work as an unpaided “dozent”, let alone earn money as a lecturer, until he publishes his ‘’Habilitationsschrift’’, i.e. another major paper. 1930: So Goedel sets out to prove a positive solution to the second of Hilbert’s problems – “giving a finitary consistency proof for the axioms of analysis”; his goal being to prove Hilbert ‘’correct’’ (Dawson:63). Davis:118 opines that Goedel was able to transcend the mindset of the Vienna Circle that biased it against any kind of mathematical proof other than provability; rather, "unencumbered by such beliefs, Goedel was led to the remarkable conclusion that on the contrary, no only is there a meaningful notion of mathematical truth, but also its extent goes beyond what can be proved in any given formal system" (Davis:118). In other words, there are true propostions expressible in the system that cannot be proved in the system (Davis:118); this is perhaps a reflection of his Platonistic outlook that he claimed to hold such views since at least 1925 (cf Dawson:100). Dawson opines that Goedel disagreed with both Hilbert’s “naïvely optimistic belief in the limitless efficacy of formal methods” and with Brouwer’s contempt for the very idea of formalization (Dawson:55). G-G opines that "Apparently Goedel found his theorem when he repesented each real number by an arithmetical proposition φ(x) and found that, while 'φ(x) is provable' could also be so treated, 'φ(x) is true' landed him in liar and naming paradoxes (Wang 1996a, 81-85: Hao Wang 1996 A Logical Journey. From Goedel to Philosophy, MIT Press, Cambridge MA). Maybe because of Viennese empiricist doubts over truth, he recast the paradox in terms of unprovability and 'correct' (' richtig ') propositions . . .. (G-G:509).
- ca 1930: Goldstine (another biographer of Goedel) reports (in conversation with von Neumann) that von Neumann was, at the same time, working on Hilbert’s second problem, but he had not recognized the critical “truth-versus-provable” issue that Goedel did recognize (Dawson:71).
Immediate events surrounding Goedel’s incompleteness results
[edit]- 26 August 1930: While at a café Goedel announces to Carnap, Feigel and Waismann (all 4 will be attendees at the upcoming Konigsberg conference the next week) that he has obtained the first of his incompletness theorems (Dawson:68).
- 29 August 1930: At the same café Goedel discusses his discoveries further with Carnap (Dawson:68).
The four journey with Hahn and Grelling to Konigsberg (Dawson:68).
- 5-7 September 1930: The conferences in Konigsberg: three societies hold their conferences jointly: (1) Conference on Epistomology of the Exact Sciences (organized by a Berlin Society allied with the Vienna Circle), (2) 91st annual meeting of the Society of German Scientists and Physicians, and (3) 6th Assembly of German Physicists and Mathematicians (Dawson:68-69).
- (conference 1) 5-September 1930 (Friday): 1-hour addresses by Carnap, Heyting, and von Neumann re the three mathematical philosophies (logicism, intuitionism, formalism respectively) (Dawson:69).
- (conference 2) 6-September 1930 (Saturday): Hilbert delivers the opening address to the Society of German Scientists and Physicians where he announces: “The true reason why [no one] has succeeded in finding an unsolvable problem is, in my opinion, that there is no unsolvable problem.” Dawson assert that Goedel was likely in the audience (Dawson:71). Goedel would never meet Hilbert face-to-face (Dawson:72).
- (conference 1) 6-September 1930, 3 PM to 3:20 PM (Saturday): Goedel’s 20 minute “contributed talk” (not about incompleteness; this would come the next day) (Dawson:69).
- (conference 1) 7-September 1930 (late in the discussion, Sunday): Roundtable discussion of Friday’s addresses. Godel, “without warning and almost offhandedly, quietly announced that some propositions while true are unprovable in the formal system of classical mathematics” (Dawson:69).
- Transcript by recorder Reichenbach shows no follow-up discussion of Goedel’s announcement nor even of Goedel’s attendance (Dawson:69).
- von Neumann may have been the only one to grasp the significance, he apparently draws Godel aside for discussion (cf Dawson:69).
- 16 October 1930: Carnap records Goedel’s refutation of Behmann’s claim that “every existence proof could be made constructive”. His counterexample is similar to one of Brouwer’s. (footnote 9 Dawson:73). But G-G:521 asserts that "Goedel clarified that he had not refuted Behmann but had shown that unrestricted type theory would generate paradoxes independently of the forms of nominal definitions".
- 23 October 1930: Goedel submits an abstract of his paper (“Some metamathematical results on completeness and consistency” cf ‘’Collected Works Volume 1’’ pp. 140-143) to the Vienna Academy of Sciences (Dawson:70).
- 17 November: the editors of Monatshefte fur Mathematic und Physic receive the full paper (Dawson:70).
Unexpected competition (von Neumann)
[edit]- 20 November: von Neumann writes Goedel to announce that he had discovered “that in a consistent system any effective proof of the unprovability of 0=1 could itself be transformed into a contradiction”; Godel’s response has not been located. (Dawson:70).
- 29 November: von Neumann writes Goedel to thank him for the preprint. “von Neumann was not accustomed to being anticipated, and the tone of his second letter . . . conveys his disappointment” (Dawson:70). von Neumann soon curtails his own research efforts in logic; he remains a friend of Goedel throughout their lives (Dawson:70); see 1932 below.
General confusions, and a suggestion from Herbrand to enhance the notion of recursion
[edit]- ca early 1931: Paul Bernays on behalf of Hilbert writes to thank Goedel for a reprint of his paper, he requests galley prints (Dawson:70, also footnote 6).
- December 1930: Hilbert delivers a talk that will become his 1931a, b (see below) introduces the “ω-rule” (footnotes 7, 8 Dawson:72-73); Goedel et al consider this to be contrary to Hilbert’s “basic principles (Dawson:73)
- 15 January 1931: Goedel speaks before the Schlick [aka Vienna] Circle [cf a long discussion of Carnap's and Behmann's work at this time in G-G:513-523]. Hahn (Goedel's mentor/thesis advisor), Felix Kaufmann and Schlick express their confusions and misunderstandings. Goedel quotes Brouwer’s belief that no formal system could comprise all intuitionistic mathematics (Dawson:73); see 16 October 1930.
- 18 January 1931: Bernays thanks Goedel for the galleys. “So at that point, if not before, Hilbert must have become aware of what Goedel had done” (Dawson:72). Constance Reid, Hilbert’s biographer, reports that Bernays told her that Hilbert was angry. Bernays asks for clarification of points in Goedel’s proof; Dawson opines that Bernays found the proofs “difficult to assimulate”; Bernays would write also on 20 April, and 3 May; he is confused by an earlier finite consistency proof of Ackermann and von Neumann, one whose “restricted applicability is difficult to understand” (Dawson:73)
- 7 February 1931: Bernays meets with Goedel, confesses his work “hard to understand” (Dawson:73)
?? 1931a, 1931b: Hilbert “dealt with [the consequences of the incompleteness theorems] in a positive way”; however, neither paper cites Goedel’s work (Dawson:72-73).
- 25 March 1931: 100 cc’s of the incompleteness paper is sent to Goedel; he sends two to Bernays. Bernays passes the galley prints to Herbrand (Dawson:74).
- 7 April 1931: Herbrand sends Goedel off-prints of his own work, comments about implications of the incompleteness theorems, suggests a more-general recursion schema (Dawson:74). Goedel would take up this matter and present Herbrand’s suggested “general recursion” in the Princeton lectures of 1934.
- 25 July 1931: Goedel responds to Herbrand, but Herbrand is killed in a mountaineering accident the day the letter arrives. Goedel states that he is not convinced that the second incompleteness theorem “contradict[s] Hilbert’s formalistic viewpoint” (Dawson 74:75).
A strong detractor (Zermelo) and a priority challenge (Finsler)
[edit]- 15 September 1931: Goedel’s talk encounters Zermelo “his first and most vocal detractor . . . a very irascible person” (Dawson:76).
- 21 September 1931 -- writes Goedel to announce that he has found “an essential gap in Goedel’s argument” (Dawson:76).
- September 1931 -- the Bad Elster lectures: Zermelo The Deutsche Mathematiker-Vereinigung holds its annual meeting in Bad Elster (G-G:512), with Zermelo and Goedel presenting papers. Zermelo rejects the notion of "finitude in proof" and presents his theory of infinitely long proofs (containing "infinite con- and disjunctions") and "especially the message of the lecture 'On the existence of undecidable arithmetical theorems in formal systems of mathematics' that was given by Goedel.
- 12 October 1931: Goedel replies to Zermelo with a 10-page letter and hopes that now Zermelo will be convinced of his proofs. (Dawson:75, G-G:512-513 gives a detailed account
- 29 October 1931: Zermelo continues to misunderstand and publishes his criticisms in print (see below). Goedel “no doubt thought it pointless to pursue the matter any further.” Carnap agrees with Goedel that Zermelo completely misunderstands. (Dawson:76)
- 1932 - Zermelo writes up his lectures at Bad Elster for publishing and incluudes a "rather scathing paragraph on his young competitor" (G-G:513) G-G opines that Zermelo's work did not gain much attention nor traction in infinitary logics after WWII. (ibid).
- 1932 – von Neumann lectures in Princeton NJ about Goedel’s results; student Stephen C. Kleene first hears of Goedel (Dawson:70-71).
- 25 June 1932 – Goedel presents his paper as his Habilitationsschrift (Dawson:81).
- 3 December 1932 – Goedel is granted his post-doctoral “doctorate” “Dr. habil.” (Dawson:87).
- 11 February 1933 – Finsler, citing his 1926, challenges Goedel’s priority re the incompleteness results (Dawson:89).
- 25 March 1933 – Goedel bluntly points out where Finsler’s proof fails (Goedel would state that he was unaware of Finsler’s paper and it “contain[ed such] obvious nonsense” (Dawson:89).
- ca June-July 1933 – Finsler studies Goedel’s offprints, “retorts angrily”. Goedel does not reply (Dawson:90). (Commentary by Dawson and letters etc to be found in Volume ?? of Goedel's Collected Works).
- The published letters to Finsler are in Volume 4 of the CW, pp 405 - 416, including the introductory note by Dawson. Also reproduced there are some of Finsler's letters to Goedel. --Taekwandean (talk) 10:20, 17 June 2010 (UTC)
- Yeah right now the (hardback) volumes IV and V cost ~$250 each. I took photos off the screen previews from Amazon to get what I could get (an old trick, but it works). I've got vols. I- III in paperback. Thanks. Bill Wvbailey (talk) 23:55, 17 June 2010 (UTC)
- The published letters to Finsler are in Volume 4 of the CW, pp 405 - 416, including the introductory note by Dawson. Also reproduced there are some of Finsler's letters to Goedel. --Taekwandean (talk) 10:20, 17 June 2010 (UTC)
Aftermath -- After proposing Herbrand's more-general recursion, Goedel exists recursion theory
[edit]- Fall 1933, 1934 – Princeton NJ: Alonzo Church is concerned that “the incompletness theorems were somehow dependent on the particularities of formalization”, Goedel seeks to dispel this notion in his lectures (a refined version of his consistency proofs) as transcribed by students Kleene and Rosser (cf Dawson:101). At the end of the lectures Goedel also proposes “general recursion” as suggested by Herbrand. Goedel suggests this, rather than Church’s lambda-calculus, as a foundation necessary to prove undecidability (cf Dawson:101). Goedel exits further work in recursion theory (Dawson:102).
- 1936 – Rosser’s paper demonstrates that simple consistency rather than ω-consistency is adequate to demonstrate incompleteness of a formal theory (Dawson:112).
- October 1938 – Goedel is in New York, meets Emil Post who “had also come close to obtaining the incompletness theorems” (Dawson:130); Post outpours his ideas, and his heart, to Goedel of his “anticipation” but without malice acknowledges Goedel’s achievement (Dawson:131).
- 1939 – a full proof of the second incompleteness theorem is published in Hilbert and Bernays 1939 (cf footnote 6 Dawson:70).
Wittgenstein on Goedel
[edit]Wang [see ref. in Goedel on Wittgenstein on Goedel, page 180 gives a history of W. commenting on G.]. W. died in 1951 (cf Chronology in Monk) and none of his major works were published in his lifetime.
- ? 1950’s – posthumous Wittgenstein's ‘’Remarks on the Foundations of Mathematics’’ seems to “betray a particularly glaring lack of comprehension’’ (Dawson:77 with caveat in reference. This caveat appears as footnote 179 on page 283 that in turn references Juliet Floyd 1995 On Saying What You Really Want to Say: Wittgenstein, Goedel, and the Trisection of the Angle. In Jaakko Hintikka, ed., From Dedekind to Goedel: Essays on the Development of the Foundations of Mathematics 373-425. Boston and Dordrecht:Kluwer.).
- According to Wittgenstein's Philosophy of Mathematics,
- After the initial, scathing reviews of RFM [Remarks on the Foundations of Mathematics], very little attention was paid to Wittgenstein's (RFM App. III) and (RFM VII, §§21-22) discussions of Gödel's First Incompleteness Theorem (Klenk 1976, 13) until Shanker's sympathetic (1988b). In the last 11 years, however, commentators and critics have offered various interpretations of Wittgenstein's remarks on Gödel, some being largely sympathetic (Floyd 1995, 2001) and others offering a more mixed appraisal [(Rodych 1999a, 2002, 2003), (Steiner 2001), (Priest 2004)]. Recently, and perhaps most interestingly, (Floyd & Putnam 2000) and (Steiner 2001) have evoked new and interesting discussions of Wittgenstein's ruminations on undecidability, mathematical truth, and Gödel's First Incompleteness Theorem [(Rodych 2003, 2006), (Bays 2004), (Sayward 2005), and (Floyd & Putnam 2006)]. —Preceding unsigned comment added by 98.210.236.39 (talk) 19:04, 8 March 2010 (UTC)
- Wow! BillWvbailey (talk) 04:37, 15 March 2010 (UTC) What I meant to say is I'm really impressed with this research. Bill Wvbailey (talk) 04:39, 15 March 2010 (UTC)
- After the initial, scathing reviews of RFM [Remarks on the Foundations of Mathematics], very little attention was paid to Wittgenstein's (RFM App. III) and (RFM VII, §§21-22) discussions of Gödel's First Incompleteness Theorem (Klenk 1976, 13) until Shanker's sympathetic (1988b). In the last 11 years, however, commentators and critics have offered various interpretations of Wittgenstein's remarks on Gödel, some being largely sympathetic (Floyd 1995, 2001) and others offering a more mixed appraisal [(Rodych 1999a, 2002, 2003), (Steiner 2001), (Priest 2004)]. Recently, and perhaps most interestingly, (Floyd & Putnam 2000) and (Steiner 2001) have evoked new and interesting discussions of Wittgenstein's ruminations on undecidability, mathematical truth, and Gödel's First Incompleteness Theorem [(Rodych 2003, 2006), (Bays 2004), (Sayward 2005), and (Floyd & Putnam 2006)]. —Preceding unsigned comment added by 98.210.236.39 (talk) 19:04, 8 March 2010 (UTC)
- April 1963 – Bertrand Russell admits that he finds Goedel’s work puzzling (Dawson:77).
Why Goedel and not Skolem or the team of Hilbert-Ackermann-Bernays?
[edit]- 7 December 1967: In a letter to Hao Wang Goedel concluded that the failure to discover the completeness theorem (i.e. the theorem of his doctoral thesis) was indeed surprising. Davis opines that "there was little novelty in his methods, all perfecctly well known to logicians at the time". But Davis goes on to apply this failure more widely than to the specific completeness theorem:
- "The completeness theorem is indeed an almost trivial consequence of [Skolem 1923b]. . . . This blindness . . . . of logicians is indeed surprising. But I think the explanation is not hard to find. It lies in a widespread lack, at that time, of the required epistemological attitude toward metamathematics and toward non-finitary reasoning . . . . [The easy] reference from [Skolem 1923b] is definitely non-finitary, and so is any other completeness proof for the predicate calculus. Therefore these things escaped notice or were disregarded" (Davis:115 quotes the italicized phrase and in footnote 6 references Dawson:58, who in turn references Hao Wang in a letter from 7 Dec 1967).
Goedel on Wittgenstein on his (Goedel's) incompleteness theorems
[edit]A reader of Wittgenstein must be made aware that "Wittgenstein's published output was tiny. In his lifetime, he published one book, one article and one book review. . . It [the book review] was published in 1913 in a Cambridge undergraduate magazine called the Cambridge Review, and it was his very first publication" (page 5). After his Tractatus, all else of major significance was unpublished in his lifetime (even the Blue and Brown notebooks that were transcribed by students from his lectures but not actually published until well after his 1951 death i.e. in 1974-5, and RFM was published by Blackwell in 1967) [see Chronology and Primary Material pp. 108-109]. Monk notes that ". . . It should be borne in mind that none of them [his unpublished works], not even Philosophical Investigations, can be regarded as a book by Wittgenstein" (p. 63) (These quotes etc are from Ray Monk 2005 How to Read Wittgenstein, W. W. Norton & Company, NY, ISBN 0-393-32820-1 (pbk).).
A google search using the phrase [with quote-marks] "Godel's comments on Wittgenstein's" coughs up only one source: Hao Wang's 1996 A Logical Journey, From Goedel to Philosophy in particular pages 179ff -- here Wang is discussing W. with Goedel after Goedel has had a chance to read the 1967 Remarks on the Foundations of Mathematics [RFM] that Carl Menger had sent him (wanting some comments for RFM) and after some information Wang has sent him in advance:
- "Goedel's main comments on Wittgenstein were made on 5 April 1972 . . . his habitual calmness was absent in his comments:
- "5.5.4 Has Wittgenstein lost his mind? Does he mean it seriously? He intentionally utters trivially nonsensical statements. What he says about the set of all cardinal numbers reveals a perfectly naïve view....He has to take a position when he has no business to do so. For example, “you can’t derive everything from a contradiction.” He should try to develop a system of logic in which that is true. It’s amazing that Turing could get anything out of discussions with somebody like Wittgenstein.
- "5.5.5a He has given up the objective goal of making concepts and proofs precise. . . .
Goedel's 20 April 1972 written response to Menger's letter includes this:
- "5.5.5b It is clear from the passages you cite [RFM: 117-123, 385-389] that Wittgenstein did not understand it [1st incompleteness theorem] (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite, namely a mathematical theorem within an absolutely uncontroversial part of mathematics (finitary number theory or combinatorics). Incidentally, the whole passage you cite seems nonsense to me ."
I've read Timothy Bays 2004 On Floyd and Putnam on Wittgenstein on Goedel JPhil CI.4:197-210 where the "relevant passage" of Wittgenstein's is quoted from "Anscombe" (1956). I will flesh this out when I get a cc of Wang. Bill Wvbailey (talk) 20:36, 21 April 2010 (UTC)
History
[edit][This is a rough cut. I'm having problems reducing it. G-G stands for "Grattain-Guiness "]. I am intentionally avoiding the "Wittgenstein on Gödel" and "Gödel on Wittgenstein on Gödel" sections because I don't think they're of much relevance except to stir up a fracas: Gödel thought Wittgenstein was either a dissembler or a putz, take your pick [see the detailed quotes in the history time-line above]. After comments etc I'll doublecheck spelling etc. sources have been checked, with emendations. I have a poor cc of the Yossef Balas letter and a partial cc of the Finsler letters+commentary, but am not sure if this is from Volume 5 of Complete Works, and the pages need verification. BillWvbailey (talk)
Influences leading to Gödel's incompleteness results
[edit]The Hilbert school: With regards to Gödel's "direction for creative work" Feferman credits the lectures of Rudolf Carnap on mathematical logic and the publishing of David Hilbert's and Wilhelm Ackermann's 1928 Grundzüge der theoretishen Logik (Feferman in Collected Works Vol. 1:p. 5). By 1928, with regards to Hilbert’s second problem of 1900, Ackermann and John von Neumann “seemed to be making progress toward a finitary consistency proof for PA [Peano Arithmetic]" (Davis 2000:116) [1]. However, it would turn out that the restrictions they had to place on their "limited sub-system” in order to prove it consistent, the restrictions would render the Ackermann-von Neumann proof inadequate to encompass all of PA [Dawson:50, Davis 2000:116].
Influences: Besides the challenge of Hilbert’s second problem, a couple of currents in the mathematical community were having an effect on Gödel’s thinking. Between 1928-1930 Luitzen Egbertus Jan Brouwer’s lectures on intuitionism had influence on "Carnap and Gödel [; both] were impressed by the pessimistic idea that there might be unsolvable problems in mathematics (Koehler 1991a, drawing upon Carnap's diary)" (G-G:504). Between 1926-1930, at the invitation of his teacher Hans Hahn, Gödel attended meetings of the so-called “Vienna Circle”, "formed in 1924 by a group of philosophers and scientists continuing in the empiricist-positivist tradition . . .”(Davis 2000:110); “father figures included Mach and especially Russell, and Wittgenstein's Tractatus exercised both positive and negative influence” (G-G:498). While Russell's logicism and Wittgenstein's "emphasis on the problems of speaking about language from within language" (Dawson:62) must have influenced Gödel, "he found himself out of sympathy with much of what he heard" (Davis 2000:111).
Gödel discovers his theorems: On 6 July 1929 Gödel’s dissertation The completeness of the axioms of the functional calculus of logic[2] was formally approved (cf Chronology in Dawson:313); the topic derived from an unproven thesis mentioned as such in the Hilbert and Ackerman text (cf G-G:504), and on 6 February 1930 Gödel was granted his PhD. But he could not work as an unpaid “dozent”, let alone earn money as a lecturer, until he published his Habilitationsschrift, i.e. another major paper. So in 1930 Gödel set out to provide a positive solution to the second of Hilbert’s problems – to give a finitary consistency proof for the axioms of analysis relative to arithmetic; his goal being “not to destroy Hilbert’s program but to advance it” (Dawson:61)[3]. G-G opines that "Apparently Gödel found his theorem when he represented each real number by an arithmetical proposition φ(x) and found that, while 'φ(x) is provable' could also be so treated, 'φ(x) is true' landed him in liar and naming paradoxes” [4]. As reported by Goldstine, von Neumann stated that he was, at the same time, working on Hilbert’s second problem, but he had not recognized the critical “truth-versus-provable” issue that Gödel did recognize (Dawson:71). As to why others had not arrived at the proof first, Gödel would blame "the philosophic prejudices of our times 1. nobody was looking for a relative consistency proof because [it] was considered axiomatic that a consistency proof must be finitary in order to make sense 2. a concept of objective mathematical truth as opposed to demonstrability was viewed with greatest suspicion and widely rejected as meaningless."(Letter to Yossef Balas in Collected Works Vol. IV:10).
Gödel announces his incompleteness results
[edit]By late August, Gödel had reached conclusions firm enough that he felt he could announce them to his friend Carnap (Dawson:68). Gödel and Carnap would travel together with two friends to a joint conference a few days later, in Königsberg on Friday-Sunday, 5-7 September 1930 (Dawson:68-69). There on Saturday Hilbert delivered the opening address to the Society of German Scientists and Physicians where he announced his now-famous prognostication: "The true reason, according to my thinking why Comte[5] could not find an an unsolvable problem lies in the fact that there is no such thing as an unsolvable problem" (Reid 196). But then on Sunday, in a follow-up roundtable discussion of Friday’s addresses, “without warning and almost offhandedly, Gödel, quietly announced that ‘one can even give examples of propositions . . .while contentually true, are unprovable in the formal system of classical mathematics’ ” (Dawson:69). Dawson reports that the time of his announcement Gödel "definitely" did not yet have his second theorem (i.e. theorem XI). Thus the announcement was with respect to the "first" incompleteness theorem (theorem VI). Wang reports that he did not have his arithmetical-relation theorems VII and VIII (cf Collected Works Vol. I:198), these deriving from a question from von Neumann after the meeting as to whether "number-theoretic undecidable propositions could be constructed". In fact when he discovered they could, "Gödel was astonished" (Collected Works Vol.I:137); Feferman reports that while independently of theorems VII and VIII Gödel would "at the same time" derive his "second" incompleteness theorem (i.e. theorem XI). This put him on a priority collision-course with von Neumann.
von Neumann as unexpected competition
[edit]Von Neumann was one of the roundtable participants, and he may have been the only one to grasp the significance; he apparently drew Gödel aside for discussion (cf Dawson:69). Indeed, von Neumann had good reason to be interested. In a letter dated 20 November von Neumann announced to Gödel that he had discovered "that in a consistent system any effective proof of the unprovability of 0=1 could itself be transformed into a contradiction"; Gödel’s response has not been located (Dawson:70). But Gödel’s manuscript was received for publication on 17 November, and he had submitted an abstract received on 23 October. So there could be no issue of priority; a few days later (29 November) von Neumann wrote Gödel to thank him for the preprint of Gödel’s paper (Dawson:70). Von Neumann soon curtailed his own research efforts in logic, and he remained a friend of Gödel's throughout their lives (Dawson:70).
The immediate reception: confusion in the Hilbert school
[edit]On 15 January 1931 Gödel spoke before the Vienna Circle about his results, but Hahn, Felix Kaufmann and Moritz Schlick expressed their confusions and misunderstandings (Dawson:73). On 18 January Hilbert’s assistant Paul Bernays would thank Gödel for the galleys Gödel sent him[6]. “So at that point, if not before, Hilbert must have become aware of what Gödel had done” (Dawson:72). Constance Reid, Hilbert’s biographer, reports that Bernays told her that Hilbert was angry[7]. Dawson:72-73 reports that Hilbert "dealt with [the consequences] in a positive way”, and Reid:198 reports "he began to try to deal constructively with the problem". However, neither of two of his papers published in spring 1931 cites Gödel’s work (Dawson:72-73), and Feferman concludes that "the available evidence leaves us with no clear-cut answer as to the possible influence of Gödel's work on that of Hilbert[8]. Dawson opines that Bernays found Gödel proofs difficult to “assimilate” (Dawson:73). Even Carnap met met 7 February with Gödel and confessed his work “hard to understand” (Dawson:73, Collected Works Vol. I:199). Bernays would write (18 January, 20 April, 3 May) for clarification; “he was confused in particular by the earlier finite consistency proof of Ackermann and von Neumann, proofs whose restricted applicability was only belatedly recognized” (Dawson:73)[9].
While Bernays may have found the proofs difficult, he would pass the galley prints to Jacques Herbrand (Dawson:74). On 7 April Herbrand would send Gödel off-prints of his own work, his comments about implications of the incompleteness theorems, and his suggestion for a more-general recursion schema (Dawson:74)[10]. In his return letter Gödel would state that he was not convinced that the second incompleteness theorem "contradict[s] Hilbert’s formalistic viewpoint" (Dawson 75)[11]. (Gödel would eventually present Herbrand’s suggested “general recursion” in the Princeton lectures of 1934.)
A detractor (Zermelo) and a priority challenge (Finsler)
[edit]In mid-September 1931 Gödel would encounter in Ernst Zermelo “his first and most vocal detractor . . . a very irascible person” (Dawson:75). Zermelo “thought of quantifiers as infinitary conjunctions or disjunctions of unrestricted cardinality and conceived of proofs not as formal deductions from axioms, but as metamathematical determinations of the truth or falsity of a proposition through transfinite induction . . . syntactic considerations thus played no role in his thinking” (Dawson:76). He wrote Gödel to announce that he had found “ ‘an essential gap’ in Gödel’s argument” (Dawson:76). In October Gödel, “in calm and patient terms”, replied with a 10-page letter with hopes that now Zermelo would be convinced (Dawson:76, G-G:512-513). But Zermelo continued to misunderstand, and he published his criticisms in print with “a rather scathing paragraph on his young competitor” (G-G:513). Gödel "no doubt thought it pointless to pursue the matter any further”; indeed, Carnap agreed with Gödel that Zermelo completely misunderstood (Dawson:77).
A second challenge would come a year later (11 February 1933) in the form of a priority claim by Paul Finsler citing his 1926 paper Formal proofs and undecidability (Dawson:89)[12]. In a response dated 25 March 1933 Gödel bluntly pointed out that Finsler’s proof failed (Dawson:89) and why: "But (and that is the salient point) if one tries to apply your proof to a truly formal system P, it turns out to be wrong"[13] [because] your antidiagonal sequence . . . and therefore the undecidable proposition, is never representable in the same formal system from which it starts out" (Collected Works Vol. IV:409-411). After studying Gödel’s off-prints, Finsler "retorted angrily" (Dawson:89)[14]. Gödel did not reply (Dawson:90). Years later (1970 letter not mailed), Gödel stated that "I myself did not know his paper when I wrote mine, and other mathematicians or logicians probably disregarded it because it contains [such] obvious nonsense" (cf Dawson:89)[15]; he crossed out the following ending: "This "proof" (which incidentally was not known to me when I wrote my paper) is therefore worthless..."[16].
Gödel exists recursion theory
[edit]Goldstein opines that "von Neumann did more than anyone else to disseminate the news of Gödel's accomplishments" (Goldstein:195). In 1932 continued work in recursion theory moved to Princeton N.J. with von Neumann; here student Stephen C. Kleene first heard of Gödel from von Neumann’s lectures (Dawson:71, Goldstein:195 footnote 9). Hot in pursuit of an undecidability proof, Professor Alonzo Church was expressing concern that “the incompletness theorems were somehow dependent on the particularities of formalization” (Dawson:101). As a visiting lecturer during fall 1933 into 1934 Gödel sought to dispel this notion with his lectures -- a refined version of his 1931 incompleteness proofs -- as transcribed by students Kleene and J. B. Rosser (Dawson:101)[17]. At the end of the lectures Gödel would also propose "general recursion" as suggested by Herbrand; Gödel would suggest this to Church, rather than Church’s own lambda-calculus, as a foundation for "effective computability" that would be necessary to prove undecidability (Dawson:101, cf section 9 of the lectures "General recursive functions")[18]
At this point Gödel exited further work in recursion theory (Dawson:102). In 1936 – Rosser’s paper[19] would demonstrate that simple consistency rather than ω-consistency is adequate to demonstrate incompleteness of a formal theory (Dawson:112). In October 1938 Gödel, while in New York, met Emil Post who "had also come close to obtaining the incompletness theorems" (Dawson:130). To Gödel Post outpoured his ideas and his "anticipation" of Gödel's, Church's and Turing's works, but without malice acknowledged Gödel's achievement (Dawson:131)[20]. In 1939 a full proof of the second incompleteness theorem would be published in Hilbert and Bernays 1939 (cf footnote 6 Dawson:70).
Formal systems versus the potentialities of the human mind
[edit]In a note (28 August 1963) added to van Heijenoort’s translation of Gödel’s 1931, Gödel would state that “In my opinion the term “formal system” or “formalism” should never be used for anything but this notion [A. M. Turing’s work] . . . reasoning in them, in principle, can be completely replaced by mechanical devices” (van Heijenoort 1967:616 footnote 70). This is a briefer, honed version of the first two paragraphs of his “Postscriptum” that appears after his Princeton lectures (Davis 1965:71). But he also adds that “Note that the results mentioned in this postscript do not establish any bounds for the powers of human reason, but rather for the potentialities of pure formalism in mathematics” (Davis 1965:73). Dawson reports that Gödel held this view “sincerely”: “He addressed the issue explicitly in his Gibbs Lecture of 1951[21] and his posthumous note 1972, where he disputed Turing’s contention that ‘mental procedures cannot go beyond mechanical’ ones” (Dawson:75 footnote 11)[22].
Absolutely undecidable propositions
[edit]In the context of undecidability and his 1936 proposal to reduce human calculation to the simplest imaginable behaviors[23], Emil Post stated his belief at the end of his paper, that when conclusions derived from Gödel's theorems together with Church's discovery of "recursive unsolvability" are extended to "all symbolic logics and all methods of solvability they would have to be expressed as a natural law in need of "its continual verification" (Post in Davis 1965:291). He would extend this to his unpublish(able) 1941 where he begins by attributing the phrase "absolutely unsolvable problems] to Church, and he opines that this matter was of "fundamental importance to mathematics" (Post in Davis 1965:340).
With regards to the existence of "absolutely" undecidable propositions, Gödel would opine in 1967 that Finsler "had the nonsensical aim of proving formal undecidability in an absoulte sense" and his proof was "therefore worthless and the result claimed, nametly the existence of "absolutely" undecidable propostions is very likely wrong." (unsent letter to Yossef Balas in Collected Works Vol. 5?:10-11).
Hilbert's 10th problem -- the undecidability of Diophantine equations
[edit][This section to include Goedel's important proofs re the "Diophantine equations" that introduce the notion of "arithmetical expression (proposition, relation)" and shows them equivalent to the notion of "recursive relation" that he defines in his 1931 (Theorem VII). This thereby allows him to state Theorem VIII that there are undecidable arithmetical propositions. He develops this much further in his 1934 to include equations -- he calls "Diophantine" -- of the type that students in algebra frequently encounter [24]. For example, Franzen 2005:10 gives examples such as these (the multiply-sign is implied)
- x + 8 = 5y [x = 5n-8], x2 = 2y2 [only x=0, y=0], x2+y2=z2 [ the Pythagorean triplets such as x=3, y=4, z=5], x4 + y4 = z4 [no non-zero solutions], y2=24-1 [x=1 & y=1, or x=13 & y=239], etc.
By use of his "arithmetical expessions" Goedel proves that "Thus there exists a statement about the solution of a Diophantine equation which is not decidable in our formal system" (p. 367). While it will be decidable in the next higher variable-type, there's a question there that cannot be decided, ad infinitum; "thus there can be no complete theory of Diophantine analysis . . . [and] no method of deciding relations in which both + and x occur..." (p. 370); in his 1967 Postscriptum he would invoke the "Turing machine" to make this result "definitive": "there exists no formalized theory that answers all Diophantine qustions of the form (P)[F = 0]", and "There is no algorithm for deciding relations in which both + and x occur." (p. 370). In his commentary before this paper Kleene would comment that, in connection with Hilbert's 10th problem, Matiyasevich 1970 would improve this so (P) includes only existential quantifiers (i.e. "Ex1" etc).
Notes
[edit]- ^ The “formal system” that Gödel would eventually adopt was in essence Hilbert's system. An example of this can be found in Hilbert’s 1927 address The foundations of mathematics together with a brief commentary by van Heijenoort, in van Heijenoort 1967:464ff. Gödel would use somewhat different axiom sets in his 1931 paper and 1934 Princeton lectures, but all formulations include at least the necessary axioms of logic, a for all operator, modus ponens (required for the notion of “proof”), a couple “axioms of number” and a restricted form of mathematical induction derived from Peano Arithmetic (PA), and what is now known as a “primitive recursion schema” with its various symbols to represent functions and variables and the notion of "substitution" or "composition".
- ^ This paper with commentary by van Heijenoort can be found in van Heijenoort 1967:582ff.
- ^ Also Dawson’s commentary before his un-sent 1970 letter to Yossuf Balas in Collected Works Vol. IV page 10.
- ^ Grattain-Guiness derives this supposition from Wang 1996a, 81-85: Hao Wang 1996 A Logical Journey: From Gödel to Philosophy, MIT Press, Cambridge MA. This is corroborated by the 1970 unpublished letter to Yossef Balas "Hence, if truth were equivalent to provability, we would have reached our goal. However (and this is the decisive point) it follows from the correct solution of the semantic paradoxes i.e., the fact that the concept of "truth" of the propositions of a language cannot be expessed in the same language, while provability (being an arithmetical relation) can. Hence true ≢ provable." (Gödel underlined correct twice; Collected Works Vol. IV:10).
- ^ cf Reid:196, Hilbert is using Comte as a cautionary teaching point-- Comte was a philospher who claimed that science could never discover the chemical composition of the bodies of the universe.
- ^ Details can be found in Feferman's commentary before Review of Hilbert 1931c in Collected Works Vol. 1:208ff: e.g. Bernays recounted to Reid that Hilbert was "very angry" when he said he doubted completeness of number theory, and that they had "violent arguments" concerning the foundations of mathematics.
- ^ Reid uses the phrases "somewhat angry" and then later "only angry and frustrated" (Reid:198)
- ^ Hilbert's solution was to allow the addition of a new premise ∀xA(x) to the formal system if one could show by finitary means (e.g. simple induction) that given all numerical instances for z that A(z) holds (p. 210-211): Feferman's commentary in Collected Works Vol. 1:208-213 describes the documentary chaos.
- ^ Bernays' confusion is explicable: Feferman reports that the necessity to restrict the scope of the Ackermann-von Neumann proofs was "not yet realized, and was thus a cause for puzzlement [etc] . . . (Gödel himself was cautions on the scope of finitary proofs in general, at the end of 1931h. (hIn his introduction to Hilbert and Bernays 1934, Hilbert stood firm in defense of his program [etc]", see Collected Works Vol. 1:211-212.
- ^ Herbrand’s own paper On the consistency of arithmetic was mailed to the publisher on 14 July 1931. Herbrand would die in a climbing accident on the 17th. This paper with commentary by van Heijenoort can be found in van Heijenoort 1967:618ff.
- ^ This also appears, with an explanation why, at the third-to-last paragraph of his 1931 paper.
- ^ ”Both Gödel's and Finsler's proofs, with their similarities and differences, skirt the Richard paradox without falling into it; both exploit Richard’s argument to obtain new and valid conclusions. ¶ Finsler’s paper, however, remains a sketch”; cf van Heijenoort’s commentary and Finsler's paper in van Heijenoort 1967:438ff.
- ^ Quoted from two drafts, the one that Dawson quotes from is the first; this wording is from the second.
- ^ Dawson in his commentary before the letters states it this way: "Finsler reacted angrily to Gödel's criticisms, and his subsequent papers, particularly 1944, reveal a persistent inability to understand the issues involved." The issues are "In contrast to Gödel, however, Finsler made no attempt (and saw no need) to give a precise specification of the syntax of his "formal" language"; cf Collected Works Vol. IV:406ff)
- ^ “Letter to Yossef Balas” in Collected Works Vol. IV:10)
- ^ Bottom of page 9: “Letter to Yossef Balas” in Collected Works Vol. IV.
- ^ These are sometimes called the "IAS lectures" for the Institute for Advanced Study (delivered Spring 1934); they would remain in manuscript form until published by Davis (with commentary) in Davis 1965:39ff; the lectures and postscriptum also appear, with a commentary by Stephen Kleene, in Collected Works Vol. I:338-371. See Dawson:94-96 for a good history of the founding of the IAS: chartered in May 1930, The first professors (1932) were Albert Einstein and Oswald Veblen. John von Neumann, James Alexander and Hermann Weyl joined in 1933.
- ^ Gödel did not seem to have much use for the lambda-calculus. See footnote 18 (Davis 1965:100) in Church's 1935 An Unsolvable Problem of Elementary Number Theory where Church acknowledges that Gödel urged recursion rather than lambda-calculus be used as a starting point for "effective calculability". In his 1964 Postscriptum (Davis 1965:72) he eschews both recursion and the lambda-calculus in favor of "Turing machines".
- ^ Rosser’s 1936 Extensions of some Theorems of Gödel and Church with brief commentary by Davis can be found in Davis 1965:230ff. A useful followup paper -- Rosser 1939 An Informal Exposition of Proofs of Gödel’s Theorem and Church’s Theorem -- can be found in Davis 1965:223ff.
- ^ Dawson’s story of the meeting and Post’s subsequent letter to Gödel is touching – Post was professionally isolated in the US and he suffered from manic-depression. Post’s paper was rejected for publishing in 1941, and it first appeared in print as Absolutely Unsolvable Problems and Relatively Undecidable Propositions in Davis 1965:340ff. Both the commentary by Davis 1965:338-339, and familiarity with Post’s 1921 PhD thesis Introduction to a general theory of elementary propositions (to be found with commentary by van Heijenoort 1967:264ff), would be helpful when tackling this paper.
- ^ Dawson summarizes Gödel's beliefs: "In his Gibbs lecture, Gödel addressed the question whether the power of the human mind exceeds that of any finite machine"(Dawson slide #24)and "Either … the human mind infinitely surpasses the powers of any finite machine, or else there exist absolutely unknowable Diophantine problems"; Gödel thought the former 'more likely' ”(Dawson slide #33).
- ^ Turing, he said, had disregarded that “mind, in its use, is not static, but constantly developing” (Dawson slide #34).
- ^ Move left one box, move right one box, print a single mark in occupied box, erase if marked, determine whether the box is marked or not, follow a list of instructions with "instruction jumps" allowed. The paper preceded Turing's 1936-7 by just a few months. It can be found in Davis 1965:288ff.
- ^ More formally these are "Diophantine questions" of the form (P)[F = 0] where [F=0] is a "polynomial with integral coefficients" and (P) is "a sequence of logical quantifiers" such as his examples (using ∃, ∀ in place of E and ( )) and we're after integer solutions to the equations: "(∃x1)(∃x2)...(∃xn)(F(x1,...xn) = 0 says that there is a solution; ∀x3(∃x1)(∃x2)(∃x4)...(∃xn)(F(x1,...,xn) = 0 says that, for any assigned value of x3, the resulting equation has a solution" "Collected Works Vol. 1":363-364.
References
[edit]- ed. Solomon Feferman et al., 1986─2003, Kurt Gödel: Collected Works (5 vols.), ed. Solomon Feferman et al. Oxford University Press.
- http://www.easychair.org/FLoC-06/dawson_goedel_keynote_floc06.ppt Dawson slides
- I. Grattain-Guinness, 2000, The Search for Mathematical Roots 1870-1940, Princeton University Press, Princeton NJ, ISBN 0-691-05858-X (pbk.:alk. paper)
- Martin Davis, 2000, Engines of Logic: Mathematics and the Origin of the Computer, W. W. Norton & Company, NY, ISBN 0-393-32229-7 pbk.
- Martin Davis ed., 1965, The Undecidable: Basic Papers on Undecidable Propositions, Uinsolvable Problems and Computable Functions, Raven Press, NY, no ISBN.
- Rebecca Goldstein, 2005, Incompleteness: The Proof and Paradox of Kurt Gödel, W. W. Norton & Company, NY, ISBN 0-393-05169-2.
- Jean van Heijenoort, 1967, From Frege to Gödel: A Source Book in Mathematical Logic, 1979-1931 (3rd printing 1976), Harvard University Press, Cambridge, MA, ISBN 0-674-32449-8 (pbk).
- Constance Reid, 1996, Hilbert 2nd edition (first edition 1965), Springer-Verlag New York, Inc., NY, ISBN 0-387-94674-8.
Comments
[edit]Bill, thanks for doing that. I'll try to add some comments in the next day or so. For now, I'll just say I'd hoped to not have to hear any more about Wittgenstein ;-) 66.127.53.162 (talk) 11:12, 23 April 2010 (UTC)
- Very interesting -- I've used some of this. Now I need to get the Gibbs lecture. (I have only Volume I of Collected Works Publications 1929-1936). Amazing that Dawson inserted the Yossef Balas slides. I was reading this very exerpt today off my poor copy of the pages, wondering what to include. (This letter and Dawson's commentary is very intersting indeed.) Bill Wvbailey (talk) 21:57, 23 April 2010 (UTC)
- Murawski discusses Gödel's work on arithmetic truth as antecedent to the incompleteness theorem. 66.127.53.162 (talk) 22:37, 23 April 2010 (UTC)
- I haven't been able to open this. My "Adobe distiller" goes batshit. Bill Wvbailey (talk)
- Hmm, you could ask the author about it (his email is on his homepage). Here is an article about the Gibbs lecture. Sorry my address keeps changing, I'm messing with my hardware setup. 69.111.194.5 (talk) 02:16, 24 April 2010 (UTC)
- I haven't been able to open this. My "Adobe distiller" goes batshit. Bill Wvbailey (talk)
- Thanks for the link to Feferman's paper; I sat down and read it in one gulp. When I read the title as it came off the printer I immediately thought of Post's comments (in his very long footnote 1) at the beginning of his 1941 unpublished-until-1965 "Absolutely Unsolvable Problems and Relatively Undecidable Propositions: Account of an Anticipation". The footnote begins, and ends as follows:
- ”1. The phrase "absolutely unsolvable" is due to Church who thus described his problem in answer to a query of the writer as to whether the unsolvability of his elementary number theory problem was relative to a given logic [he refences: Church 1936, An unsolvable problem in elementary number theory]. By contrast, the undecidable propositions in this and related papers are undecidable only with respect to a given logic. A fundamental problem is the question of the existence of absolutely undecidable propositions, that is, propositions which in some a priori fashion can be said to have a determined truth-value, and yet cannot be proved by any valid logic. An attempt at formulating such a proposition appears in the appendix . . .The fundamental new thing is that for the combinatory problems [e.g. Gill's problem of "tag"] the given set of instruments is in effect the only humanly possible set. (Davis 1965:340ff)
- There's an additional footnote 12 where he stays "the creativeness of human mathematics has as counterpart inescapable limitations thereof -- witness the absolutely unsolvable (combinatory) problems [etc]" (p. 345)
- He begins his Appendix coherently enough:
- "The unsolvability of the finiteness problem for all normal systems, and the essential incompleteness of all symbolic logics, are evidences of limitations in man's mathematical powers, creative though these may be. They suggest that in the realms of proof, as in the realms of process, a problem may be posed whose difficulties we can never overcome; that is that we may be able to find a definite proposition which can never be proved or disproved. This theme will protrude itself every so often in our more immediate task of obtaining an analysis of finite processes" (Davis 1965:418).
- He begins his Appendix coherently enough:
- . . . But then the rest of his Appendix reads like the notebook-ending of F. Scott Fitzgerald's unfinished (because he died) novel The Last Tycoon. Because the paper was rejected in 1941 Goedel probably wasn't aware of Post's musings [we'd need the correspondences to find out]. In his brief commentary before the paper Davis notes that the nettlesome problem of "tag" that Post introduces was indeed proven unsolvable by Marvin Minsky in 1961. Was Goedel aware of any of this activity? Dawson does speculate: in 1970 Goedel was quite sick; Dawson reports he had a "mental crisis", and Dawson speculates he was unaware of Matijasevich's proof of the unsolvability of Hilbert's 10th problem. Dawson is struck by this considering "it concerned a decision problem for Diophantine equations that was related to unpublished results he had obtained years earlier as corollaries to his incompletness theorems. (Like other mathematicians before Matijasevich, Goedel had overestimated [!] the problem's difficulty . . .) . . . he seems never to have mentioned it in any subsequent correspondence"(Dawson:238)). There's certainly a lot here to munch on. Bill Wvbailey (talk) 18:05, 24 April 2010 (UTC)
- Bill: I can convert that file to PDF and email it to you if you want. Just let me know on my talk page. — Carl (CBM · talk) 11:48, 24 April 2010 (UTC)
- Did you have any luck with the pdf conversion? I got a bunch of error messages from ps2pdf and I don't know if Acrobat can read the pdf that came out of it. 69.228.170.24 (talk) 08:27, 26 April 2010 (UTC)
- The more aggressive way to fix broken PS files is to have ghostscript render the file as a series of bitmaps, using the command
- gs -sDEVICE=psmono -dNOPAUSE -r600 -sOutputFile=OUTPUT.ps INPUT.ps
- (Type 'quit' at the gs prompt when it appears.) This will result in the same sort of file you would get by scanning the original PS into bitmaps using a 600dpi scanner. Then you can convert the resulting ps to pdf with ps2pdf and it usually works fine. The resulting file is not very attractive on-screen but it should print out reasonably well. The benefit of this is that ghostscript will do the best it can to render broken files.
- The more aggressive way to fix broken PS files is to have ghostscript render the file as a series of bitmaps, using the command
- Did you have any luck with the pdf conversion? I got a bunch of error messages from ps2pdf and I don't know if Acrobat can read the pdf that came out of it. 69.228.170.24 (talk) 08:27, 26 April 2010 (UTC)
- Bill: I can convert that file to PDF and email it to you if you want. Just let me know on my talk page. — Carl (CBM · talk) 11:48, 24 April 2010 (UTC)
- In this case, evince is OK with a direct ps2pdf of the original, but xpdf is not. Both are happy with the bitmapped version, of course. If you don't have access to a computer with ghostscript, I can email you to fixed version. — Carl (CBM · talk) 12:32, 26 April 2010 (UTC)
- I was able to open both Murawski and the Franzen .ps below using Acrobat 8: I saved the .ps files to the desktop and then opened them with Acrobat. I'm supposing that the Acrobat reader tried to get the use of the shared "distiller" from Acrobat 8 but Acrobat 8 had claim to it. Murawski looks better in print than on the screen. If you need pdf cc's lemme know. BillWvbailey (talk) 14:49, 26 April 2010 (UTC)
- I can read the .ps's ok with evince. I'll have to remember the gs bitmap trick in case such an issue comes up again. 69.228.170.24 (talk) 18:27, 26 April 2010 (UTC)
- In this case, evince is OK with a direct ps2pdf of the original, but xpdf is not. Both are happy with the bitmapped version, of course. If you don't have access to a computer with ghostscript, I can email you to fixed version. — Carl (CBM · talk) 12:32, 26 April 2010 (UTC)
- Just want to say thanks to Bill for this monumental effort. Haven't found time to actually read it all, but it's very valuable to have it around. --Trovatore (talk) 22:08, 3 May 2010 (UTC)
History section
[edit]I made a very rough attempt to start a history section tonight. Wvbailey's notes above are invaluable for this. However, I tried to keep the text of the article focused on the incompleteness theorems, rather than on Gödel in general.
Most of the things I added tonight are already sourced above, and I will work on adding references for them in the article.
One thing I don't have a source about is the planned second part of the paper, which never materialized. Did Dawson or Wang have anything to say about it?
A second thing I don't have a source in mind for is any response by Hilbert. This will be a complicated issue to cover. — Carl (CBM · talk) 01:27, 2 May 2010 (UTC)
Nice job with the new section. The planned Part II is mentioned by Feferman[4] p. 10. It wasn't written in part because the second incompleteness theorem turned out to be uncontroversial. I think one response by Hilbert was the proposal of ω-logic. Some other comments:
- His original goal was to obtain a positive solution to Hilbert's second problem by obtaining a finitary consistency proof for arithmetic. I thought he was working on the consistency of analysis.
- Ackermann and von Neumann had previously established a consistency proof for a limited theory of arithmetic I think that refers to Presberger arithmetic, which should be mentioned.
- Gödel gave a series of lectures on his theorems at Princeton in 1933–1934 I don't have a source for this and would want to find one before including it, but I heard that von Neumann gave a seminar on the incompleteness theorems in Göttingen immediately on receiving Gödel's paper; the other members of the Hilbert school quickly accepted the result, and basically closed down the program.
- Dawson 1984 discusses reception of the theorems in possibly more depth than his Gödel biography does, so might be worth looking into. 69.228.170.24 (talk) 02:59, 2 May 2010 (UTC)
- Thanks, that's very helpful. I agree the sentence on previous work by Ackermann needs to be clarified.
- The terms "analysis" and "arithmetic" are somewhat interchangeable; "analysis" in this sort of context refers to the first-order theory now called second-order arithmetic. However we can follow whatever the reference actually says.
- Wvbailey mentions ω-logic above, too; I was not sure how to phrase the Hilbert school response so I didn't include it yet. — Carl (CBM · talk) 03:04, 2 May 2010 (UTC)
- There is some discussion of Hilbert's response at [5] p.13 but nothing about ω-logic there. 69.228.170.24 (talk) 04:30, 2 May 2010 (UTC)
- Maybe I was thinking of this, p. 22, but it doesn't say much. ("Another option he [Bernays] considered was an extension of the notion of an axiomatic theory by a finitary version of the ω-rule proposed by Hilbert [1931a; 1931b].") 69.228.170.24 (talk) 04:43, 2 May 2010 (UTC)
- Re analysis vs arithmetic, apparently the consistency of first-order arithmetic was considered already proved by Ackermann in 1928,([6] p. 94) so Gödel was trying to prove the consistency of analysis using arithmetic. I guess that's what you meant about Ackermann (looking at the article on Presberger arithmetic, its consistency was proved by Presberger). von Neumann found a mistake in Ackermann's proof later.([7] p. 9) but I don't yet understand this (will try to read it more). 69.228.170.24 (talk) 05:06, 2 May 2010 (UTC)
- I added a little to try to clarify the Ackermann consistency proof, and added some references.
- Re closing the program in Goettingen, if von Neumann did speak there about Goedel's results that would be nice to include. The changes to the research program, however, were more likely due to the Nazi purge in 1933 that displaced many of the key figures there, including Bernays. — Carl (CBM · talk) 12:32, 2 May 2010 (UTC)
- Thanks, the new additions help. Should Presberger arithmetic also be mentioned? I think it was part of the reason for the Hilbert school's optimism in expecting stronger systems like PA or set theory to also be complete. 69.228.170.24 (talk) 04:52, 3 May 2010 (UTC)
- Re closing the program in Goettingen, if von Neumann did speak there about Goedel's results that would be nice to include. The changes to the research program, however, were more likely due to the Nazi purge in 1933 that displaced many of the key figures there, including Bernays. — Carl (CBM · talk) 12:32, 2 May 2010 (UTC)
---
RE Hilbert's response: In Feferman's commentary before "Review of Hilbert 1931" there's everything you'll need, and probably everything that is known at this time, about Hilbert's reaction to Goedel: "In all, then, the available evidence leaves us with no clear cut answer as to the possible influence of Goedel's work on that of Hilbert" (Collected Works Vol. I:208-213). As for Hilbert's "omega-rule", this is also discussed there in detail. I had to go to Reid (Hilbert's biographer) to get what details she could get from Bernays.
Here's how Goedel thought about what he was doing: "his attempt to further Hilbert's program by giving a consistency proof of analysis relative to arithmetic" (Dawson's wording in commentary before "Letter to Yossef Balas" in Collected Works Vol. IV:9). Here's Goedel's words: "The occasion for comparing truth and demonstrability was an attempt to give a relative model-theoretic consistency proof of analysis in arithmetic" | (For, an arithmetical model of analysis is nothing else but an arithme(tical ε-relation satisfying the comprehension axiom:)" (letter to Yossef Balas). Bill Wvbailey (talk) 15:40, 2 May 2010 (UTC)
- The above paragraph is strongly corroborated by the paper (discovered by our mystery IP) written by Wang http://www.shsu.edu/~mth_jaj/math467/godel_article.pdf . It expands a bit on the above about the comprehension axiom, and is the best summary I've read. Wang was interviewing Goedel so this is a precis of Goedel's words: "In the summer of 1930, Goedel began to study the problem of proving the consistency of analysis. He found it mysterious that Hilbert wanted to prove directly the consistency of analysis by finitst method. his idea was to prove the consistency of number theory by finitist number theory, and prove the consistency of analysis by number theory, where one can assume the TRUTH of number theory, not only the consistency. The problem he set for himself at that time was the relative consistency of analysis to number theory . . . ¶ He represented real numbers by formulas (or sentences) of number theory and found he had to use the concept of truth for sentences in number theory in order to verrify the comprehension axiom for analysis. He quickly ran into the paradoxes (in particular, the Liar and Richard's) connected with truth and definability. He realized that truth in number theory cannot be defined in number theory and therefore his plan of proving the relative consistency of analysis did not work" [TRUTH capitalized for emphasis, p. 654].
- Thanks. Please feel free to expand or correct things in the article that seem bad to you. There's a lot of work to do, particularly in the "criticism" section, which is too vague and lacks enough references at the moment. I also think there should be a paragraph explaining how Goedel intentionally avoided talking about "truth" in his paper to minimize possible philosophical criticisms; I know this can be sourced, but I don't remember exactly where. — Carl (CBM · talk) 17:14, 2 May 2010 (UTC)
- Murawski (url above) p. 8 quotes a 1984 paper by Feferman ("Kurt Gödel, Conviction and Causation") that's not on Feferman's web site or JSTOR--maybe your library has it. (Added: it looks like it's in Feferman's book In the Light of Logic which I don't have but which is excellent.) 69.228.170.24 (talk) 23:10, 2 May 2010 (UTC)
I fleshed out the "criticism" section: First of all, I time-orded the paragraphs and dated the events to which they pertain. I fleshed out the text using my "quotations" style, which could be emended into a precis style (not by me: I'm uneasy with this precis style because of strict rules about plagarism that I learned in my undergrad days, so I stick with quotations). I added something I remember reading about Wittgenstein's (understandable) misinterpretation of something Goedel wrote (a summary piece), and I know exactly where that misinterpretable-wording is in the primary reference (it surprised me too; it seems to confuse "true" with "provable"), but I can't quite remember the secondary reference-source, so I need to hunt this down. This is one of the footnotes that could be turned into in-line cites when the references are updated. Bill Wvbailey (talk) 00:26, 3 May 2010 (UTC)
- Citations are good, I'm not sure the chronological ordering really helps, and normal prose writing that summarizes facts is fine (just cite where the facts are from). I feel like the criticism section is dwelling too much on relative trivia. Have you looked at Dawson's article on the theorems' reception? 69.228.170.24 (talk) 03:38, 3 May 2010 (UTC)
I made another pass on the criticism section this morning. I am getting more satisfied with the Finsler and Wittgenstein sections, but the Zermelo section is incomplete. Here are a few of my personal ideas about writing; you don't have to agree with them but at least you can see my motivations:
- I think it's better to avoid too much personalization of issues. Sure, everyone is human, and people get emotional sometimes. But if we describe Zermelo as "irascible", it only makes our prose appear (more) biased.
- I like to include some details about the actual mathematics, rather than just saying that each side thought the other side was wrong. For example, "Finsler's methods did not rely on formalized provability, and had only a superficial resemblance to Gödel's work (van Heijenoort 1967:328)." This makes it much easier to understand what the argument was about. The reader can figure out which side she thinks was "right".
— Carl (CBM · talk) 12:21, 3 May 2010 (UTC)
- (For the most part . . .) I'll let you do the entries; I'll just feed you my opinions-- our writing styles are too different, methinks. (E.g. I'm a biographer/historian that likes the personalities.) I do agree that the "actual math" is useful especially if it provides a "twist" or "alternate view" of the content in the article, the editorial question becomes "how much". Hence I suggest we expand the really important stuff about the "comprehension axiom" and about "true <> provable" which Goedel wrote in his letter to Balas (and also see next paragraph about arithmetical predicates). Au contraire to mystery-IP, I strongly urge all history to include strict time order and date references (if not then you end up with Grattain-Guiness's hard to follow mish-mash). And I don't like precis style because it usually erases the source-trail. So anyway...
- Speaking of really important but missing in the article, (and the most interesting to me personally) is Goedel's "arithmetical predicate" discovery (the Diophantine-equation discovery) of theorems VII, VIII and IX and his expansion into his 1934. This from the Wang paper: "Shortly afterward [following von Neuman's question] Goedel, to his own astonishment, succeeded in turning the undecidable proposition into a polynomial form preceded by quantifiers (over natural numbers). At the same time but independently of this Goedel also discovered his second theorem..."(p. 655). This is greatly expanded in Davis 1958 (Dover edition), but it's pretty chewy (in particular his Appendix 2 re Hilbert's 10th). But I found Kleene's 1952 treatment of "arithmetical" more accessible (and to us Collatz-conjecture folk the astonishing result (1948) by Julia Robinson that the predicate | [divides evenly] and successor ' can replace + and x when defining aritmetical predicates). BillWvbailey (talk) 14:41, 3 May 2010 (UTC)
- Cool, the section continues to get better. Re chronological ordering, I think there are several separate topics in the section and it's reasonable to keep them separate, but staying mostly-chronological within each topic makes good sense (and I think reflects the current version). IIRC, Gödel's correspondence with Zermelo is discussed at some length in van Heijenoort's book. Dawson 1984 (JSTOR 192508) (full wiki-citation further up in the talk page) may also say something about it. I think it may be worth mentioning some other antecedents to the incompleteness theorem, like Emil Post's work on the problem, and some previous hints of unsolvable problems, also mentioned way further up (in the discussion from a few months ago). Hilbert was so influential that we now think of his belief of "no ignorabimus" (why does that sound like a Harry Potter spell?) as universally accepted and the first incompleteness theorem as an utterly astonishing bombshell that turned everything upside down. Gödel was of course the one who settled the matter, but it seems to me that not everyone had Hilbert's faith in completeness. Re biography and personality: the article Kurt Gödel can also use some improvement. I edited it a little a few months ago but I think I got reverted by someone. 69.228.170.24 (talk) 15:04, 3 May 2010 (UTC)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e7/African_daisy_%28Osteospermum_sp._%27Pink_Whirls%27%29.jpg/200px-African_daisy_%28Osteospermum_sp._%27Pink_Whirls%27%29.jpg)
- Yes, you're right (I thought about this on the way to buy some more osteospermum for our walkway) -- only within a section should we stick to time-order.
- RE more biography of Goedel, Finsler, Zermelo, Post etc. -- yes, some of this (esp. the Finsler stuff) probably can be reused in those sections. When this is done maybe we attack those articles; with new writings (G-G, the Goedel Collected Works etc.) new info is coming forth.
- About Post -- I haven't encountered any evidence that Post, either before or after 1931, had influence on Goedel. But I'm waiting for a paperback cc of Collected Works Vol. II, and because of the unbelieveable cost for the letters-volumes I'll have to take a trip to the library (and hope the missing hardbound volumes have reappeared). What I can see off the googlebooks (reading around its absent pages) is the two met in 1938, when as mentioned in the sections above, Post told Goedel that he had "anticipated Goedel's results" but for various reasons [poverty, professional isolation, mental health] failed to bring them to fruition. But did their exchange of letters affect Goedel's thinking about e.g. "absolutely unsolvable problems"?
- RE Zermelo -- this from Grattain-Guiness:
- "[Imitating a marvellous recent foray 1930a ... deep into Cantor's transfinite ordinals, he offered in Zermelo 1932a a theory of infinitely long proofs and thereby hoped to show that all true mathematical propositons were provable in this extended sense. ¶ In his proof Zermelo followed the algebraic line in reading quantification in terms of infinite con- and disjunctions, attacked model theory, and left trugh-values unexplained. The details are not our concern; the point is that he rejected the normal preference for finitude in proof, and especially the message of the lecture 'On the existence of undecidable arithmetical theorms in formal systems of mathematics' which was given by Goedel" (p. 512, bottom).
- There's a lot more good stuff on p. 513; if you want I can type it in too. Bill Wvbailey (talk) 17:25, 3 May 2010 (UTC)
- I don't have reason to expect that Post influenced Gödel. But in a section about the history of the theorem, it's appropriate to mention other attention that had been given to the problem. The Apollo moon landing was a great accomplishment, but the Russians (who failed to get there first) at least believed that the moon existed. The incompleteness theorem is like Gödel being first to reach the moon, when the Hilbert school not only didn't get there first, but also strongly believed (and were trying to prove) that the moon didn't exist. So discussing Post, Finsler, etc is in some sense asking: ok, Gödel was the first to land on the moon, but did everyone else go as far as disbelieve the moon's existence the way Hilbert did? Was anyone else trying to get there? Of course I'm coming from a contemporary perspective that has been completely shaped by Gödel's impact, but from this viewpoint, I've never been able to understand why the Hilbert program had any expectation that mathematics could be proved complete. 69.228.170.24 (talk) 18:04, 3 May 2010 (UTC)
- It was a combination of many factors:
- Hilbert's consistency proof for Euclidean geometry in 1899.
- A very naive understanding of formal logic – it took until the 1950s for the distinctive features of first-order logic to be generally understood. In the 1900s–1930s, the distinction between first-order and second-order semantics was so poorly understood that even asking how they differed would have led to confusion. This is despite knowledge of the Lowenheim–Skolem theorem.
- Combining 1 and 2, people didn't realize that although arithmetic can be reduced to geometry in a general sense (by constructing lengths with a ruler and compass), first-order Peano arithmetic is in some sense diametrically opposed to complete axiomatizations of geometry
- A lingering influence of logicism, even among formalists. The logicists argued all of mathematics can be reduced to logic. The standard counterargument is that certain axioms, such as the axiom of infinity, are not "logical". This still leaves open the possibility that all of mathematics can be reduced to some set of (non-logical) axioms. I would guess that many undergraduate math majors still have this belief.
- An affinity for finitism that made it difficult to appreciate the utility of semantic reasoning (this is one reason the completeness theorem was not obtained even when all of its pieces were in place). Although Gödel's proof is syntactical, he arrived at it by investigating semantic considerations and then washing away the semantical parts.
- A flawed consistency proof by Ackermann was accepted as correct, leading to false conclusions about what other things were likely to be provable. Even when von Neumann corrected the proof, the fact that the corrected version was only valid for arithmetic without induction was not understood at the time. This is related to #2; people did not understand the importance of induction axioms for increasing the strength of arithmetical theories.
- A perceived need to argue against Brouwer and his new circle of intuitionists
- The general slow pace of mathematical progress
- It was a combination of many factors:
- Viewed in hindsight, although Gödel obtained results that others were not yet able to obtain, he was not that far ahead of the curve. Tarski was working on aspects of incompleteness, and the Hilbert school was certain to eventually realize the errors in some of their proofs.
- I agree it would be nice to mention Post and Tarski in more detail, as example of researchers who were working in vaguely the same direction as Gödel. — Carl (CBM · talk) 19:15, 3 May 2010 (UTC)
- Thanks, that was enlightening. I think the axioms of Euclidean geometry and Peano arithmetic were considered obviously true, which would mean they are consistent, and one can have reasonable hope that any obviously true proposition (e.g. the consistency of these axioms) should be provable. I think Getnzen's proof could be presented as finitary combinatorics (using induction on finite trees), though not as finitary arithmetic (induction only allowed on natural numbers). I'm still not sure how that leads to expecting completeness though. Many propositions have no obvious truth or clear meaning, so the above consideration wouldn't seem to require them to be provable. 69.228.170.24 (talk) 03:01, 5 May 2010 (UTC)
- I agree it would be nice to mention Post and Tarski in more detail, as example of researchers who were working in vaguely the same direction as Gödel. — Carl (CBM · talk) 19:15, 3 May 2010 (UTC)
Why nobody else got there first
[edit]To add to what Carl wrote above, I've copied some of the salient stuff from above. These are in Goedel's own voice:
- 7 December 1967: In a letter to Hao Wang Goedel concluded that the failure to discover the completeness theorem (i.e. the theorem of his doctoral thesis) was indeed surprising. Davis opines that "there was little novelty in his methods, all perfectly well known to logicians at the time". But Davis [Davis 2000] goes on to apply this failure more widely than to the specific completeness theorem under discussion:
- "The completeness theorem is indeed an almost trivial consequence of [Skolem 1923b]. . . . This blindness . . . . of logicians is indeed surprising. But I think the explanation is not hard to find. It lies in a widespread lack, at that time, of the required epistemological attitude toward metamathematics and toward non-finitary reasoning . . . . [The easy] reference from [Skolem 1923b] is definitely non-finitary, and so is any other completeness proof for the predicate calculus. Therefore these things escaped notice or were disregarded" (Davis:115 quotes the italicized phrase and in footnote 6 references Dawson:58, who in turn references Hao Wang in a letter from 7 Dec 1967).
As to why others had not arrived at the incompleteness proof first, Gödel would blame "the philosophic prejudices of our times 1. nobody was looking for a relative consistency proof because [it] was considered axiomatic that a consistency proof must be finitary in order to make sense 2. a concept of objective mathematical truth as opposed to demonstrability was viewed with greatest suspicion and widely rejected as meaningless."(Letter to Yossef Balas in Collected Works Vol. IV:10).
Why Goedel didn't work on "logic" (recursion theory) afterwards Goedel's shift in interest away from logic after ca 1946
[edit]This is from mystery-IP's Wang paper. (BTW: I find this paper to be extremely useful (Wang 1981:653-659)). Per footnote #4 on page 656: Wang has been hanging out with Goedel at his house in Vienna, and he's going to the (sparsely-attended) lectures Herr Prof is offering on "Axiomatic Set Theory":
- "Probably in 1937, Goedel told Professor Wang that after the incompleteness theorems more work in the general area of mathematical logic would not make much difference: "Jetzt, Mengenlehre"." [Bill's attempt at translation: "Now, [it's] set theory"
or "This is it!: Set theory"]
Bill Wvbailey (talk) 01:58, 4 May 2010 (UTC)
- I think that is also in Dawson's biography. Your first translation is accurate. 69.228.170.24 (talk) 01:26, 5 May 2010 (UTC)
I also found this in the above paper:
- "Goedel, encouraged by the successful analysis of the invariant concept of computability, suggests looking for invariant notions of definability and provability. From both this lecture and the 1947 paper one gets the clear impression that Goedel was interested only in really basic advances" (boldface added, cf Wang 1981:658 footnote 10)
Bill Wvbailey (talk) 17:36, 5 May 2010 (UTC)
---
- I don't know that the section title is quite accurate. The Dialectica translation was developed by Goedel to give a consistency proof of arithmetic using a form of generalized recursion theory. Whatever classification this has, it isn't set theory. — Carl (CBM · talk) 01:49, 5 May 2010 (UTC)
I changed the title. Some deep scouring of sources indicates that Goedel's Dielectica results were achieved in 1942 and delivered in lectures at Yale and Princeton (cf Wang 1981:657). (They were published in German in 1958 (Bernay's 70th birthday), and revised/republished by Goedel in 1972.) While Moore opines that "Cantor's continuum problem served as one of the principal and periodic forci for Goedel's research from 1935 until his death more than four decades later" (Vol. II:154), Wang says that after his 1943 axiom-of-choice proof, and although "the method looked promising toward getting also the independence of CH, [he] developed a distaste for the work and did not enjoying doing it(Wang:657). He then made a transition toward "mathematical" philosophy (Wang:657-658, cf the Gibbs lecture, a paper RE Carnap "mathematics is not syntax"), with a detour into mathematical physics. His contributions in logic thereafter was mainly revisions and notes.
From the listing below (derived from Completed Works Vol.s I and II and Wang 1981), the four basic interests I found are:
- logic L (1929-1933, 1934-1936, 1944-1946, revisions 1958, 1963-1972),
- geometry G (1933),
- set theory ST (1938-1940, 1947),
- physics Phy (1947-1952),
- philosophy Phil (1947-onward)
- analysis A (posthumous?)
- L: 1929 -- "On the completness of the calculus of logic"
- L: 1930 -- "The completeness of the axioms of the functional calculus of logic"
- L: 1930b-- "Some metamathematical resulsts on completeness and consistency"
- L: 1931 -- "On formally undecidable propositions of Principia mathematica and related systems I" [note added 1963]
- L: 1932 -- "On the intuitionistic propositonal calculus"
- L: 1932a-- "A special case of the decision problem for theoretical logic"
- L: 1932b-- "On completeness and consistency"
- L: 1932c-- "A property of the realizations of the propositional calculus"
- L: 1933 -- "On Parry's axioms" [relevance logic]
- L: 1933a-- "On independence proofs in the propositional calculus"
- G: 1933b-- "On the isometric embeddability of quadruples of points of R3 in the surface of a sphere"
- G: 1933c-- "On Wald's axiomatization of the notion of betweenness"
- G: 1933d-- "On the axiomatization of the relations of connection in elementary geometry"
- L: 1933e-- "On intuitionistic arithmetic and number theory"
- L: 1933f-- "An interpretation of the intuitionistic propositional calculus"
- G: 1933g-- "Remark concerning projective mappings"
- G: 1933h-- "Discussion concerning coordinate-free differential geometry"
- L: 1933i -- "On the decision problem for the functional calculus of logic"
- L: 1934 -- "On undecidable propositions of formal mathematical systems" [Princeton lectures, Postscriptum added 1964]
- L: 1936a-- "On the length of proofs" ["speed-up theorem"]
- ST: 1938 -- "The consistency of the axiom of choice and of the genralized continuum hypothesis"
- ST: 1939 -- "The consistency of the generalized continuum hypothesis"
- ST: 1939a -- "Consistency proof for the generalized continuum hypothesis"
- ST: 1940 -- "The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory
- ST: 1941 -- [a general consistency proof of the axiom of choice: Wang 1981:657]
- L: 1942 -- [Yale/Princeton lectures -- Dielectica -- "interpretation of inuitionistic number theory by primitive recursive functionals" Wang 1981:657]
- ST, L: 1943 -- [proof of the independence of the axiom of choice in the framework of (finite) type theory, cf Wang 1981:657]
- L: 1944 -- "Russell's mathematical logic" [in particular: RE ramified type theory, written 1942-1943]
- L: 1946 -- "Remarks before the Princeton bicentennial conference on problems in mathematics" ["absolute" demonstrability and definability, "completely absolute" d. and d.]
- ST: 1947 -- "What is Cantor's continuum problem?" [version 1, see 1964]
- Phy: 1949 -- "An example of a new type of cosmological solutions of Einstein's field equations of gravitation"
- Phy: 1949a-- "A remark about the relationship between relativity theory and idealistic philosophy"
- L, Phil: 1951 -- Gibbs lecture at Brown: "Some basic theorems on the foundations of mathematics and their philosphical implications" [cf Wang 1981:658 fn 11]
- Phy: 1952 -- "Rotating universes in general relativity theory"
- L, Phil: 1950's -- "Is mathematics sytax of language? #1, #2" [two unpublished efforts]
- L: 1958 -- "On a hitherto unutilized extension of the finitary standpoint" [1st published version of Dialectica paper, in German; see 1942 Yale/Princeton lectures]
- L: 1963 -- "Note added to 1931 "On formally undecidable proposiitons of Principia mathematica and related systems I" [Vol. I]
- ST: 1964 -- "What is Cantor's continuum problem?" [version 2 of 1947 paper]
- L: 1964 -- "Postcriptum (3 June 1964)" to 1934 "Undecidable Propositions of Formal Mathematical Systems" [Princeton lectures, Vol. I]
- L: 1972 -- "On an extension of finitary mathematics which has not yet been used" [2nd version of Dialectica paper, in English]
- L: 1972a-- "Some remarks on the undecidability results"
- A: 1974 -- "[Remark on non-standard analysis]" [RE infinitesimals]
This doesn't include reviews that he wrote. To be thorough we also need his unpublished work alluded to by Wang (see all the footnotes on page 658-659. Bill Wvbailey (talk) 17:36, 5 May 2010 (UTC)
- I'd say most of the above doesn't have terribly much to do with the incompleteness theorem. It could be useful for a more extensive Gödel bibliography. Akihiro Kanamori's historical articles about Gödel's work in set theory look very good[8][9] if you're interested in that sort of thing. The second one helped motivate set theory for me as having something to do with arithmetic (it had always seemed like a beautiful but essentially bogus subject before). It might be worth adding something to this article about the assertion in the incompleteness paper that "the undecidable propositions constructed here become decidable whenever appropriate higher types are added", but I'm not sure how to go about it. 69.228.170.24 (talk) 04:47, 6 May 2010 (UTC)
RE relevance: Certainly we could eliminate the geometry and physics from the reading list. But I'm not so sanguine about the irrelevance of the published and unpublished "logic", "set theory", and "philosphy" papers. My sense is that Goedel wanted to resolve Hilbert's 2nd problem once and for all -- philosphically and mathematically (for all systems no matter how they're assembled, including "mechanisms", or otherwise there were indeed "absolutely undecidable Diophantine problems" (cf Gibbs lecture)). In other words, the "incompleteness theorems" didn't end for Goedel in 1934. The reviewer below agrees. What surprised me in the list was: (i) his work on intuitionistic logic through the 10 years 1932-1942 [why?], (ii) his 1946 "Russell type-theory" paper (and here I thought the ramified type-theory was dead after the 2nd edition of PM) [what's going on?], (iii) the "absolute demonstrability" address/paper, (iv) Goedel's ready willingness to accept "mechanism" [is this true? seems to be with his 2 addenda to his 1931, but I need the full Gibbs lecture]. This review of the 2002 Hofstadter version of Nagel-Newman's classic Goedel's Theorem, http://www.ams.org/notices/200403/rev-mccarthy.pdf, cites both the Gibbs lecture and the 1946 "absolute demonstrability" lectures, and also indicates that Goedel's set theory work may have been part of his broader plan: "At one point Gödel speculated that “it is conceivable that every proposition expressible in set theory is decidable from the present axioms plus some true assertion about the largeness of the universe of sets,” and in his Gibbs Lecture he considered a strategy for introducing new axioms of the latter sort." My worry isn't irrevance; rather, continued pursuit may put me at risk of committing O.R. offenses.
RE decidabilty with introduction of higher type: I agree with you but I don't have the technical ability, at least at this time; I think I understand it intuitively but would probably foul it up in the details. Maybe Carl can help. BillWvbailey (talk) 16:30, 6 May 2010 (UTC)
- Goedel thought that adding enough large cardinal axioms would decide everything in set theory? Do set theorists believe that these days? Maybe it's true, but it would take infinitely many such axioms and they would not be recursively enumerable, so what's the point? You could do the same thing in arithmetic (see true arithmetic). And of course the more complex ones would be completely beyond any possibility of human understanding. He can't have possibly meant adding just one axiom, because of the first incompleteness theorem. 69.228.170.24 (talk) 06:59, 7 May 2010 (UTC)
- It doesn't sound so much that Goedel thought that; he apparently thought it could be true.
- As regards set theorists today: It can be proved that large-cardinal axioms of the sort we know of cannot possibly decide the continuum hypothesis. That's because they are preserved under small forcing — that is, forcing where the size of the partial order is less than the cardinal in question — and such forcings are sufficient to make CH either true or false.
- In fact W. Hugh Woodin has an abstract definition of "large-cardinal property" in general, according to which one can prove that a consistent large-cardinal axiom of that sort cannot decide CH.
- However Woodin's definition is not universally accepted. John Steel says that large-cardinal axioms are "natural markers of consistency strength", and that it is "not absurd" that such a marker might decide CH one way or the other. (That's a quote from a personal conversation — I don't know that it could be sourced.)
- As to what the "point" is, given that of course the set of axioms would not be r.e., personally I think it would be very interesting, if true, that any true set-theoretic proposition whatsoever could be proved simply from some natural marker of consistency strength. Offhand it sounds very unlikely that that could be true, but if it were, it would be remarkable and not at all pointless. --Trovatore (talk) 08:45, 7 May 2010 (UTC)