I'm a math beginner. I am a self-learner. A while ago, I finished reading “How to Prove It: A Structured Approach, 2nd Edition” by Daniel J. Velleman.

Now, I want to learn Gödel's incompleteness theorem to avoid making the same mistakes made in the past by others.

Where do I find the best learning material for Gödel's incompleteness theorem?

  • 7
    $\begingroup$ What sort of mistakes do you want to avoid by learning Gödel's incompleteness theorem(s)? $\endgroup$ – user642796 Oct 7 '15 at 13:34
  • $\begingroup$ I'm a programmer. I heard type systems in programming languages are subject to Gödel's incompleteness theorem. I also plan to write programs that deal with sets. Sets may also be subject to Gödel's incompleteness theorem. $\endgroup$ – crocket Oct 7 '15 at 13:35
  • $\begingroup$ So you actually do not want to know about the incompleteness theorem, but rather how it affects programming? If you want to learn about the theorem, just read about any university logic course book. If you want to learn about the programing part, I am not sure... $\endgroup$ – Ove Ahlman Oct 7 '15 at 13:40
  • $\begingroup$ This post clearly shows that as long as a formal system can somehow prove the output of any program if it halts, then it must be incomplete. This is simply a matter of string manipulation and not related to sets or types. $\endgroup$ – user21820 Apr 11 '17 at 5:07
  • $\begingroup$ This post gives a more informal proof of a generalized incompleteness theorem based only on knowledge of programming and basic logic. $\endgroup$ – user21820 Sep 11 '18 at 10:00

You can see Gödel's Incompleteness Theorems.

Two good books are :

And you can see also this post for other references.


Start for example here: Wikipedia

Or read the translated version of Gödel's paper: http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf

  • $\begingroup$ Does research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf contain everything about Gödel's incompleteness theorems? Can a person who just finished “How to Prove It: A Structured Approach, 2nd Edition” by Daniel J. Velleman read such a paper? $\endgroup$ – crocket Oct 7 '15 at 13:41
  • $\begingroup$ I don't know if a person can, but Wikipedia is sort of always a good place to start with. Yes it should contain everything, because it is a translation of Gödel's paper. But as already mentioned by others, if you want to program, then really Gödel's theorems are of little practical use. Just program. $\endgroup$ – orgesleka Oct 7 '15 at 13:45
  • $\begingroup$ I have found that paradoxically reading the original paper of a subject is usually not the best way to learn a subject. However, reading Wikipedia is usually a great way to get an introduction to a subject. $\endgroup$ – Craig Feinstein Oct 9 '15 at 13:46

I learned Gödel's Incompleteness Theorem in high school in the 1980's from two books,

The Lady or the Tiger by Raymond Smullyan http://www.amazon.com/THE-LADY-OR-TIGER/dp/0394514661 and

Gödel, Escher, and Bach by Douglas Hofstadter http://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden/dp/0465026567

These are entertaining presentations of the theorem in which one doesn't get lost in the details.

If you want to learn more, I would recommend reading Meta-Math by Gregory Chaitin, where he takes things to a higher level. http://arxiv.org/abs/math/0404335


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.