12.1.1 Gödel’s Incompleteness Theorem

Kurt Gödel was born in Brno (then in Austria-Hungary, now in the Czech Republic) in 1906. Gödel proved that the axiomatic system in Principia Mathematica could not be complete and consistent. More generally, Gödel showed that no powerful axiomatic system could be both complete and consistent: no matter what the axiomatic system is, if it is powerful enough to express a notion of proof, it must also be the case that there exist statements that can be expressed in the system but cannot be proven either true or false within the system.

Gödel's proof used construction: to prove that Principia Mathematica contains statements which cannot be proven either true or false, it is enough to find one such statement. The statement Gödel found:

$G_{PM}$: Statement $G_{PM}$ does not have any proof in the system of Principia Mathematica.

Similarly to Russel's Paradox, this statement leads to a contradiction. It makes no sense for $G_{PM}$ to be either true or false:

Statement $G_{PM}$ is provable in the system. If $G_{PM}$ is proven, then it means $G_{PM}$ does have a proof, but $G_{PM}$ stated that $G_{PM}$ has no proof. The system is inconsistent: it can be used to prove a statement that is not true.
Statement $G_{PM}$ is not provable in the system. Since $G_{PM}$ cannot be proven in the system, $G_{PM}$ is a true statement. The system is incomplete: we have a true statement that is not provable in the system.

The proof generalizes to any axiomatic system, powerful enough to express a corresponding statement $G$:

$G$: Statement $G$ does not have any proof in the system.

For the proof to be valid, it is necessary to show that statement G can be expressed in the system.

To express $G$ formally, we need to consider what it means for a statement to not have any proof in the system. A proof of the statement $G$ is a sequence of steps, $T_0$, $T_1$, $T_2$, $\ldots$, $T_N$. Each step is the set of all statements that have been proven true so far. Initially, $T_0$ is the set of axioms in the system. To be a proof of $G$, $T_N$ must contain $G$. To be a valid proof, each step should be producible from the previous step by applying one of the inference rules to statements from the previous step.

To express statement $G$ an axiomatic system needs to be powerful enough to express the notion that a valid proof does not exist. Gödel showed that such a statement could be constructed using the Principia Mathematica system, and using any system powerful enough to be able to express interesting properties. That is, in order for an axiomatic system to be complete and consistent, it must be so weak that it is not possible to express this statement has no proof in the system.