1
$\begingroup$

I'm really interested in Godel's incompleteness theorem, yet, I know very little about logic.

I recently started reading an online pdf that supposedly had a complete proof, but when I asked in MathStackExchange about sentences I couldn't understand in the text, the repliers told me that the document was rather "confusing and misleading".

So I was wondering, does someone know of a book/document/blog that while providing a complete proof of the theorem, also explains each step in a way that someone without much experience about logic could understand?

I would really appreciate any help/thoughts.

Improve this question
$\endgroup$
6
$\begingroup$

First of all, before you read the full proof, it's worth finding a good overview so you know what you're getting into. It's pretty old, but I'm a big fan of Rosser's expository paper on the topic; I'd read that before diving into the full proof, since it clarifies a lot of what will be going on. Note that it doesn't just discuss Godel's incompleteness theorems, but also a couple related results (including Rosser's own improvement of Godel's theorem - which is, in fact, how Godel's theorem is usually stated).

Now what about the full proof?

Peter Smith's book An introduction to Godel's theorems is extremely good, but covers a lot of ground - in particular it doesn't actually get to the incompleteness theorem until chapter 21! So if you're willing to devote a lot of time to this task, I think this is the best source you'll find, but there are definitely faster ways to get there.

If Smith's book seems a bit daunting for now, I recommend the text Computability and logic by Boolos, Burgess, and Jeffrey. I absolutely adore this book; it was the first logic text I read, and it was what got me hooked. As the title indicates, this isn't just about Godel's incompleteness theorems, and so you can ignore most of it for now (but seriously the whole thing is excellent - do read it sometime!) Specifically, chapters $9,10,14,15,16,17$ give an entirely self-contained path to the first incompleteness theorem in about $80$ pages; chapter $18$ then covers the second incompleteness theorem in about $10$ more pages.

Improve this answer
$\endgroup$
  • $\begingroup$ With no objective other than studying for its own sake, at this point do you have a preference as to which to read first? $\endgroup$ – user12802 Jun 15 '18 at 21:16
  • $\begingroup$ @Andrew I think it depends on whether you're looking for a "big narrative" - in which case, go with Smith - or something more modular. Personally I find it easier to start on the more modular side, so I would begin with BBJ, but there's no solid reason for that; they're both great books. I think the warning I would attach to Smith's is that you really should commit to read at least a large fraction of it, I don't think it does as well if you just read a small bit (whereas BBJ is very forgiving in that respect). $\endgroup$ – Noah Schweber Jun 15 '18 at 21:18
  • $\begingroup$ You are right, modules are appealingly accessible. And, thus, starting at chapter 9, BBJ is math writing at its best. $\endgroup$ – user12802 Jun 18 '18 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.