I’m sometimes asked for recommendations about what to read after IGT – or indeed, what to read instead of tackling IGT if you are looking for something less weighty, or for something more like a conventional mathematical text. So here are some suggestions, for different kinds of audiences.
1. What should I read if I want something shortish but reliable that will just give me some headline news?
As so often, the Stanford Encyclopedia of Philosophy is a good place to start: the entry on Kurt Gödel by Juliette Kennedy gives a brisk account of the incompleteness theorems. But if you want/need to go a bit slower, you probably won’t do better than the excellent and rightly much admired
Torkel Franzen, Gödel’s Theorem: An Incomplete Guide to its Use and Abuse (A.K. Peters, 2005)
which explains the incompleteness theorems and how they are proved, and gives some indication of why they might matter. Franzen is also excellent at pouring cold water on some ludicrous abuses/misinterpretations of Gödel’s result. A different approach, which some will love, is to be found in one of Smullyan’s classic books exploring logic through puzzles:
Raymond Smullyan, Forever Undecided: A Puzzle Guide to Gödel (OUP pbk 1998).
2. What if I want more detail but still something a lot shorter than IGT?
Well, there are my own notes (which at least are both a lot shorter and a lot cheaper than IGT, but unsurprisingly run along very similar lines)
Or, if you can cope with a certain degree of terse elegance, there is the simply wonderful
Raymond Smullyan, Gödel’s Incompleteness Theorems (OUP, 1992).
which weighs in at a meagre 135 pages.
3 I’m reading/have just read IGT and would like some parallel reading at about the same level.
The obvious recommendation, apart from the Smullyan book just mentioned, has to be
George Boolos and Richard C. Jeffrey, Computability and Logic (CUP, 3rd edn 1989).
The fourth and fifth editions have John Burgess as a third author. But many would agree that the later additions and amendments are not all for the best, and the book has become notably longer in the process.
4. I’m a graduate student, want to learn about Gödel’s theorems in detail, have some logical background, and could handle more than a ‘Cambridge Introduction to Philosophy’.
Don’t be put off IGT by the series it appears in (I happily agreed to its inclusion because it led to the paperback being comparatively very cheap). The book is of the same kind of level as the compressed Smullyan or the more expansive Boolos/Jeffrey, so would e.g. be as apt for an introductory graduate-level reading group as those books are. But if you want alternatives, Smullyan’s treatment has the virtues of brevity and elegance, as does the insightful but non-standard approach of
Melvin Fitting, Incompleteness in the Land of Sets (College Publications, 2007).
[I think that has to be got via print-on-demand from Amazon, ISBN 978-1904987345.] But IGT is in places quite a bit more detailed.
5. I’ve read IGT and would like to push on from there.
One direction to go is read more on the theory of computable functions in a more general and systematic way. I’d recommend the following pair of texts (the first is rightly something of a modern classic, the second seems the best of a later crop):
N. J. Cutland, Computability: An Introduction to Recursive Function Theory (CUP, 1980).
S. Barry Cooper, Computability Theory (Chapman & Hall/CRC Mathematics 2004: 2nd edition promised for 2012).
(There’s also a more recent book by Herb Enderton, Computability Theory: An Introduction to Recursion Theory (Academic Press, 2011) which looks good too, but which I can’t vouch for yet.) Another direction to go, more specifically tied to the incompleteness phenomenon, is to consider what happens if you e.g. add to PA its unprovable consistency sentence to get PA+Con, and then add the consistency sentence of that, and so on. On this and related matters, see
Torkel Franzen Inexhaustibility: A Non-exhaustive Treatment (Association of Symbolic Logic/A. K. Peters 2004).
And in a rather different direction again, there is another modern classic
George Boolos, The Logic of Provability (CUP, 1993).
If you’ve got a reasonably solid background in maths and or formal logic why not go for a real classic Stephen Kleene’s “Introduction to Metamathematics”?
As the notes linked to the previous post make clear, I am a great admirer of Kleene’s book. I’d certainly recommend any graduate student at least to skim-read it sometime, slowing down over any sections that take her interest. (But if your particular interest is in the incompleteness theorems, this isn’t the best thing to read instead of IGT!)
I think that what’s important is that Kleene shows that Gödel’s results are part of an extensive system and not isolated facts.
Dear Dr. Smith,
I am a first year Philosophy student at Cambridge at the moment. Do you think it would be possible to understand the book once I finish this year’s logic paper?
I think I just have to say “try it and see”. On the one hand, there’s almost nothing by way of logical background that’s needed that isn’t in my Introduction to Formal Logic. On the other hand, it perhaps needs a certain ‘mathematical maturity’ (as they call it in the trade) — a willingness and ability to follow mathematical proofs.
You speak of ‘mathematical maturity’ but could you tell me how to acquire an ability to follow mathematical proofs. It’s not of much help to speak in this way without giving specific advice. How can I bridge the gap between IFL and IGT?
Good point: it spurred me to get round, at last, to writing this page, which I hope might help.
I would say, amost all of Smullyan’s books are about Godel’s results, not only the upper quoted one (which is quite advanced).
True enough. I should, certainly, have mentioned Forever Undecided. Now added.
Hi -
Could you please elaborate a bit on the issue of whether or in what ways Boolos and Jeffrey C&L 3rd edition might be preferable to the 4th edition with Burgess’ changes (supposedly to make chapters independent). I have read Amazon comments that the chapters in the 4th are somewhat disconnected (some key concepts are not integrated into the exposition or even cross-referenced).
I am particularly interested in Boolos’ application of modal logic to provability. and would by some edition of C&L for that chapter alone. I realize he has two books on the topic, one of which you mentioned, but am not yet sure I need that much detail. I’d really just like to understand the general connections and results.
I am also wondering how Fitting you mention (Incompleteness if the Land of Sets) compares to Boolos’ books on modal logical & provability.
Lastly when might the next edition of IGT appear? I noticed you commented on its preparation and this made me wonder if I should not wait for the new edition.
Any comments or advice appreciated.
Thanks in advance.
1. I’m not the only one who thinks a bit of elegance is lost between C&L 3 and C&L 4/5. (But I don’t think it is a deal breaker. The latest version is still a very good book.)
2. There is indeed a brief treatment of provability logic in C&L; but it is may be a bit too short to be useful. I’d say that if you do want more than is in the Stanford Encyclopedia article on Provability Logic, then jump to Boolos’s second book.
3. Fitting only briefly touches provability logic in his last chapter.
4. The second edition of IGT won’t be out before the end of the year.
Everybody I know who read C&L3 said it is superior to versions 4 and 5. I must admit I have only come into contact with C&L5 and I like it. But it attracks me when they said that C&L3 is far more elegant.
Thanks for the quick & helpful reply!