What is the prerequisite knowledge for learning Godel's incompleteness theorem

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!

Solution 1:

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.

Solution 2:

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.