Gödel's Incompleteness Theorems

Introduction

• Gödel's Theorems: Among the most important results in modern logic, they explore the limits of provability in formal axiomatic theories.
  • First Theorem: States that in any consistent formal system with a certain degree of arithmetic, there are statements that cannot be proved or disproved.
  • Second Theorem: Such systems cannot prove their own consistency.
• Impact: Significant implications for philosophy of mathematics and logic, with some controversial applications in philosophy.

Key Concepts

• Formal System: A system of axioms and inference rules. A system is
  • Complete: If every statement or its negation is derivable.
  • Consistent: If no statement and its negation are both derivable.
• Gödel's First Theorem: Any consistent formal system capable of basic arithmetic (like ZFC) is incomplete.
• Gödel's Second Theorem: Such a system cannot prove its own consistency.

Formalized Theories

Arithmetical Theories

• Robinson Arithmetic (Q): Weakest standard system relevant to incompleteness and undecidability.
• Peano Arithmetic (PA): Includes induction axiom, more comprehensive.
• Primitive Recursive Arithmetic (PRA): Lies between Q and PA, involving primitive recursive functions.
• Second-order Arithmetic (PA2): Stronger system.

Beyond Arithmetic

• Theorems apply to systems like ZFC, provided systems like Q or PRA can be interpreted in them.
• Interpretability: If one theory can be translated into another, preserving properties like consistency.
• Exception: Some theories are complete and do not follow Gödel's theorems, e.g., Presburger arithmetic.

Church-Turing Thesis

• Gödel, Church, and Turing developed equivalent notions of computable functions and decidable sets.
• Distinction between decidable (recursive) and recursively enumerable (semi-decidable) sets.

First Incompleteness Theorem

Proof Outline

1. Diagonalization Lemma: Constructs self-referential sentences.
2. Gödel Sentence (GF): Can be shown to be neither provable nor disprovable in F if F is 1-consistent.
3. Rosser's Improvement: Refines proof to require only consistency, not 1-consistency.

• Non-standard Models: Exist for any theory satisfying the theorem, demonstrating the presence of non-intended interpretations.

Second Incompleteness Theorem

Proof Concept

• Utilizes arithmetized provability predicates to demonstrate that a system cannot prove its own consistency.
• Derivability Conditions: Conditions like Löb's conditions are necessary for the proof.
• Feferman's Approach: Offers an alternative proof using RE-formulas for axiom representation.

Related Results

Undecidability

• Theories containing Q are inherently incomplete and undecidable.
• Church's Theorem: First-order logic is undecidable.

Philosophical Implications

• Affects logicism, conventionalism, and debates on mechanism.
• Gödelian arguments against mechanism: Debate over whether human thought transcends machines.
• Gödel's work has spurred philosophical discussions on Platonism and the nature of mathematical truth.

Historical Context

• Gödel's discoveries were initially surprising but followed a backdrop of earlier discussions on the limits of formal systems.
• Mixed reception, with some misunderstanding and resistance, but ultimately recognized as groundbreaking.
• Gödel's work influenced philosophical thinking, including views on infinity, truth, and formalism.

Conclusion

• Gödel's incompleteness theorems have deep and far-reaching implications across mathematics, logic, and philosophy.
• They challenge foundational assumptions about formal systems, consistency, and the nature of proof.