🗂️ Maths, Logic & Crypto · View mindmap

Recursive Subtraction

Recursive subtraction refers to processes where a value is reduced through iterative or recursive operations, often involving changes in representation. While elementary arithmetic subtraction is straightforward, complex number-theoretic sequences may exhibit explosive initial growth before eventually terminating at zero due to underlying structural constraints.

Key Mechanisms & Examples

• Goodstein Sequences: A primary example where recursive transformation rules appear to cause divergence but are guaranteed to terminate.
  • Defined by hereditary-base-notation: rewriting a natural number $n$ in base $b$, replacing all exponents recursively until the expression contains only the base and addition.
  • Process involves incrementing the base ($b\to b+1$) and subtracting 1, repeated iteratively.
  • Despite initial exponential/hyperexponential growth, the sequence must reach 0 for any starting natural number.
  • Proof relies on Transfinite Ordinals mapping each step to a strictly decreasing sequence of ordinals less than ${ϵ}_0$.

Related Concepts

• hereditary-base-notation: The representation system crucial for defining Goodstein sequences.
• Ordinal Numbers: Used to prove the termination of sequences that cannot be proven finite within Peano Arithmetic.
• Gödel’s Incompleteness Theorems: Goodstein’s Theorem is an example of a statement true in standard arithmetic but unprovable within PA, illustrating limitations of formal systems.

References

• Goodstein’s Theorem: Resolving the Paradox of Explosive Growth to Zero (Up and Atom, 2026)
• Goodstein’s Theorem: Resolving the Paradox of Explosive Growth to Zero