Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi!

What text on both incompleteness theorems you would recommend for beginner? Specifically, I'm looking for the text with the following properties:

1) The proofs should be finitistic, in Godel's tradition, i. e. formalizing "I'm unprovable" (not, for instance, via formalization of halting problem);

2) The text must be of reasonable length but with complete proofs, so that one can study them in a reasonable amount of time (e. g. only those forms of recursion theory theorems are proved which are precisely needed for incompleteness proofs);

3) The entire text should be motivated and discussing ideas (even those of philosophical character) before and between technical constructions.

I would be very thankful if you'll equip your suggestion with some short resume.

share|improve this question
    
The following does not prove Godel's Completeness Theorems, but it does show how they might be applied to problems in algebra: msri.org/publications/books/Book39/files/marker.pdf –  David Corwin Aug 1 '10 at 12:06
    
@Davidac897: Thank you, I've read this text. But my question concerns with incompleteness theorems, not completeness ones. –  Sergei Tropanets Aug 1 '10 at 12:10
    
@Davidac897: And I think that it's more faithfully to say that all those are applications of compactness theorem. In fact, you may not use deductive system at all –  Sergei Tropanets Aug 1 '10 at 12:14
add comment

10 Answers 10

up vote 2 down vote accepted

First chapter of Jean-Yves Girard, "Proof Theory and Logical Complexity", Vol I, Bibliopolis, 1987

It satisfies all of your conditions, but it is not an elementary book. If I remember correctly, the authors (A.S. Troelstra and H. Schwichtenberg) of the book "Basic Proof Theory" which is published in 2001 wrote in their introduction that their intention was to fill the gap between this and all other (introductionary) books in proof theory. As far as I know, he never published the second volume.

share|improve this answer
    
I was not aware of Girard's book. It's amazing book! (not only on incompleteness). Thank you very much! –  Sergei Tropanets Aug 1 '10 at 23:51
    
"For beginners" doesn't necessarily mean "elementary" :) –  Sergei Tropanets Aug 1 '10 at 23:56
2  
If you want a non-elementary but general and short reference, I'd recommend Smorynski's article in the Handbook of Mathematical Logic. When I read "for beginners" in the question, it made me think you are looking for undergraduate-level references. –  Carl Mummert Aug 2 '10 at 0:02
    
@Carl Mummert: I'll check it out, Thanks! –  Sergei Tropanets Aug 2 '10 at 0:15
    
I think an enthusiastic beginner can read the book (at least the first few chapters) if he or she has the stomach for it. I used to jump out of my chair every few pages the first time I read it. :) –  Kaveh Aug 2 '10 at 4:57
add comment

Speaking as a beginner myself:

I haven’t read it all yet, but An Introduction to Gödel’s Theorems by Peter Smith seems like a good candidate, and it doesn’t have many prerequisites. Smith also wrote a series of shorter handouts on the topic, Gödel Without (Too Many) Tears.

There’s also Godel’s Theorem: An Incomplete Guide to Its Use and Abuse by Torkel Franzén, which is much less technical and primarily concerns false myths about the incompleteness theorems; in my opinion, it is a good companion (not a substitute) for Smith’s book.

share|improve this answer
    
Smith's book is too big. But his "Gödel Without (Too Many) Tears" seems to be a good candidate. Thank you! As for Franzen's book, I'm not sure if it contains complete and fully rigorous proofs. The quote from Richard Zach's review: <<On the heels of Franzén's fine technical exposition of Gödel's incompleteness theorems and related topics (Franzén 2004) comes this survey of the incompleteness theorems aimed at a general audience.>> –  Sergei Tropanets Aug 1 '10 at 11:50
    
No, Franzén doesn’t give full proofs; it might be interesting, however, for some philosophical discussion (which, I think, is missing in Smith’s handouts). –  Antonio E. Porreca Aug 1 '10 at 12:11
    
For introductory philosophical discussion, both Smith's book and the new book by Berto ("There's something about Goedel") seem good. I have had a chance to scan through Berto's book but haven't read it in detail yet. –  Carl Mummert Aug 1 '10 at 12:25
add comment

For instance, there is a well-regarded recent book of Torkel Franzen:

Gödel’sTheorem: An Incomplete Guide to Its Use and Abuse

A detailed and positive review was given by Panu Raatikainen in the Notices of the AMS:

http://www.mv.helsinki.fi/home/praatika/rev-raatikainen.pdf

Honestly, your question seems underdetermined, since there are many other well-regarded books that an internet search will reveal to you. I would suggest just picking one and trying it out.

share|improve this answer
1  
<<Gödel’sTheorem: An Incomplete Guide to Its Use and Abuse>> Does it contain fully rigorous proofs? <<I would suggest just picking one and trying it out.>> My personal experience tells me it's not a good idea. –  Sergei Tropanets Aug 1 '10 at 11:56
1  
Yes - despite the unserious name, Franzen's book is very thorough. I would also recommend it to beginners. –  Carl Mummert Aug 1 '10 at 12:24
    
