For years after I first encountered Gödel’s incompleteness theorems, they had utterly baffled me (just look at the Wikipedia page and tell me if it is comprehensible). So I dismissed it as one of those inexplicable-to-non-mathematicians things.
Recently though, I’ve been reading Douglas Hofstadter’s Gödel, Escher, Bach: An Eternal Golden Braid which lays the foundation meticulously and slowly that culminate in the explaining of the theorems. This article <Kurt Gödel and the romance of logic> also gives a comprehensible, intuitive, and succinct explanation of the first incompleteness theorem:
… He did this by an ingenious method now called “gödel numbering,” which assigns a unique number to each symbol of the system (+, -, 1, 2, etc), each sequence of symbols (this would include every proposition, such as “2 + 2 = 4”), and each sequence of sequences of symbols (this would include every proof). Tallied up in this way, any arithmetical statement could be represented by a unique number, which in turn allows arithmetical statements (statements about numbers) to be about arithmetical statements.
Thus, he showed how it was possible for an arithmetical statement about two numbers to be also a meta-mathematical statement about whether a particular arithmetical statement can or cannot be proven in the system of—say—Principia Mathematica. This allowed him to create the self-reference needed for a “strange loop” and to create an arithmetical statement that in effect says, in an echo of Epimenides, “I am not provable in the Principia Mathematica system.”
If the system of Principia Mathematica is consistent, then this statement must be true. Why? Because, if it were false, then it would be provable in the Principia system, and, as it says that it is not provable, this would introduce an inconsistency into the system. So, if the system is consistent, then the statement must be true. But, if it is true, and (this is the crucial bit) it expresses an arithmetical statement, then it expresses an arithmetical truth—an arithmetical truth that cannot, by virtue of its own truth be proven in Principia Mathematica. In sum, if the system of arithmetic is consistent, then it is necessarily incomplete.
I’m not sure if I would find the excerpt above comprehensible without reading the book, though. I think I’m starting to get it. And the next level is to be able to make other people understand the theorem. We will see if I gain more aufklärung after finishing the book.