Showing posts with label Godel Escher Bach. Show all posts
Showing posts with label Godel Escher Bach. Show all posts

Tuesday, May 14, 2013

I just want to understand the proof of Gödel's incompleteness theorems

So this is it! Summer 2013... This is when I get to master the proof of Gödel's incompleteness theorems (thereafter: GIT).

I discovered GIT as an undergraduate student in one of my Artificial Intelligence courses. My instructor was reading Gödel, Escher, Bach and was raving about the book. He even took some of our exam problems from it. But what I remember most is the outline of the proof of GIT, more precisely the first theorem. To be honest, the only part of it that stuck with me was the idea of numbering the formulas. Of course, at the time, I bought a copy of the book. I liked many parts of it but I never finished it.

Years later, while I was teaching computability theory and other computer science topics, I encountered GIT several times. At some point, I decided I wanted to understand the proof of GIT. 

First, I read the classic "Gödel's Proof" by Nagel and Newman. That is a concise and user-friendly overview of the proof. But it was only a proof sketch. So I looked at some textbooks on formal logic, which were neither concise nor user-friendly. I still did not understand the proof.

Finally, a couple of years ago, I came across a promising volume: "Introduction to Gödel’s Theorems" by Peter Smith. I read the first few chapters but then ran out of time (and motivation) to finish it. The following year, I made another attempt: I had to start from scratch and did not get any farther into it the second time around...