Godel's incompleteness Theorems

• Print

Godel's incompleteness theorems are two celebrated theorems proved by Kurt Godel in 1930.

The first states:

In any consistent axiomatic system (formal system of mathematics) sufficiently strong to allow one to do basic arithmetic, one can construct a statement about natural numbers that can be neither proved nor disproved within that system.

An axiomatic system is one with a recursive set of axioms; equivalently, the theorems of the system can be generated by a Turing machine. The statement which cannot be proved nor disproved within the system is furthermore true in the sense that what it asserts about the natural numbers in fact holds. Because the system fails to prove a true statement, it is said to be incomplete. In other words, Godel's first incompleteness theorem says that any sufficiently strong formal system of mathematics is either inconsistent or incomplete.

Godel's second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states:

Any sufficiently strong consistent system cannot prove its own consistency.

In essence, the proof of the first theorem consists of constructing the statement

p = "This statement cannot be proven"

within a formal axiomatic system. As such, it can be seen as a modern variant of the Liar paradox.

If the axiomatic system is consistent, Godel's proof shows that p (and its negation) cannot be proven in the system. Therefore p is true (p claims not to be provable, and it isn't) yet it cannot be formally proved in the system.

For the second theorem, let p stand for the undecidable sentence constructed above, and assume that the consistency of the system can be proven from within the system itself. We have seen above that if the system is consistent, then p is not provable. The proof of this implication can be formalized in the system itself, and therefore the statement "p is not provable", or "not P(p)" can be proven in the system.

But this last statement is equivalent to p itself (and this equivalence can be proven in the system), so p can be proven in the system. This contradiction shows that the system must be inconsistent.