Gödel’s incompleteness theorems

Gödel’s incompleteness theorems
http://en.wikipedia.org/wiki/G%C3%B6del’s_incompleteness_theorems

The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics.

For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system.

The second incompleteness theorem, an extension of the first, shows that such a system cannot demonstrate its own consistency.

Relation to the liar paradox
The liar paradox is the sentence “This sentence is false.” An analysis of the liar sentence shows that it cannot be true (for then, as it asserts, it is false), nor can it be false (for then, it is true). A Gödel sentence G for a theory T makes a similar assertion to the liar sentence, but with truth replaced by provability: G says “G is not provable in the theory T.”

Extensions of Gödel’s original result
… it is common to state the effectiveness and expressiveness conditions as hypotheses for the incompleteness theorem, so that it is not limited to any particular formal theory. The terminology used to state these conditions was not yet developed in 1931 when Gödel published his results.

the epistemological relevance of the second incompleteness theorem

Examples of undecidable statements
There are two distinct senses of the word “undecidable” in mathematics and computer science. The first of these is …

Limitations of Gödel’s theorems
The conclusions of Gödel’s theorems are only proven for the formal theories that satisfy the necessary hypotheses.
Not all axiom systems satisfy these hypotheses, …

Gödel’s theorems only apply to effectively generated (that is, recursively enumerable) theories.
If all true statements about natural numbers are taken as axioms for a theory, then this theory is a consistent, complete extension of Peano arithmetic (called true arithmetic) for which none of Gödel’s theorems apply in a meaningful way, because this theory is not recursively enumerable.

Minds and machines
Authors including J. R. Lucas have debated what, if anything, Gödel’s incompleteness theorems imply about human intelligence. Much of the debate centers on whether the human mind is equivalent to a Turing machine, or by the Church–Turing thesis, any finite machine at all. If it is, and if the machine is consistent, then Gödel’s incompleteness theorems would apply to it.