7
$\begingroup$

I would like to learn more about the proofs of Gödel's incompleteness theorems. I have read and am rereading Gödel's proof by Nagel, Newman, and Hofstadter. I like it very much, but I would like something a bit more substantial (but not too substantial). More specifically, I am a professor of mathematics, but not a logician. (If it helps, I am a probabilist.) I would like to read something that is aimed more at my level and is preferably self-contained. But this is purely for my own curiosity, so I do not want to learn a whole new field to understand it. Does anyone have any suggestions?

$\endgroup$
9
$\begingroup$

Highly recommended: Torkel Franzén. Gödel's Theorem: An Incomplete Guide to its Use and Abuse. Wellesley, Massachusetts: A K Peters, Ltd., 2005. x + 172 pp. ISBN 1-56881-238-8.
Some reviews: NAMS (Panu Raatikainen), Phil. Math. review (Stewart Shapiro) and R. Zach.

For a more concise technical treatment see Smorynski's 47 page exposition in the Handbook of Mathematical Logic (edited by J. Barwise). Smorynski is an expert in the field and a gifted expositor. I recall being highly influenced by many of his expositions as a student (some less technical than the cited paper). Note also that the 1165 page Handbook is an excellent general reference on logic for a mathematician.

See also this Related MO question.

$\endgroup$
  • 2
    $\begingroup$ that's a terrific book, but does it really go into the proofs of Godel's Theorems, as user requests? $\endgroup$ – Gerry Myerson Jul 19 '11 at 3:52
  • 1
    $\begingroup$ @Gerry. Yes, I believe so, and my opinion is shared by others, e.g. in the MO thread: Pete Clark and Carl Mummert. $\endgroup$ – Bill Dubuque Jul 19 '11 at 4:03
  • $\begingroup$ In that same thread, Bill, Antonio Porreca writes, "No, Franzén doesn’t give full proofs." On pp. 3-4, Franzen writes, "In this book, no knowledge of logic or mathematics (beyond an acquaintance with school mathematics) will be assumed, on the basis of the view that a sound informal understanding of the theorem is attainable without a study of formal logic." $\endgroup$ – Gerry Myerson Jul 19 '11 at 4:22
  • $\begingroup$ @Gerry If a reader lacks sufficient background to fill in the details of proofs sketched in Franzén's book then they can find them in the paper of Smorynski that I cited above. $\endgroup$ – Bill Dubuque Jul 19 '11 at 4:37
4
$\begingroup$

I suggest the terrific book "An Introduction to Gödel's Theorems" written by Peter Smith http://www.amazon.com/Introduction-Theorems-Cambridge-Introductions-Philosophy/dp/0521674530

$\endgroup$
  • $\begingroup$ That book is recommended in two of the answers to the MO question mentioned in Bill Dubuques's answer. $\endgroup$ – Gerry Myerson Jul 19 '11 at 12:57
3
$\begingroup$

A couple of good, standard texts that handle Godel's work are Mendelson, Introduction to Mathematical Logic, and Enderton, A Mathematical Introduction to Logic.

$\endgroup$
3
$\begingroup$

I recommend Gödel's Incompleteness Theorems by Raymond Smullyan. He motivates well and his style is appropriate for a mathematician reader.

$\endgroup$
  • $\begingroup$ Seconded here - I have a slight bias towards Smullyan, but while he certainly has his weaknesses I find his writing particularly crisp. $\endgroup$ – Steven Stadnicki Jul 21 '11 at 22:02
3
$\begingroup$

It is also possible to proof the incompleteness theorem utilizing computability theory, by reducing it to the halting problem. I think this method is easier to understand, since it just relies on some basic knowledge of the undecidability of the halting problem.

Here is a reference http://www.logicmatters.net/resources/pdfs/PartIII.pdf

As we speak, Scott Aaronson made a wonderful post about this on his blog: http://www.scottaaronson.com/blog/?p=710

$\endgroup$

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.