General Question

Hacksawhawk's avatar

What are the requirements to understand Gödel's Incompleteness Theorems?

Asked by Hacksawhawk (518points) November 12th, 2011

So this might be a long shot, but hoping there are a bunch of mathematicians/logicians on Fluther I ask thee:

How much and what kind of math and logic must one master to be able to understand Gödel’s “On Formally Undecidable Propositions of Principia Mathematica and Related Systems”?

I realize that understanding differs from person to person, but ignoring that, it’s obvious that one cannot understand Gödel without the necessary knowledge of mathematics and logic.
Also, I’ve already read non-technical works explaining his theorems, but now I’m actually talking about his paper from 1931, and what is necessary to understand it.

Curious because this is at the moment sort of my goal to understand it.

Observing members: 0 Composing members: 0

4 Answers

LostInParadise's avatar

My familiarity with the theorem is mostly from Douglas Hofstadter’s book, Godel, Escher, Bach

The book gets a little too cute at times, but for the most part I enjoyed it. According to Hofstadter, most of the difficulty in the theorem comes from setting up the machinery for manipuating logical statements using arithmetic. What this book does is to assume the existence of this machinery and to provide a high level view of how it is used to prove the theorem. I recommend the book as a good introduction. I can’t help you much if you want to get into the low level details.

ratboy's avatar

The actual mathematics required is relatively simple—elementary number theory and primitive recursion. A greater obstacle is the formal logic; in order to grasp what Godel is doing, one must be familiar with some of the low level mechanics of formal derivations. In particular, it is crucial to understand freedom and bondage of variables and the notion of substituting a term for a variable in a formula. Godel’s paper probably isn’t the best place to start because the logical system and the notation he uses are seldom used today and his German mnemonics have been retained in the translation, so that it is difficult to find references for portions that prove hard to grasp.

The authoritative translation is found in the first volume of Godel’s Collected Works, where it is accompanied by expert commentaries. There is a translation by Martin Hirzel that attempts to incorporate modern terminology and English mnemonics.

Melvin Fitting’s Incompleteness in the Land of Sets presents the proof in the context of finite set theory, which simplifies the encoding.

gasman's avatar

I second @LostInParadise‘s vote for Hofstadter, who explains recursive self-reference like no other. Too cute? You mean like pushcorn or meta-genies? The dialogues? I’d say he’s being witty, clever, & entertainingly informative but not overdone. At times he uncannily anticipates a question or point of confusion and explains it in the next sentence. You can see I’m a big fan of Douglas Hofstadter’s writings.

gasman's avatar

I forgot to add “lol” to previous, lol.

I’d been racking my brain to remember where I recently saw a new explanation of Godel numbering based & proof of the theorem. It’s in James Gleick’s The Information. Quite readable and much shorter than Hofstadter, Gleick gives you the gist of it.

I’d say the only mathematical prerequisite is to understand symbolic logic and the concepts of prime numbers and factorization.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther