Key Concepts of Incompleteness Theorems

Why This Matters

The incompleteness theorems represent one of the most profound discoveries in mathematical logic—they reveal fundamental boundaries on what formal systems can achieve. You're being tested on understanding why these limits exist, how self-reference and diagonalization create undecidable statements, and what distinguishes different types of incompleteness results. These concepts connect directly to proof theory's core questions: What can be proven? What does consistency guarantee? And where do formal methods necessarily fall short?

Don't just memorize theorem names and dates. Know what mechanism each result exploits—whether it's self-reference, truth vs. provability gaps, or computational complexity. Understand how these theorems relate to each other: some extend others, some offer alternative proofs, and some demonstrate incompleteness through entirely different routes. When an FRQ asks you to explain why a system can't prove its own consistency, you need to articulate the underlying logic, not just cite Gödel.

---

Self-Reference and Diagonalization

These foundational results exploit the ability of formal systems to encode statements about themselves. The key mechanism: when a system is powerful enough to represent its own syntax, it can construct sentences that refer to their own provability status.

Gödel's First Incompleteness Theorem

• Any consistent system capable of expressing basic arithmetic contains true but unprovable statements—this establishes that completeness and consistency cannot coexist in sufficiently powerful systems
• Gödel sentences achieve undecidability through self-reference, essentially saying "this statement is not provable in system $S$"
• Diagonalization provides the construction method, encoding proof-theoretic concepts as arithmetic statements via Gödel numbering

Gödel's Second Incompleteness Theorem

• No consistent system can prove its own consistency—if $S$ proves "$S$ is consistent," then $S$ is actually inconsistent
• Extends the first theorem by applying the same self-referential machinery to the consistency statement itself
• Hilbert's program was directly impacted, showing that finitary consistency proofs for mathematics are impossible from within

Löb's Theorem

• If a system proves "if this statement is provable, then it's true," the statement must actually be provable—written formally: if $S \vdash \Box P \rightarrow P$, then $S \vdash P$
• Strengthens understanding of self-reference by showing provability has unexpected logical properties beyond simple truth
• Provability logic emerges from this work, formalizing how $\Box$ (the provability predicate) behaves in consistent systems

---

Truth vs. Provability

These results formalize the gap between what's true and what's provable, establishing that truth itself resists complete formal capture.

Tarski's Undefinability Theorem

• Truth for a language cannot be defined within that same language—any sufficiently expressive system lacks a truth predicate for its own sentences
• Diagonal argument parallels Gödel's method but targets truth rather than provability, showing the liar paradox has formal consequences
• Meta-language requirement means truth must always be defined at a higher level, creating an infinite hierarchy of languages

Henkin's Completeness Theorem

• Every consistent set of first-order sentences has a model—syntactic consistency guarantees semantic satisfiability
• Contrasts with incompleteness by showing first-order logic is complete in the sense that all logical truths are provable
• Completeness vs. incompleteness distinction is crucial: logical completeness (Henkin) differs from arithmetic completeness (Gödel)

---

Strengthened and Alternative Approaches

These theorems either strengthen Gödel's original results or demonstrate incompleteness through different mechanisms entirely.

Rosser's Theorem

• Removes the $\omega$-consistency requirement from Gödel's proof, needing only simple consistency for incompleteness
• Rosser sentences use a clever modification: "if this is provable, there's a shorter proof of its negation"
• Technically stronger because it applies to a broader class of systems while achieving the same incompleteness conclusion

Chaitin's Incompleteness Theorem

• Algorithmic complexity creates incompleteness—there exists a constant $c$ such that no statement "$K(s) > c$" can be proven, where $K$ is Kolmogorov complexity
• Information-theoretic approach provides an entirely different route to incompleteness, independent of self-reference
• Randomness connection shows that proving strings are complex (incompressible) exceeds formal systems' capabilities

---

Computability Connections

These results link incompleteness to fundamental questions about what can be computed or decided algorithmically.

Church-Turing Thesis

• Effective computability equals Turing computability—any algorithmically computable function can be computed by a Turing machine
• Undecidability results follow immediately: the halting problem, provability in arithmetic, and validity in predicate logic are all uncomputable
• Foundational bridge connects Gödel's incompleteness to computability theory, showing unprovability and uncomputability are deeply related

---

Natural Independence Results

These theorems demonstrate that incompleteness isn't just a logical curiosity—it affects "natural" mathematical statements that mathematicians actually care about.

Paris-Harrington Theorem

• A strengthened Ramsey theorem is true but unprovable in Peano Arithmetic—the first "natural" combinatorial independence result
• Uses ordinal analysis to show PA cannot prove the statement because it requires induction up to $\varepsilon_0$
• Demonstrates practical incompleteness by showing standard axioms miss genuinely mathematical truths, not just self-referential constructions

Goodstein's Theorem

• Every Goodstein sequence eventually reaches zero—true but unprovable in PA despite being a simple statement about natural numbers
• Hereditary base-$n$ notation creates sequences that grow enormously before collapsing, requiring transfinite induction to prove termination
• Ordinal arithmetic at level $\varepsilon_0$ is essential, illustrating exactly what PA lacks

---

Quick Reference Table

---

Self-Check Questions

1. Both Gödel's First Theorem and Tarski's Undefinability Theorem use diagonalization. What is the key difference in what each theorem shows cannot be captured internally?

2. How does Rosser's Theorem strengthen Gödel's First Theorem, and why does this matter for the class of systems to which incompleteness applies?

3. Compare Paris-Harrington and Goodstein's Theorem: what do they share as independence results, and how do their mathematical domains differ?

4. Explain why Henkin's Completeness Theorem does not contradict Gödel's Incompleteness Theorems. What distinction resolves this apparent tension?

5. If an FRQ asks you to explain incompleteness without using self-reference, which theorem provides the best alternative approach, and what mechanism does it use instead?