Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

up vote 7 down vote accepted

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.

share|improve this answer
2  
that's a terrific book, but does it really go into the proofs of Godel's Theorems, as user requests? –  Gerry Myerson Jul 19 '11 at 3:52
1  
@Gerry. Yes, I believe so, and my opinion is shared by others, e.g. in the MO thread: Pete Clark and Carl Mummert. –  Bill Dubuque Jul 19 '11 at 4:03
    
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." –  Gerry Myerson Jul 19 '11 at 4:22
    
@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. –  Bill Dubuque Jul 19 '11 at 4:37

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

share|improve this answer
    
That book is recommended in two of the answers to the MO question mentioned in Bill Dubuques's answer. –  Gerry Myerson Jul 19 '11 at 12:57

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

share|improve this answer

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

share|improve this answer
    
Seconded here - I have a slight bias towards Smullyan, but while he certainly has his weaknesses I find his writing particularly crisp. –  Steven Stadnicki Jul 21 '11 at 22:02

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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