Thursday, April 28, 2016

[cqejnfvs] A note about the Goodstein Theorem

The mapping from a number in hereditary base notation to an ordinal number with omegas always results in an expression for an ordinal number with terms joined by plus signs only (addition), never minus signs (subtraction), because hereditary base notation by construction only has pluses.  A sequence of such plus-sign-only expressions that is strictly decreasing will converge to zero in a finite number of steps (this was the meat of the proof of the theorem).

If minus signs were permitted, then the following sequence

omega, omega-1, omega-2, omega-3...

is strictly decreasing but would not reach zero in a finite number of steps.  Arguably "omega-1" is not even defined for ordinal numbers, though such an expression could have been formed by substitution starting from something other than hereditary representation:

Given a positive integer N, prove that the sequence

N, N-1, N-2, N-3...

will reach zero in a finite number of steps.