Gödel's Proof

Summary

Gödel's Proof by Ernest Nagel and James Newman is a concise and accessible explanation of Kurt Gödel's incompleteness theorem, which is among the most important and profound results in mathematics.

Gödel showed that within any sufficiently powerful formal mathematical system (those that allow recursion), there are true statements that cannot be proven within that system (or that there are contradictions within the system).

This idea of recursion is important to the ideas of Gödel because he uses it as part of the algorithm to construct the Gödel sentences that break the formal systems and shows them to be incomplete. It is related to the idea of the Halting Problem worked on by Alan Turing which can be seen as a special case construction of a Gödel sentence within the formal system of Turing machines based mathematics.

The historical context of Gödels ideas is interesting, back then mathematicians like David Hilbert, Bertrand Russell and Alfred North Whitehead, tried to create formal systems, where, with a set of axioms and logical rules to transform these axioms you could mechanistically create all the rest of mathematics. This idea of formalization would mean that you could do math without creativity. It's similar to the question of determinism in philosophy and Gödel showed mathematics has truths outside of the things that follow from any set of axioms and rules.

Formal systems should be both complete (able to prove every true statement) and consistent (able to avoid proving contradictions). Gödel showed that this is impossible to achieve in praxis.

The way he did this is by using mathematics itself to encode formal systems. He developed a way to assign numbers to every symbol, formula, and proof in a formal system, a process called Gödel numbering. This allowed him to translate statements about logic and proofs into statements about numbers.

This "arithmetization" enabled Gödel to construct mathematical statements that could make reference to themselves, similar to self-referential statements in natural language (e.g., "This statement is false"). This self-reference is crucial to Gödel's proof.

From this followed his two incompleteness theorems:

1. In any sufficiently powerful formal system (such as arithmetic), there are true statements that cannot be proven within the system.

2. No consistent formal system that includes basic arithmetic can prove its own consistency. In other words => a system cannot demonstrate, using its own rules, that it is free from contradictions.

This is how he got there.

Gödels Proof Summarized:

1. Arithmetization: Assign numbers to every symbol, formula, and proof.
2. Self-Reference: Construct a self-referential mathematical statement that asserts its own unprovability.
3. Incompleteness: Demonstrate that this statement cannot be proven within the system, leading to the conclusion that the system is incomplete.

The result of Gödels work is that we now know that mathematics has limitations, just like other endeavours of human knowledge acquiry. The incompleteness theorems also suggest that human intuition and creativity might play a role in mathematics because we know that there are truths that cannot be reached through formal procedures alone.

This makes Gödels proofs and theorems some of the most important work in all of mathematics and philosophy.