First Incompleteness Theorem: Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; that is, there are statements of the language of F which can neither be proved nor disproved in F.
More precisely: If F is a formally axiomatized theory containing basic arithmetic, then F cannot be both consistent and complete. In particular, if F is consistent, there exists a sentence G that is expressible in the language of F, such that neither G nor its negation is provable in F.
Second Incompleteness Theorem: For any consistent formal system F within which a certain amount of elementary arithmetic can be carried out, the consistency of F cannot be proved within F itself.
More precisely: If F is a consistent, effectively axiomatized formal theory that can represent elementary arithmetic, then F ⊬ Con(F), where Con(F) is a statement asserting the consistency of F.
To understand this proof, you should be familiar with:
Gödel's Incompleteness Theorems demonstrate fundamental limitations of formal mathematical systems. Intuitively, the First Incompleteness Theorem shows that in any consistent mathematical system capable of expressing basic arithmetic, there will always be true statements that cannot be proven within the system itself. This is often compared to the Liar Paradox (“This statement is false”), but formulated rigorously within mathematical logic.
The Second Incompleteness Theorem extends this result to show that such systems cannot prove their own consistency unless they are actually inconsistent. This creates a fundamental epistemic limitation: we cannot use a formal system to fully verify itself.
These theorems have profound implications for the foundations of mathematics, the philosophy of mathematics, and theoretical computer science.
We will outline a proof of Gödel's First Incompleteness Theorem, which is necessarily complex and multi-staged.
Main Proof (First Incompleteness Theorem):
Step 1: Develop a method of arithmetization (Gödel numbering).
We assign unique natural numbers to every symbol, formula, and proof in our formal system F. This allows us to “talk about” the syntax of F using the language of arithmetic.
For example: - Assign numbers to logical symbols: “¬” might be 1, “∧” might be 3, etc. - Assign numbers to variables: “x₁” might be 11, “x₂” might be 13, etc. - Use prime factorization to encode sequences: the formula “x₁ = x₂” might be encoded as 2^11 × 3^5 × 5^13, where 5 is the code for “=”.
Step 2: Show that syntactic properties and relations are primitive recursive.
Using this encoding, we can show that important syntactic properties and relations like “n is the Gödel number of a formula,” “n is the Gödel number of an axiom,” and “n is the Gödel number of a proof of the formula with Gödel number m” are all primitive recursive and thus representable in F.
Step 3: Construct a self-referential formula.
Using a diagonal lemma, we construct a formula G that, in essence, states: “This formula is not provable in F.”
More precisely, we construct a formula G such that G ↔ ¬Prov(⌜G⌝) is provable in F, where: - ⌜G⌝ is the Gödel number of G - Prov(n) is a formula representing “n is the Gödel number of a provable formula”
Step 4: Analyze the consequences.
Now we consider two cases: 1. If G is provable in F, then ¬Prov(⌜G⌝) is also provable (by the equivalence). But this contradicts the fact that Prov(⌜G⌝) must be true if G is provable. This is a contradiction, so G cannot be provable in F.
2. If ¬G is provable in F, then Prov(⌜G⌝) is provable (by the equivalence). But since ¬G is provable, G is not provable, so Prov(⌜G⌝) is false. This means F proves a false statement, making F inconsistent.
Therefore, if F is consistent, neither G nor ¬G can be proven in F, making F incomplete. ■
Main Proof (Second Incompleteness Theorem):
The Second Incompleteness Theorem follows from the First by analyzing the structure of the proof more carefully.
Step 1: Formalize the proof of the First Incompleteness Theorem within F.
We show that the proof of G ↔ ¬Prov(⌜G⌝) can be formalized within F itself.
Step 2: Show that consistency implies G.
We can formalize within F the statement: Con(F) → G, where Con(F) expresses the consistency of F.
Step 3: Derive the impossibility of proving consistency.
If F could prove Con(F), then F could also prove G (by modus ponens from Steps 1 and 2). But we know from the First Incompleteness Theorem that F cannot prove G if F is consistent. Therefore, F cannot prove Con(F). ■
Alternative Proof 1: Using Computability Theory
A modern approach uses concepts from computability theory to prove Gödel's results:
Computability-based proof of Incompleteness Theorems
Alternative Proof 2: Using the Halting Problem
Another approach relates the Incompleteness Theorems to Turing's Halting Problem:
Gödel's Incompleteness Theorems have numerous applications:
1. Foundations of Mathematics: The theorems showed that Hilbert's program to find a complete and consistent axiomatization of all mathematics was impossible.
2. Limitations of Formal Systems: They demonstrate inherent limitations in formal systems, showing that mathematical truth exceeds formal provability.
3. Computer Science: They relate to the unsolvability of the Halting Problem and other undecidable problems in computation.
4. Philosophy of Mind: Some philosophers, like Lucas and Penrose, have used the theorems to argue against the computability of human thought.
5. Metamathematics: They led to new fields studying the relative strength of different formal systems.
Kurt Gödel (1906-1978) proved the Incompleteness Theorems in 1931 in his paper “Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” (“On Formally Undecidable Propositions of Principia Mathematica and Related Systems I”).
The theorems came at a critical time in the foundations of mathematics, particularly in response to Hilbert's program, which sought to formalize all of mathematics and prove this formalization's consistency. Gödel's work showed fundamental limitations to this program.
The initial reception was one of shock in the mathematical community, as it upended widely held beliefs about the power and completeness of formal mathematics. John von Neumann immediately recognized the significance of the result, while it took others longer to fully appreciate its implications.