Home

Goedel's Theorem and Theories of Arithmetic

Logic is the cornerstone of computer science in general and much of programming language theory in particular. Goedel's results are fundamental for any real understanding of modern logic.

This book by Peter Smith might serve as an introduction to Goedel's incompleteness results. Twelve chapters are online, and seem quite readable.

By Ehud Lamm at 2004-08-21 17:04 | Misc Books | other blogs | 79240 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

What's next?

The author asks readers tos end him any comments they might have. LtU readers should take this to heart.

I suggest reading the TOC and the section titled "What's Next" and letting the author know if you have different ideas about the future of the book. It seems that adding something on the Curry-Howard isomorphism would be a good idea, seeing as the book naturally deals with the border between CS and logic.

By Ehud Lamm at Sat, 2004-08-21 17:42 | login or register to post comments

Read the Real Thing

If this book piques your interest, I heartily suggest reading the original paper by Gödel. It is available, in English translation, published by Dover in a slim paper back edition.

The proof is not all that hard to work through. One of the wonders of it is that it is a constructive proof: The paper constructs an actual undecidable proposition.

If you do decide to work through it, have some paper and pens in four colors at your side. You'll need 'em...

By MtnViewMark at Sat, 2004-08-21 21:03 | login or register to post comments

Good suggestion

I second the recommendation. It's a beautiful proof, beautifully done.

In fact, being both elegant and constructive it looks very much like a set of function definitions in a functional language...

By Ehud Lamm at Sat, 2004-08-21 21:07 | login or register to post comments

On Gödel

"If you look at Gödel's original paper you see what to me looks like LISP, it's very close to LISP, the paper begs to be rewritten in LISP!" — Gregory Chaitin, "Exploring Randomness"

By Paul Snively at Sat, 2004-08-21 22:54 | login or register to post comments

Another introduction to his proof

I was lucky enough to borrow a friend's copy of Gödel's Proof, which is another excellent introduction to it for less math-oriented folks (like me). I know one other person who's read the book (also without a formal logic background) who found it easy to follow and enlightening.

By Andre Pang at Sun, 2004-08-22 01:52 | login or register to post comments

Hintikka On Goedel

Hintikka has a very nice bit about the philosophical implications of
Goedel's proof in On Goedel that debunks some of Chaitin and Hofstader (and most
popularizers, for that matter). There are a number of nice
modern "translations" of the proof on the web as well. I can't find the
original one I really enjoyed, but I did find this by googling:
Beautifying Goedel.

By Drew Bagnell at Sun, 2004-08-22 15:14 | login or register to post comments