Gödel's incompleteness theorems

[hyperds]

I saw this explanation of Gödel's incompleteness theorems in another thread:

Godel found a way of encoding a statement to the effect of "This statement is unprovable" into the symbolic logic system defined in Principia Mathematica (PM). The notable aspect of the statement is that it is self-referential, which Godel managed to accomplish by encoding statements in PM into "Godel Numbers." Thus the actual statement in PM refers to its own Godel Number.

To boil it down into a nutshell, I'd say it means that any system which is expressive enough to be consistent and complete is also expressive enough to contain self-referential statements which doom it to incompleteness.

Is this correct? And does this mean that all unprovable statements in math, will take the form of a self-referential paradox? If this is true, I don't get why the incompleteness theorem is considered deep, if it is basically irrelevant to the rest of math, and only applies to carefully constructed paradoxical statements.

 

[Hurkyl]

And does this mean that all unprovable statements in math, will take the form of a self-referential paradox?

No. Or, at least, not obviously so. (But for completeness, I should remark, the Gödel statement isn't obviously self-referential either -- it only becomes apparent after going through the particular translation of formal logic into number theory)


Incompleteness is a normal thing. For example, $\forall x: x+x=0$ is an undecidable statement in the theory of an Abelian group -- there are groups where it's true and groups where it's false. This is good, because "the theory of an Abelian group" is supposed to describe many inequivalent kinds of things.


Sometimes, we want complete theories, and there are interesting ones. For example, the theory of real closed fields, which describes (in first-order logic) the arithmetic and ordering of the real numbers.



The main reason Gödel's first incompleteness theorem is interesting is that people generally thought one could find axioms to make make number theory complete, or to make set theory complete, etc.

 

[micromass]

I don't get why the incompleteness theorem is considered deep, if it is basically irrelevant to the rest of math, and only applies to carefully constructed paradoxical statements.

It is true that Godels incompleteness theorem is irrelevant to the rest of mathematics. And today, Godels theorem seems intuitively obvious. However, you must see this in it's context, let me sketch this for you:

Up until the 20th century, people have always done mathematics very informally. That is, they considered sets to be arbitrary collections of things and they thought it was obvious what a set was. However, one day came Russel and he showed everybody the set $\{x~\vert~x\notin x\}$ and he asked whether this set is an element of itself. This leads to an obvious paradox.

This lead to a very deep crisis in mathematics, as suddenly it seemed that mathematics was based on thin air (and it was). Enter Hilbert, who thought he had the solution. He would give a list of axioms and a list of inference rules and he would regard mathematics as the formal manipulation of symbols. Hilbert had the dream that he could give a set of axioms which completely descirbe mathematics, and furthemore he had the dream that in his system he could prove the consistency of his system.

So for over 30 years, people believed Hilbert to be correct and searched for a complete set of axioms. But then Godel showed that this was impossible. This was a huge surprise to all mathematicians of that time!

It nevertheless took some time for the first unprovable statement (that was not self-referential) to show up in set theory. This was the continuum hypothesis.