@ST: Your personal experience tells you that it's not a good idea to select texts that seem like they may be relevant and of interest and try reading them to see whether this is actually the case? I don't know what to say to that, except that I'm sorry to hear it. –  Pete L. Clark Aug 1 '10 at 12:30
2  
@Pete L. Clark: I didn't mean that at all! Let me explain. I tried to study incompleteness proofs by Goodstein and after many preliminary chapters (=much time) I found that the proofs are in many places disorderly and as a result the reading got harder and harder. When you go to other books you see different style, deductive systems and so on. So, because of that reasons, I am asking some suggestions. –  Sergei Tropanets Aug 1 '10 at 12:55
add comment

Peter Smith's book is great. It's very readable and contains all the details. The problem is that it doesn't leave anything for you to do! If you want to get your hands dirty and work a few things out for yourself, I'd recommend Raymond Smullyan's book Godel's Incompleteness Theorems. It's a bit terse, but very clear and complete, more like what one would expect of a traditional mathematics text. Most importantly, it contains some very well selected exercises at the end of each chapter.

Edit: It costs a fortune on amazon, but if you look around discount places like abebooks you can find it for a fraction of that price.

share|improve this answer
add comment

The most accurate text (even for beginners) in my opinion is C. Smorynski's paper in the Handbook of Mathematical Logic - "The incompleteness theorems". I think it answers all your three requirements.

share|improve this answer
add comment

My favorite text on mathematical logic period is Wolf's A Tour Through Mathematical Logic. There's a terrific chapter in there on the Godel Theorums with historical and philosophical notes. That's where I'd begin.

For a more mathematically rigorous presentation, the classic An Introduction To Mathematical Logic by my old teacher Elliott Mendelson is still very hard to beat for clarity and depth.

share|improve this answer
    
+1 for Mendelson's book, though I think Girard's book beats it. :) –  Kaveh Aug 2 '10 at 4:55
add comment

It's not a book, and it's not perfectly formal, but it's short (8 pages), eminently readable, and the best source of intuition about Goedel's Theorem (and related results) that I've yet found: "An Informal Exposition of Proofs of Godel's Theorems and Church's Theorem" by J. Barkley Rosser. Basically the only things this paper omits are the coding apparatus used to show that "$x$ is the Godel number of a provable sentence," and other similar sentences, are expressible; and Rosser's Trick, which reduces the number of assumptions required for Godel's Theorem to hold. Personally, I find this first omission to be justified: the coding apparatus is much easier to understand after one has seen the rest of the proof. The latter omission is kind of annoying, since Rosser's Trick is so pretty, but c'est la vie. Barring these omissions, however, Rosser's paper is basically entirely rigorous.

share|improve this answer
add comment

If you can read Spanish, an excellent text which both formally proves and philosophically treats both Incompleteness theorems is Carlos Ivorra Castillo's "Lógica y teoría de conjuntos" which is freely available on-line:

http://www.uv.es/ivorra/Libros/Logica.pdf

It treats as little recursion theory as it is needed to prove the results on logic.

share|improve this answer
    
Thank you. But, unfortunately, I can't read in spanish. I can't understand author's motivation for writing a book on such an important subject not using international language either. –  Sergei Tropanets Aug 5 '10 at 14:58
2  
The author explains in the following page, where he lists all the books he has written: uv.es/ivorra/Libros/Libros.htm that "I like to study math in my spare time, and my way of doing it is organizing everything I study in the form of books. Here is the result of almost all the math I've studied in that time." Perhaps that answers your question. –  Bruno Stonek Aug 5 '10 at 15:07
    
According to Wikipedia en.wikipedia.org/wiki/Spanish_language, Spanish is "the second most natively spoken language in the world", and is the official language in 21 countries, so I can't really understand Sergei's definition of an "international language". –  David FernandezBreton Jul 18 '12 at 0:49
add comment

Stephan Bilaniuk's: "A problem Course in Mathematical Logic". The only source I've found that satisfies all your requirements. And it's free.

share|improve this answer
add comment

For absolute beginner, I highly recommend Gödel’s Proof (Ernest Nagel with J. R. Newman, 1958). It can be supplemented with the ever popular Gödel, Escher, Bach by Douglas Hofstadter (1980) and I Am A Strange Loop by the same author. It would also benefit to study his biography Gödel: A Life of Logic by John L. Casti and Werner DePauli (2000) as well as the classic Forever Undecided by Raymond Smullyan.For serious study Gödel's Theorem in Focus by S.G.Shanker can serve as a stepping stone. And finally, why not - to borrow Abel- "study the master" himself from his Nachlass?

[Rudy Rucker in Infinity and the Mind discusses his meeting with Gödel as well as the logician's mysticism.]

share|improve this answer
1  
Although I have accepted Kaveh's answer, now I think that the best (so far) exposition of incompleteness theorems for theories formalized in arithmetical languages is Smorynski's paper (either for beginners in logic or for more experienced readers). But before that paper I would now recommend reading incompleteness theorems for theories formalized in, say, first order language with names for its symbols (Quine's version from 1940, for instance). Quine's treatment is much less technical and yet absolutely rigorous. –  Sergei Tropanets Dec 15 '11 at 13:37
add comment

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.