Wow, it’s just raining Gödel references. The latest issue of the Bulletin of Symbolic Logic is all about Gödel, with exciting-sounding titles like “Future tasks for Gödel scholars” (John W. Dawson, Jr. and Cheryl A. Dawson), “On Gödel’s way in: the influence of Rudolf Carnap” (Warren Goldfarb), and “Gödel’s reformulation of Gentzen’s first consistency proof for arithmetic: the no-counterexample interpretation” (W. W. Tait). The papers are freely available in PostScript on the BSL website. If you can’t display PostScript, convert the files here or wait for the issue to appear on Project Euclid. (The issue also has a nice review by Dirk Schlimm of my paper on Hilbert’s “verunglückter Beweis”–thanks, Dirk!)
If you happen to be in or near Vienna, there’s a little workshop at the TU Wien, Monday to Wednesday of next week, sponsored by the Gödel Society. It’s on cut-elimination; speakers include Lev Beklemishev, Ale Carbone, Grigori Mints, Pavel Pudlák, and Helmut Schwichtenberg as well as a bunch of up-and-coming young logicians like Arnold Beckmann, Agata Ciabattoni, Rosalie Iemhoff, Georg Moser and George Metcalfe. (Ok, that’s almost the entire program, so I’ll mention also Christian Urban and Clemens Richter, who I don’t know yet. But I’m sure their talks will be top-notch as well.)
Don’t you wish someone would write a book that catalogs all the various ways in which one can misstate, misunderstand, and misapply Gödel’s theorems, and how to correct such misunderstandings? A book that you can send your students off to read when they say stuff like, “Gödel showed that there is no mathematical truth,” or “The mind can go outside the system, but no formal system can because of incompleteness, so the mind is not a formal system.” Well, it’s here. Torkel Franzén has been tireless for at least 15 years in correcting misunderstandings relating to logic on sci.logic (which was a lot of fun in the pre-AOL days), on FOM, and elsewhere. He has a book out last year in the ASL’s Lecture Notes in Logic series, which is an excellent technical treatment, and now a fine popular book: Gödel’s Theorem. An Incomplete Guide to its Use and Abuse (A K Peters, 2005). A brief excerpt from a forthcoming review in History and Philosophy of Logic:
On the heels of Franzén’s fine technical exposition of Gödel’s incompleteness theorems and related topics comes this survey of the incompleteness theorems aimed at a general audience. Gödel’s Theorem. An Incomplete Guide to its Use and Abuse is an extended and self-contained exposition of the incompleteness theorems and a discussion of what informal consequences can, and in particular cannot, be drawn from them. The book is divided into seven chapters. A brief introduction outlines the aims and contents of the book, a lengthy second chapter introduces the incompleteness theorems and outlines their proofs in non-technical terms, and chapter 3 discusses computability and its connections with the incompleteness theorems. Chapter 7 deals with the completeness theorem, and chapter 8 outlines and criticizes Chaitin’s work on information-theoretic complexity and its relationship to incompleteness. An appendix fills in some of the technical details. The remaining three chapters (4−6) are devoted to dispelling confusions about incompleteness. Chapter 4, “Incompleteness Everywhere”, dispenses with some basic misconceptions, examples range from atrocious yet all-too-common claims made in Internet discussions (“Gödel’s theorems show that the Bible is either inconsistent or incomplete.”) to published remarks by the likes of Freeman Dyson and Stephen Hawking. As one might expect, the corrections here are often basic (e.g., pointing out that the Bible is not a formal system of arithmetic), but just as often they are quite subtle. The (purported) implications of Gödel’s theorems for the character of mathematical knowledge and for the nature of the mind (the anti-mechanist arguments of Lucas and Penrose) receive extended treatment in chapters 5 (“Skepticism and confidence”) and 6 (“Gödel, minds, and computers”), respectively.
It’s out now from A K Peters; Powell’s and Amazon don’t ship it yet, but you can preorder from Amazon.
UPDATE: The book’s shipping now, and is also available from Powells.
ANOTHER UPDATE: Sol Feferman kindly sent a link to his letter to the editor of the New Your Review of Books on Dyson’s review in which he (Dyson) appealed to Gödel’s theorem.
Christos Papadimitriou has a novel called Turing (A Novel About Computation). (He also has a few other excellent textbooks on technical stuff, but y’all know that.) I didn’t know about the novel before, and so when I went to the MIT Press website, I noticed that it’s on sale! Only 9 bucks (US) for the hardcover! Here’s the content blurb:
Our hero is Turing, an interactive tutoring program and namesake (or virtual emanation?) of Alan Turing, World War II code breaker and father of computer science. In this unusual novel, Turing’s idiosyncratic version of intellectual history from a computational point of view unfolds in tandem with the story of a love affair involving Ethel, a successful computer executive, Alexandros, a melancholy archaeologist, and Ian, a charismatic hacker. After Ethel (who shares her first name with Alan Turing’s mother) abandons Alexandros following a sundrenched idyll on Corfu, Turing appears on Alexandros’s computer screen to unfurl a tutorial on the history of ideas. He begins with the philosopher-mathematicians of ancient Greece — “discourse, dialogue, argument, proof… can only thrive in an egalitarian society” — and the Arab scholar in ninth-century Baghdad who invented algorithms; he moves on to many other topics, including cryptography and artificial intelligence, even economics and developmental biology. (These lessons are later critiqued amusingly and developed further in postings by a fictional newsgroup in the book’s afterword.) As Turing’s lectures progress, the lives of Alexandros, Ethel, and Ian converge in dramatic fashion, and the story takes us from Corfu to Hong Kong, from Athens to San Francisco — and of course to the Internet, the disruptive technological and social force that emerges as the main locale and protagonist of the novel.
With his characteristic blend of genius and insanity, Leibniz had conceived of a project in which the simple constituents of concepts would be represented by prime numbers and their composition by multiplication. From the Chinese number theorem [sic] (and certein assumptions about the nature of truth) he inferred that–given this “perfect language”–could be resolved by appeal to the algorithm of division.
I wonder if Gödel was inspired by this “project” in his coding apparatus and the proof of Theorem VII in his 1931 paper on the incompleteness theorem (which is where he uses the Chinese remainder theorem to deal with arithmetical coding of sequences).
Well, I spent the last 2 weeks finishing a paper and cleaning house, and now I’m in Vienna and jetlagged. But I got all my library cards in order and checked out some books. Now all I need is some sleep, setting up some kind of internet access at home, and I’ll be back to reading, writing, and blogging. Oh, and obviously enjoying being in a decent town where one can catch good shows, e.g., next week Magnolia Electric Co. and Feist (allegedly).
Yarden Katz emailed me this query, which I unfortunately don’t have time right now to think about. Please, someone help him out by posting a comment!
I was reading Graham Priest’s account of intuitionist logic (in Intro to Non-Classical Logics), where he gives a possible world semantics for several intuitionist logics. In addition to few other restrictions in the semantics, the accessibility relation is essentially K + transitivity + symmetry. In parallel, I have been working on ground non-monotonic logics, especially on S5. K + trans + symmetry is obviously a subset of the universal structure used in S5, and this raised the following question for me: What would a non-monotonic intuitionist logic look like? Can it have a coherent philosophical interpretation? A bit of online searching brought nothing relevant, and I have not heard of such logics. I was wondering if you had any insights on this.
Peter Smith writes:
Just in time for its first birthday, I’ve updated the LaTeX for Logicians site. Maybe the title is getting rather misleading, as there is stuff there that may well be of interest to many philosophers and assorted other TeXies too! (My sense is that more and more philosophy grad students are picking up on LaTeX for various obvious reasons: so you might want to put a link to this on your department’s page of resources for philosophy graduates.)