Gödel's incompleteness theorems

Gödel's incompleteness theorems is the name given to two theorems (true mathematical statements), proved by Kurt Gödel in 1931. They are theorems in mathematical logic.

Mathematicians once thought that everything that is true has a mathematical proof. A system that has this property is called complete; one that does not is called incomplete. Also, mathematical ideas should not have contradictions. This means that they should not be true and false at the same time. A system that does not include contradictions is called consistent. A system is a collection of theorems (logical consequences) based on axioms (basic assumptions). Axioms are statements that are accepted as true, and need no proof.

Gödel said that every non-trivial formal system (consistent and axiomatic system with theorems listable by following an algorithm) is incomplete and not provably consistent:

1. There will always be questions that cannot be answered, using a certain set of axioms; there are truths that cannot be proved using the axioms of the system.
2. You cannot prove that a system of axioms is consistent according to the axioms of the system.

Outline of Proof of Gödel’s Theorems

The proof of Gödel’s theorems is based on forming and considering special self-referential statements.

One way to prove the theorems is to consider the first theorem before considering the second theorem. There are three parts in this proof:

A. Consider the first theorem and the truth of this first statement “This statement cannot be proved”: proving this first statement would be a contradiction because there would then be a proof for a statement that cannot be proved. For the sake of the consistency of the system, the first statement and hence the first theorem are therefore true but unprovable.

B. Recall from part A that if we were able to prove the first statement then our system would be inconsistent. Thus to prove the consistency of the system, we must prove that the first statement is not provable (ie: prove the contrapositive of the claim “if we were able to prove the first statement then our system would be inconsistent”). Because of self-reference in the first statement “this statement cannot be proved” (ie: proving the first statement is not provable is proving the first statement), therefore proof of the consistency of the system requires proof of the first statement.

C. Recall in part A that consistency of the system is why the first statement is true and unprovable. Hence by the truth of the first statement and the conclusion in part B, it follows that the consistency of the system cannot be proved with the axioms of the system. Hence the second theorem is established. The truth of the first theorem is established in part A.

Importance of Gödel‘s Theorems

The first theorem is important to mathematicians because it proves that it is impossible to create a set of axioms that explains everything in maths. The second theorem is important because it proves that the soundness of a system, soundness means only logically valid theorems are provable, cannot be proved; this means that you know that you cannot be assured that all proofs conclude in truths.

Some related topics

• Hilbert's second problem.
• Philosophy of mathematics