🗂️ Maths, Logic & Crypto · View mindmap

Bumping the Base

Bumping the base refers to a specific transformation rule in number theory where a natural number, expressed in hereditary base-$b$ notation, has its base incremented to $b+1$ while maintaining the same structural representation. This operation is the core mechanic of Goodstein sequences.

Core Mechanics

• Hereditary Base Notation: A number is written in base $b$ such that all exponents are also recursively expanded in base $b$.
  • Example: $267=2^{2^{2+1}}+2^{2+1}+3$ becomes $2^{2^2+2}+2^2+1_0$ in hereditary binary.
• The Bump Operation: Replace every instance of the base $b$ with $b+1$.
  • Result: The numerical value typically increases drastically (“explosive growth”).

Relationship to Goodstein’s Theorem

• Goodstein sequences are generated by alternating the “bump the base” operation with a subtraction of 1.
• Paradox: Despite initial exponential explosion, every Goodstein sequence eventually terminates at zero.
• Proof Strength: This termination cannot be proven within Peano arithmetic but is provable in Second-order arithmetic using Ordinal numbers.

Key Insights

• Counter-intuitive Behavior: The “bumping” step suggests divergence, but the structural reduction of ordinal equivalents ensures convergence to zero.
• Independence Result: Demonstrates limitations of first-order logic systems in capturing total computability of certain recursive processes.

Sources

• Goodstein’s Theorem: Resolving the Paradox of Explosive Growth to Zero
• See also: Goodstein’s Theorem: Resolving the Paradox of Explosive Growth to Zero