First Incompleteness Theorem

Mathematical Logic · Axiom Academy

LESSON Gödel's First Incompleteness Theorem One of the most profound results in mathematical logic: every consistent formal system powerful enough to describe arithmetic is necessarily incomplete 1. The Statement of the Theorem Gödel's First Incompleteness Theorem applies to any formal system that is: Consistent: The system does not prove contradictions Recursive: There is an algorithm to check if something is an axiom or valid proof Sufficiently strong: Can express basic arithmetic (Peano Arithmetic) Gödel constructed a special sentence G that essentially says: This is similar to the Liar's Paradox ("This sentence is false"), but crucially different: instead of truth, it speaks about provability within a formal system. Through an ingenious encoding called Gödel numbering , Gödel showed how to construct such a sentence that refers to its own provability. 3. Why G Must Be True (If PA is Consistent) Let's prove that G is actually true by considering both possibilities: Case 1: Suppose G is provable. But G says "I am not provable" So PA would prove a false statement This means PA is unsound (proves false things) An unsound system is inconsistent Contradiction! (We assumed PA is consistent) Case 2: Suppose ¬G is provable. But we assumed PA is consistent, so if ¬G is provable, then G is NOT provable So PA proves something false (that G is provable when it isn't)

This is the written version of the interactive lesson above. See the full Mathematical Logic course.