A Wonderful Read On Gödel's Theorem

I recently finished reading the book Gödel's Theorem: An Incomplete Guide to its Use and Abuse by Torkel Franzén. This is a book I would recommend to all of the readers of this blog. (Not "This is a book I would recommend to all of the readers of this book", as I had written originally. Thanks to Luca Trevisan for spotting this embarrassing statement of mine. Haste generates monsters, alas :-() It is accessible yet precise, and it sets the record straight on what Gödel's theorem implies and what it does not imply. While reading it I quickly learned that, despite my previous reading of texts on Gödel's theorem, I suffered from some of the misunderstandings that Franzén discusses in his lovely book.

To quote from the overview chapter in the book:

The aim of the present addition to the literature on Gödel’s theorem is to set out the content, scope and limits of the incompleteness theorem in such a way as to allow a reader with no knowledge of formal logic to form a sober and soundly based opinion of these various arguments and reflections invoking the theorem. To this end, a number of commonly occurring such arguments and reflections will be presented, in an attempt to counteract common misconceptions and clarify the issues. The formulations of these arguments and reflections, when not attributed to any specific author, are adaptations of statements found on the net, representative of many such reflections.

I think that the book succeeds beautifully to do just that, and will repay re-reading.

Torkel Franzén also maintained the page Gödel on the net, from which the book eventually originated.

You might have noticed the use of the past tense in the previous sentence. Unfortunately, I just discovered that the author passed away in 2006. He left some books that, like this one, have received praise from many sources. I certainly enjoyed reading this book, and I am feeling tempted to open my purse and purchase a copy of this volume for my personal library.

Addendum (17 November 2007): I encourage any reader who wants to catch a glimpse of what this book is about, and of the writing style of the author, to have a look at this short article Torkel Franzén wrote for the Notices of the AMS (volume 53, number 4). Here is an example of one of the many things I personally learned from the book.

Let us say that a formal system has an arithmetical component if it is possible to interpret some of its statements as statements about the natural numbers, in such a way that the system proves some basic principles of arithmetic having to do with summation and multiplication. Given this, we can produce (using Barkley Rosser’s strengthening of Gödel’s theorem in conjunction with the proof of the Matiyasevich-Davis-Robinson-Putnam theorem about the representability of recursively enumerable sets by Diophantine equations) a particular statement of the form “The Diophantine equation p(x1 , . . . , xn ) = 0 has no solution” which is undecidable in the theory, provided it is consistent.

Franzén remarks that

....it is mathematically a very striking fact that any sufficiently strong consistent formal system is incomplete with respect to this class of statements,....

However, no famous arithmetical conjecture has been shown to be undecidable in ZFC.....From a logician's point of view, it would be immensely interesting if some famous arithmetical conjecture turned out to be undecidable in ZFC, but it seems too much to hope for.

Wikipedia has a short list of mathematical statements that are independent of ZFC on this page. You may find it interesting.

Saharon Shelah's result to the effect that the Whitehead problem is undecidable in ZFC is discussed in this paper by Eklof. Shelah has also shown that the problem is independent of ZFC+CH.

There is also an interesting post on a combinatorial problem that is independent of ZFC on the complexity blog. That post also includes several pointers to pieces that are well worth reading.