Gödel's Incompleteness Theorem

Gödel's Incompleteness Theorems are two theorems in mathematical logic that were proved by the mathematician Kurt Gödel.

They show that any formal system of mathematics that is powerful enough to express basic arithmetic is either incomplete or inconsistent.

The First Incompleteness Theorem states that there will always be true mathematical statements that the system cannot prove.

Example: Consider the Peano axioms, which are a set of axioms used to define the natural numbers in mathematics. These axioms are believed to be consistent and complete, meaning that every true statement about the natural numbers can be proved using them.

However, Gödel's First Incompleteness Theorem shows that even in this seemingly complete system, there are true statements that cannot be proven using the axioms. Specifically, Gödel constructed a statement that says "This statement cannot be proved using the Peano axioms."

If this statement were false, then it would be possible to prove it using the axioms, which would contradict its assertion. On the other hand, if it were true, then it would be a true statement that cannot be proven using the axioms, as it asserts.

The Second Incompleteness Theorem states that any system that is powerful enough to express basic arithmetic must rely on assumptions that cannot be proven within the system itself.

Example: Consider the system of first-order logic itself, which is used as the foundation for many mathematical systems. It is impossible to prove the consistency of first-order logic using the tools of first-order logic itself.

This means that we need to rely on some external method to establish the consistency of the system, such as using meta-mathematical techniques like model theory.