The best text to study both incompleteness theorems - MathOverflow

The best text to study both incompleteness theorems

2010-08-01T10:59:23Z

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.

Answer by Antonio E. Porreca for The best text to study both incompleteness theorems

2010-08-01T11:29:47Z

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.

Answer by Pete L. Clark for The best text to study both incompleteness theorems

2010-08-01T11:31:05Z

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.

Answer by Brendan Cordy for The best text to study both incompleteness theorems

2010-08-01T15:42:35Z

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.

Answer by Andrew L for The best text to study both incompleteness theorems

2010-08-01T18:54:38Z

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.

Answer by Kaveh for The best text to study both incompleteness theorems

2010-08-01T22:43:57Z

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.

Answer by Noah S for The best text to study both incompleteness theorems

2010-08-05T13:27:01Z

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.

Answer by Bruno Stonek for The best text to study both incompleteness theorems

2010-08-05T14:49:51Z

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.

Answer by Eran for The best text to study both incompleteness theorems

2010-12-24T21:30:35Z

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.

Answer by Zeeshan Mahmud for The best text to study both incompleteness theorems

2011-12-15T01:53:58Z

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.]

Answer by Dave for The best text to study both incompleteness theorems

2012-07-17T21:28:19Z

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