Undecidable Statements

Mathematical Logic · Axiom Academy

EXAMPLE Undecidable Statements Explore concrete examples of statements that cannot be proven or disproven within their formal systems. If were provable in PA, then PA would prove a false statement (since says it's not provable), making PA inconsistent. If were disprovable (i.e., were provable), then there would be a proof of , contradicting what says. Assuming PA is consistent, can be neither proved nor disproved—it's undecidable. Yet semantically, is true because it accurately describes its own unprovability! If PA is consistent, then cannot be proved within PA itself. A consistent system cannot prove its own consistency—this is a fundamental limitation. If PA could prove , it would prove the Gödel sentence (since ), contradicting the First Incompleteness Theorem. We believe PA is consistent (from outside the system), but PA cannot establish this fact about itself. Write in complete base-2 notation (including exponents recursively in base 2). Replace all 2's with 3's to get the first term . Subtract 1 from and write in complete base-3 notation. Replace all 3's with 4's to get , subtract 1, and continue... The sequence continues to grow enormously before eventually decreasing to 0. Goodstein's Theorem is true (provable in ZFC set theory using ordinal numbers). However, it is not provable in Peano Arithmetic (proven by Kirby and Paris, 1982). The proof requires transfinite induction up to ordinal , which is beyond PA's proof-theoretic strength.

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