20
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – David Corwin
    Commented Aug 1, 2010 at 12:06
  • $\begingroup$ @Davidac897: Thank you, I've read this text. But my question concerns with incompleteness theorems, not completeness ones. $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 12:10
  • $\begingroup$ @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 $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 12:14
  • $\begingroup$ V.A.Uspensky: archive.org/details/GodelsIncompletenessTheorem $\endgroup$
    – TT_ stands with Russia
    Commented Feb 12, 2015 at 23:23

12 Answers 12

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I was not aware of Girard's book. It's amazing book! (not only on incompleteness). Thank you very much! $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 23:51
  • $\begingroup$ "For beginners" doesn't necessarily mean "elementary" :) $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 23:56
  • 3
    $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Commented Aug 2, 2010 at 0:02
  • $\begingroup$ @Carl Mummert: I'll check it out, Thanks! $\endgroup$
    – Sergei Tropanets
    Commented Aug 2, 2010 at 0:15
  • $\begingroup$ 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. :) $\endgroup$
    – Kaveh
    Commented Aug 2, 2010 at 4:57
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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.>> $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 11:50
  • $\begingroup$ 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). $\endgroup$
    – Antonio E. Porreca
    Commented Aug 1, 2010 at 12:11
  • $\begingroup$ 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. $\endgroup$
    – Carl Mummert
    Commented Aug 1, 2010 at 12:25
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

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

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

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ <<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. $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 11:56
  • 1
    $\begingroup$ Yes - despite the unserious name, Franzen's book is very thorough. I would also recommend it to beginners. $\endgroup$
    – Carl Mummert
    Commented Aug 1, 2010 at 12:24
  • $\begingroup$ @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. $\endgroup$
    – Pete L. Clark
    Commented Aug 1, 2010 at 12:30
  • 4
    $\begingroup$ @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. $\endgroup$
    – Sergei Tropanets
    Commented Aug 1, 2010 at 12:55
3
$\begingroup$

I would naturally recommend my own piece:

the entry "Gödel's Incompleteness Theorems" in the Stanford Encyclopedia of Philosophy:

http://plato.stanford.edu/entries/goedel-incompleteness/

It is written beginners in mind; it should be reliable (naturally, I had to cut some corners), and it is free.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Sergei Tropanets
    Commented Aug 5, 2010 at 14:58
  • 3
    $\begingroup$ 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. $\endgroup$
    – Bruno Stonek
    Commented Aug 5, 2010 at 15:07
  • 4
    $\begingroup$ 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". $\endgroup$
    – David Fernandez-Breton
    Commented Jul 18, 2012 at 0:49
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 for Mendelson's book, though I think Girard's book beats it. :) $\endgroup$
    – Kaveh
    Commented Aug 2, 2010 at 4:55
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sergei Tropanets
    Commented Dec 15, 2011 at 13:37
  • $\begingroup$ @SergeiTropanets Are you refeering to Quine's Mathematical Logic book? $\endgroup$
    – Red Banana
    Commented Oct 10, 2014 at 4:37
0
$\begingroup$

I learned this from Foundations of Logic and Theory of Computation:

http://sqig.math.ist.utl.pt/cgi-bin/uncgi/bib2html.tcl?author=acs&entrytype=book

I quite liked it. Here is a preprint:

http://sqig.math.ist.utl.pt/pub/SernadasA/08-SS-FLTC.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .