I’m sometimes asked for recommendations about what to read before or after IGT — or indeed, what to read instead of tackling IGT if you are looking for something less weighty, or alternatively looking for something more like a conventional mathematical text. So here are some suggestions, for different kinds of audiences.
1. What do I need to know before I can read IGT?
I am afraid that you do need some logical background to tackle my book (and likewise for most alternative presentations). But you don’t need very much background: a reading knowledge of standard logical symbolism, the idea of a formal system for first-order logic, the ideas of soundness and completeness, the idea of a formal axiomatized theory …
I suppose you could try reading IGT and filling in logical background (from Wikipedia, for example) on a need-to-know basis. But better, check out the Teach Yourself Logic Guide for suggestions for elementary logical reading.
2. There are a lot of symbols in IGT! What should I read if I want something shortish but reliable that will just give me some headline news without all the hard work?
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, and then there is of course lots more in the entry specifically on Gödel’s Incompleteness Theorems by Panu Raatikainen (though there a quite a few symbols there too). But if you want/need a slower introduction, 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).
3. What if I want more detail that Franzen gives, 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 are a bit more mathematical and 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.
4. I’m reading/have just read IGT and would like some parallel reading at about the same level.
The obvious two recommendations, apart from the Smullyan book just mentioned, have to be
Richard L. Epstein and Walter A Carnielli, Computability: Computable functions, logic, and the foundations of mathematics (Wadsworth, 3rd edn 2008).
George Boolos and Richard C. Jeffrey, Computability and Logic (CUP, 3rd edn 1989).
The fourth and fifth editions of the latter book 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. For a third suggestion, I can also recommend the insightful but non-standard approach of
Melvin Fitting, Incompleteness in the Land of Sets (College Publications, 2007).
5. I’m a graduate student, want to learn about Gödel’s theorems in detail, have some logical background, and so 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 in fact of the same kind of level as the compressed Smullyan or the more expansive Boolos/Jeffrey, for example, so would e.g. be as apt for an introductory graduate-level reading group as those books are. But if you want alternatives, I’ve just mentioned three.
6. 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 2014).
There’s also a more recent book by Herb Enderton, Computability Theory: An Introduction to Recursion Theory (Academic Press, 2011) which is excellent too, though doesn’t go as far. 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).
Enjoy!
I have access to the 2nd, 4th and 5th edition of Boolos et al. and not the 3rd edition. Which one would you recommend?
Well, the second for a first read, then the fifth for consolidation and some additional topics!
There are some huge gaps between Logic books! for instance your book on formal
logic is great at its level! but there is a huge gap between it and for instance Mendelson’s Introduction to Mathematical logic! A book is needed between them!
Iknow of the ones that you have mentioned A friendly Introduction
and Hodge’s book, but they are inadequate both because they the gap between them
and your book on formal logic is too great and because they are not the best for educational purposes! Cambridge should develop a series of books at each level of
logic!
My Teach Yourself Logic Guide tries at the beginning to give pointers to books that might help bridge the gaps between e.g. my intro book and heavy-duty math logic textbooks.
Thanks for the quick & helpful reply!
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.
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.
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.
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.