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

So what is it going to take for me to understand the proof of GIT? Maybe a blog... I know that sounds weird. So I'll try to explain.

Now that I have a nearly-four-month-long summer ahead of me with no teaching duties ("only" research projects will occupy my mind and my time), I have decided to give it another try. I am going to use this blog to take notes on what I am reading. I will write up the new stuff I just learned. I will write down unanswered questions I still have to explore, etc. Most importantly, I will force myself to post (at least) one entry each week. If I have made no progress during the week, I will have to admit it here, in writing. Will that be enough motivation to keep me going until I reach my goal? We'll see...

And what if nobody reads these posts? Ha! See, that cannot happen, because *I* am the primary target audience for this blog! And I know I will (re)read these posts.

Nevertheless, if you stumble upon this blog and would like to comment, fill in some blanks in my understanding, add reading suggestions, argue with my interpretations, etc., please be my guest. I would love to share my passion for GIT with fellow enthusiasts.

But for now, I guess it'll just be me and my buddy Kurt!


  1. Not sure if you know about this already but here's a good video series on the GITs - http://vimeo.com/album/2262409

    I'm only through 3 of them but they come highly recommended.

    1. Nick,

      Thanks a lot for pointing me to this video lecture series. I was not aware of it! It does look quite promising.