Introduction to Goodstein's Theorem

• Theorem developed by Ruben Goodstein in 1944
• Demonstrates unprovable mathematical statement with extremely fast-growing sequences
• Example starting with number 19

Hereditary Base 2 Representation Setup

• Convert numbers to powers of 2: 19 = 16 + 2 + 1 = 2^4 + 2 + 1
• Further breakdown to hereditary base 2: only 2s and 1s visible
• Replace 4 with 2^2: final form 2^(2^2) + 2 + 1

Goodstein Sequence Process

• Two-step process repeated iteratively:
  • Step 1: Replace all instances of current base with next integer (2→3, 3→4, etc.)
  • Step 2: Subtract 1
• Starting with 19 in hereditary base 2:
  • First iteration: 3^(3^3) + 3 + 1 - 1 = number > 7 trillion
  • Second iteration: 4^(4^4) + 4 - 1 = number > 10^150 (context: observable universe ~10^80 atoms)

Small Number Examples

• Starting with 3: sequence 3→3→3→2→1→0 (length 6)
• Starting with 2: sequence 2→2→1→0 (length 4)
• Pattern shows eventual termination despite initial growth

Goodstein Meta Sequence Growth Rates

• Meta sequence = length of successive Goodstein sequences until reaching zero
• Starting number 2: sequence length = 4
• Starting number 3: sequence length = 6
• Starting number 4: sequence length > 10^(10^8) = 10^(100 million)
• Starting number 5: sequence length > 10^(10^(10^(10^4)))
• Starting number 6: requires Knuth arrow notation (2↑↑↑↑9)
• Starting number 12: sequence length > Graham's number

Mathematical Foundations and Unprovability

• Peano axioms: industry standard axiomatization of arithmetic (late 19th century)
• Gödel's Incompleteness Theorem (1931): no complete axiomatization of arithmetic possible
• Always exist true facts about numbers unprovable from standard laws

Concrete Incompleteness

• Most unprovable theorems are artificial logical paradoxes
• Goodstein's theorem = example of "concrete incompleteness"
• Understandable without advanced logic knowledge
• Kirby and Paris (1982): proved Goodstein's theorem unprovable from Peano axioms

Proof Requirements and Speed Limits

• Goodstein used "fancy infinite machinery" beyond finite arithmetic
• Purely finitary proof impossible - infinite tools necessary
• Connection between unprovability and fast growth:
  • Peano axioms have speed limit on handleable sequence growth
  • Goodstein sequences exceed this limit
  • Grow "too big too quickly" for standard arithmetic laws

Tortoise and Hare Analogy

• Base change operation: sends numbers "flying up insanely fast"
• Minus one operation: appears negligible but accumulates
• Eventually accumulated minus ones overhaul base change growth
• Demonstrated with starting number 4: 3^3 - 1 = 26, breaks down into smaller blocks
• Process continues until sequence reaches zero