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 am very interested in learning the incompleteness theorem and its proof. But first I must know what things I need to learn first.
My current knowledge consists of basic high school education and the foundations of linear algebra and calculus which probably wont help but I figured it's worth mentioning.
I prefer that you recommend books as well as abstract subjects that I should learn. Also, a place where I can find the proof would be nice to have.

Thanks in advance!

share|improve this question

3 Answers 3

up vote 19 down vote accepted

Gödel's first incompleteness theorem tell us about the limitations of effectively axiomatized formal theories strong enough to do a modicum of arithmetic. So you need at least to have a notion of what an effectively axiomatized formal theory is, if you are to grasp what is going on. To understand the "formal theory" bit, it will help to have encountered a bit of formal logic; but a good intro to Gödel should explain the extra "effectively axiomatized" bit. After that, the basic argumentative moves in proving the first incompleteness theorem are surprisingly straightforward (and it was philosophically important to Gödel that this is so) -- though filling in some of the details can get fiddly: so you don't need to bring much background maths to the table in order to get to understand the proof.

My own book An Introduction to Gödel's Theorems was written for people who don't have much maths background but have done an intro logic course, and lots of people seem to find it pretty clear (I assume no more than some familiarity with elementary logic). There is also a freely available abbreviated version of some of my book in the form of lecture notes at http://www.logicmatters.net/resources/pdfs/gwt/GWT.pdf There are suggestions for other reading in the relevant sections of the study guide at http://www.logicmatters.net/tyl

You might however find it very helpful to look at Torkel Franzen's admirable little book Gödel's Theorem: An Incomplete Guide to its Use and Abuse which gives an informal presentation and will give you some understanding of what's going on, before deciding whether to tackle a book like mine which goes into the mathematical details.

share|improve this answer

For the proof you may want to actually take a look at Gödel's 1931 paper here. As for gentle introduction, along Douglas Hofstadter's Gödel,Escher, Bach I highly recommend Gödel's Proof by Ernest Nagel and James Newman. A preview can be found in Google books, but the actual book is really lucid and short and starts off with Problem with Inconsistency.

share|improve this answer
2  
Gödel 1931 is a masterpiece of compression. It isn't too surprising, perhaps, that even a great mathematician like Zermelo initially didn't understand it. So look at the paper by all means -- but perhaps only after you've taken a look at some modern presentations. –  Peter Smith Oct 2 '12 at 11:27

There are several different proofs of Godel's incompleteness theorem. Since there are so many differences, what you need to know depends on what proof version you decide to peruse. The problem is that many simpler proofs skirt over the important points, which is unsatisfactory if you are trying to get a thorough understanding. If, as seems likely by your question, you want to understand Godel's original proof, most other proofs do not give a good idea of how Godel's proof operates. I would suggest that you start with a simplified version of Godel's proof at Godel's proof simplified, which covers the essential points. From there you can go on to study Godel's original proof, which can be viewed at Godel's proof Meltzer translation.

To understand these, you will need a basic knowledge of algebra and of propositional logic and predicate logic (see for example, Wikipedia for the basics). Also a good starting point for the fundamentals of logic can be found at Shunichi Toida logic web pages

share|improve this answer
3  
Be warned -- the "Gödel's proof simplified" link leads to a site that alleges "there are several ways you can show that [Gödel's] proof is logically absurd" ... Sigh. –  Peter Smith Oct 6 '12 at 7:49
1  
DO NOT go to the Godel Proof simplified link. It is written by jams Myer who is really a nut who cannot be convinced that Gödel's proof is valid. –  Nisaim Feb 12 at 19:26

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.