A Proof of Goodstein’s Theorem without Transfinite numbers

Page last updated 30 Oct 2024

 

A 1944 paper by Reuben Goodstein (Footnote: Reuben Louis Goodstein, PDF On the restricted ordinal theorem, The Journal of Symbolic Logic 9, 1944, no. 2, pp. 33-41. ) includes a definition of a sequence of numbers which are now referred to as Goodstein sequences, and the paper introduces a proposition, now known as Goodstein’s theorem, which asserts that every Goodstein sequence terminates by reaching a value of zero. Goodstein claimed to prove this using the notion of sequences of transfinite ordinals, and several similar papers have been published since. (Footnote: ▪ Reuben Louis Goodstein, Transfinite ordinals in recursive number theory, The Journal of Symbolic Logic 12.4, 1947, pp 123‑129.
▪ A. Cichon, PDF A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Amer. Math. Soc. 87, 1983, pp 704‑706.
▪ Andrés Eduardo Caicedo, PDF Goodstein’s function, Revista Colombiana de Matemáticas 41, 2007, no. 2, pp. 381‑391.
▪ Sarah Winkler, Harald Zankl, and Aart Middeldorp, PDF Beyond Peano arithmetic - Automatically proving termination of the Goodstein sequence, 24th International Conference on Rewriting Techniques and Applications, RTA 2013, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013.
▪ Michael Rathjen, PDF Goodstein’s theorem revisited, Gentzen’s Centenary, Springer, 2015, pp. 229‑242.
▪ A. Leonardis, G. d’Atri, F. Caldarola, PDF A geometrical proof for generalized Goodstein’s theorem, Numerical Computations: Theory and Algorithmsm NUMTA 2019, 67.
▪ Henry Towsner, PDF Goodstein’s Theorem, ε₀, and unprovability, unpublished notes, 2020.
▪ A. Leonardis, G. D’atri, E. Zanardo, PDF Goodstein’s Generalized Theorem: From Rooted Tree Representations To The Hydra Game, J. Applied Math. & Informatics Vol 40.5-6, 2022, pp 883‑896. )

 

In a paper of 1982, Laurie Kirby and Jeff Paris state that there is a proposition that is an expression of Peano arithmetic that asserts that a Goodstein sequence must terminate, but that this proposition cannot be proved within Peano arithmetic. (Footnote: Laurie Kirby and Jeff Paris, PDF Accessible independence results for Peano arithmetic, Bulletin of the London Mathematical Society, 1982, pp. 285-293. ) Some people believe that the proposition cannot be proved at all except by the use of transfinite numbers. (Footnote: For example, in Chapter 10 of An Outline of Set Theory by James M Henle, Courier Corporation, 2007:
“…37 years after Goodstein’s proof appeared, L. Kirby and J. Paris proved that the use of infinite sets is actually necessary. That is, this is a theorem of arithmetic that can't be proved arithmetically, but only by using the extra powers of set theory!”)

 

However, since a Goodstein sequence is a reversible well-defined algorithmic process without any choice or any randomness, (Footnote: Reversibility: given the information regarding any single term of a Goodstein sequence, all of the other terms of the sequence both prior and subsequent to that term are completely determined. Note that this is different to cases such as the Collatz conjecture where the same term can occur in multiple different Collatz sequences.) it might be expected that a resolution of the nature of its iterative development should be susceptible to a mechanistic analysis of that algorithmic process, and this turns out to be the case. The method of the proof presented here can be viewed in a manner similar to an engineering perspective, by a consideration that the iterations of the Goodstein sequence can be imagined as operations on a modifiable rotary counter mechanism, which can be conceived as a rotary counter similar to those that were used in cars before digital screens took over that function, but where additional wheels can be added and where the wheels can be made bigger to include extra numerical digits.

This gives an insight into the nature of these algorithmic processes and leads directly to an elementary proof of Goodstein’s theorem without any reference to transfinite induction or transfinite numbers.

 

Details of the Goodstein sequence

 

Hereditary Base Notation

Our standard notation for numbers that is almost universally used is positional notation in base 10, where the position of a digit symbol indicates its value within the overall number, where, for example, we write 76020 instead of writing 7×10⁴ + 6×10³ + 0×10² + 2×10¹ + 0×10⁰ so that the relative position of each digit symbol (here 7, 6, 2 and 0) indicate a numerical value within the overall number. The historical reason for the adoption of such positional notation is that it is much more convenient for relatively large numbers. (Footnote: See also Number Systems for more on number systems and bases.)

 

The rules governing the iterations of the Goodstein sequence require that every natural number is referred to in terms of what is called “hereditary base b notation”. To express a number in hereditary base b notation, the number is expressed as the sum of exponents of the base number b and individual unique digit symbols for any remaining value less than b, and where the exponents themselves also have to follow this rule, as do exponents of exponents, and so on. As a simple example the number 909 in standard decimal notation is:

3·4⁴ + 2·4³ + 3·4¹ + 1

in hereditary base 4 notation. That number does not have any exponents greater than 4, so in that example the exponents of exponents rule is not invoked. An example of such a number is the number 549,755,814,797 in standard decimal notation, which is:

2·4^{42+ 3} + 3·4⁴ + 2·4³ + 3·4¹ + 1

in hereditary base 4 notation rather than 2·4¹⁹ + 3·4⁴ + 2·4³ + 3·4¹ + 1.

 

The only symbols allowed in such representation are the symbols for the base number b, individual unique symbols for each number greater than zero and less than b, the plus symbol, the multiplication symbol, and exponentiation. (Footnote: Exponentiation may be represented either by a symbol such as “^”, or by a superscript position of the exponent, placing the numerical value of the exponent immediately after and higher than the number to which it applies, for example 3 with exponent 5 is represented as 3⁵. No other positional notation is allowed.)

 

Defining a Goodstein sequence

A Goodstein sequence is formed by the repeated application of two steps:

1. A new number is given by increasing the numerical value of the base by 1. This means that the numerical value of every occurrence of the symbol b is increased by 1.
2. Then subtract 1 from the number that results from Step 1.

This gives the next number in the sequence.

 

For the application of these two steps, the number must always be in the correct hereditary base notation. This may mean it has to be reformulated between steps so that there is no negation symbol present. For example:

 

The fascinating thing about Goodstein sequences is how quickly the numbers become mind-bogglingly enormous. For a simple example, let’s take a number that we would consider small, such as the number 15 in standard base 10 notation, which is 2²⁺¹ + 2² + 2 + 1 in hereditary base 2 notation, and for the first few numbers of the sequence we have:

and after another four iterations, we have:

13¹³⁺¹ + 7·13⁷ + 7·13⁶ + 7·13⁵ + 7·13⁴ + 7·13³ + 7·13² + 7·13 + 6

which, in standard base 10 positional notation, is:

3,937,376,861,542,204

These numbers keep growing and growing, and yet eventually, if the theorem is correct, they must at some point start becoming smaller and terminate at zero. That is what we shall prove here, for any possible starting number and base.

 

Positional Notation with Positions for Zero

Note that in the above examples, in standard positional numerical notation there can be some positions where there is a zero symbol, whereas in the hereditary base notation, with a number such as 3³⁺¹ + 2·3³ + 3 there are “empty” positions which are not represented by any symbol. If we explicitly add such 1 and 0 symbols to:

3³⁺¹ + 2·3³ + 3

we obtain:

1·3³⁺¹ + 2·3³ + 0·3² + 1·3¹ + 0·3⁰.

which, while it is not true hereditary base notation, leads to the idea that we can use the concept of positional notation to track the changes across the iterations of a sequence, where each position has a related numeral - from here on, we will refer to such symbols as “multipliers”, and we will always show the 1 and 0 multipliers, with the proviso that the leftmost multiplier shown is always non-zero, and we will use a special form of positional notation as in the example below:

where for each b − n, while not itself in hereditary notation, there is a corresponding expression in hereditary notation that has that specific numerical value. So, for the previous example of 3^2·3 + 2·3³⁺² + 3³⁺¹ + 2·3³ + 2·3², that initial number is represented by:

and after Step 1 of an iteration we have:

 

and after Step 2 of the iteration with subtraction by 1 the result is:

which corresponds precisely to the result previously obtained for the example above. Note that Step 1 of the iteration results in two additional positions with zero multipliers (4³ and 4⁴⁺³ ); this is a key aspect to understanding the operation of the proof.

 

The reason for using this special type of positional notation lies in the fact that by this notation every position is always referenced and every multiplier is always referenced regardless of whether its value is zero or 1 or otherwise. It can be noted that this special positional notation is isomorphic to standard hereditary base notation in that given any expression in this special positional notation, the standard hereditary base notation can be obtained directly from that expression and vice-versa. This will be seen to be a key element in proving the termination of any Goodstein sequence, since we know that by using this positional notation every multiplier must always be less than the base b, and hence we know that at Step 1 of any iteration no multiplier can change value.

Referring again to a conceptual correspondence between a Goodstein sequence and a modifiable rotary counter, one can visualize that Step 1 of an iteration corresponds to enlarging each wheel and adding an extra numeral while retaining the currently displayed numeral. It will also be shown below that at Step 1 additional wheels may be added at particular locations between the existing wheels and all such additional wheels will have their initial display as the numeral zero. Then Step 2 corresponds to reversing the drive to the counter, starting at the rightmost wheel. If the rightmost wheel is not reading zero, the wheel turns backward to display the next smaller digit numeral. On the other hand, if the rightmost wheel reads zero, the wheel turns backward to display the largest digit numeral (the current base less 1), and the next wheel to the left, provided it is not reading zero, turns backward to display a numeral that is one less than previously - this corresponds to the numeral of the rightmost position changing its value to the value of the current base minus 1, while the multiplier to its immediate left decreases by one if its value after Step 1 is not zero. If that next wheel to the left is also reading zero a similar scenario ensues, and similarly for other wheels reading zero.

 

Of course, in reality such a mechanical device and its wheels would rapidly become unfeasibly enormous, but it is a principle that provides a conceptual basis for a proof. This enables a proof that can be presented in a straightforward manner that provides a nice insight as to why the sequence must terminate and at the same time is logically rigorous.

 

Unitary Decrementation

Before we proceed further, we clarify one aspect regarding Step 2 of an iteration - the subtraction of 1 from the multiplier of the rightmost position b⁰, where b is the current base. If that multiplier is not zero, then that multiplier simply decreases by one. On the other hand, if the multiplier is zero, then at the next position bⁿ to the left of b⁰ for which the multiplier is not zero, the multiplier of that bⁿ is decreased by one, while the multipliers at all positions b^n − 1, b^n − 2, … , b¹, b⁰ take the value of b − 1, where b is the current base. This of course corresponds to the standard method of subtraction in our conventional decimal number system.

 

In order to avoid undue verbosity, we shall from this point forward simply refer to this operation as “Unitary Decrementation”.

 

Incrementation of a multiplier

We can at this point note some fundamental principles:

1. No multiplier can increase at Step 1 of an iteration.
2. A multiplier m can increase at some Step 2 of an iteration if and only if;
   1. m is zero, and all multipliers to the right of it are all zero after Step 1 of an iteration. Note that this means that there must be a non-zero multiplier to the left of the position of m.
   2. the first non-zero multiplier n that is to the left of the multiplier m must decrease by 1
   3. m increases to the value of the current base minus 1.
3. From the above principles, it follows that the leftmost multiplier can never increase.

 

At this point we shall first examine some specific cases, as doing so helps to create a clear picture of what happens over the iterations of a sequence.

 

Case 1: Exponents less than b

First we consider a number where, in our positional notation, all the exponents of the positions are less than the base number. At every iteration, for each position the numerical value of the base b increases by one, but the numerical values of the exponents do not change because they are all less than b. Such a number is initially given as:

As noted previously the above is not in strict hereditary base notation since we have minus signs, but we can nevertheless apply the Goodstein rules as if it were in that notation. This means that the numerical value of a term such as b − n is not changed at an iteration, but since the value of the b changes at Step 1 of an iteration, the numerical value of that same position after that Step 1 is given as b − n − 1, where b is the new current base. This gives us, after Step 1:

It can be seen that each exponent, although its actual value is unchanged, is expressed in the above notation by a different term. In the same way, the multiplier values have not changed, and the quantity of positions has not changed.

 

Step 2 of the iteration is the subtraction of 1 from the number given by Step 1 of the iteration. If the rightmost multiplier a₀ is not zero, then it decreases by 1, and the other multipliers are unchanged:

As long as the rightmost multiplier of b₀ is not zero, each iteration decreases its value by one, while the numerical values of the other multipliers remain the same. It follows that there will be some iteration where the rightmost multiplier of b₀ decreases to zero. Step 2 of the subsequent iteration requires that the value of the number decreases by 1, and we apply Unitary Decrementation. For example if a₁ was not zero before Step 2 we have:

 

This is the same general case as the original starting case except that the multiplier of b₁ has decreased by one. Since the multiplier at any position cannot increase at any iteration unless it is zero when Step 2 of the iteration is applied, and since every time that the multiplier of b₀ is zero before Step 2 of an iteration, the multiplier of b₁ decreases by one if it is not zero, then an iteration must be reached after finitely many iterations where both a₁ and a₀ will be zero. Then at Step 2, both a₁ and a₀ take the numerical value of b − 1 and if a₂ was not zero, it decreases in value by 1. Again, after a finite number of iterations a₀ must again decrease to zero and similarly also a₂ and a₁.

 

This principle applies similarly for each of the multipliers, so that at some iteration the numerical value of the leftmost multiplier must decrease by 1, giving the same general case as the original starting case except that the numerical value of the leftmost multiplier has decreased by 1 - and since the leftmost multiplier can never increase, at some later iteration it must decrease to zero, when all the multipliers to its right take the value of the current base less 1.

 

Similarly, at some later iteration, the new leftmost non-zero multiplier must become zero at some iteration, and since this must apply to all multipliers and no new positions are generated, at some iteration all multipliers must become zero, and the sequence must terminate.

 

Case 2: Exponents b or less

Now we look at a number where the leftmost position has the position value of b^b. The initial situation is:

This time, unlike the previous case, every iteration creates a new position, which is b^b − 1, and the multiplier a_b − 1 for this is zero, so that after Step 1 of an iteration we will have:

The reason for this is that at the initial leftmost position (a_b and b^b), both the base b and its exponent b of the positional values have increased by one, but at all the other positions, the numerical value of base b increases but the numerical value of its exponent does not. And since our positional notation requires that all positions are shown, every position has an exponent which 1 greater than the next position to its right, this means that the second position from the left (the position that was immediately to the right of the leftmost position, a_b − 1 and b^b − 1) becomes the third position from the left, and its exponent is b^b − 2. Its multiplier remains the same value but is now represented here as a_b − 2. This may be envisaged by:

In this way, every iteration produces an extra new position with a zero multiplier. The additional positions with zero multipliers remain zero unless all of the positions to the right of these additional positions become zero. As in the previous case (Case 1) an iteration must be reached when all the multipliers to the right of the b^b position (for the current base b) become zero.

 

For that case, Step 1 of the next iteration increases the value of the base b by 1, and a new position is created immediately to the right of b^b with a zero multiplier, that is, every multiplier other than that of b^b is now zero.

 

At Step 2 of that iteration, the multiplier of the b^b position decreases by 1, and all the other multipliers to the right of it take the value b − 1.

 

We now have the same general case as the original starting case (all exponents b or less), except that the leftmost position is still b^b but with a multiplier that is 1 less in numerical value than before. Note that while there are more positions, in the above the quantity of positions was immaterial and so the general analysis above still holds for further iterations.

 

It follows that there must be some iteration after finitely many iterations where the multiplier of the b^b position reaches zero. When this happens, the remaining part of the number is the same as the general case already covered above in Case 1 and so, at some later iteration, all multipliers of all these positions must reach zero and hence the sequence terminates. Note that in the above, the actual numerical value of b^b cannot affect this process and the outcome.

 

“b-exponents” positions

It can also be noted at this point that for any position, by the definition of the Goodstein sequence, the expression for that position in terms of b remains exactly the same for all iterations. We will refer to any position where the exponent of b is a multiple of b as a “b‑exponents” position, where 0 and 1 are included as such multiples, for example: b⁰, b^b, b¹, b^2·b, b^b·b, b^b2 etc. (Footnote: Note that an expression such as b^b + b is equivalent to b^2·b with regard to the operation of the Goodstein sequence; for example after Step 1 of an iteration on 5^5 + 5 ≡ 5^2·5 we have 6^6 + 6 ≡ 6^2·6.)

 

By the definition of the Goodstein sequence, it follows that a b‑exponents position can never be added at any iteration, and it will be seen later that this is a key point in proving the termination of Goodstein sequences in general.

 

Case 3: Exponents b to 2b - 1

It can be readily seen that, for the part of a number that has these positions, no new positions are created at an iteration. From the tables below, we can see that for the initial positions for the positions b^b or higher:

after the change of base by Step 1 of an iteration we will have:

As in the above tables, both before and after the iteration, each exponent is exactly 1 greater than at the position to its right.

 

Note that 2b − 1 becomes 2b − 2 since in hereditary base notation, there is only one instance of b present in the 2b − 1 before the iteration (which in true hereditary notation is b + m, where m < b), hence the actual numerical value of the exponent is only increased by 1 - and since the new value of b is greater than the previous value by 1 the new expression for the exponent is 2b − 2 in our positional notation. The same applies to the names of the multipliers.

 

It follows that for this part of a number, an iteration does not create any new positions. As for the previous case, after finitely many iterations, b^b and all multipliers to its right will reach zero, and unitary decrementation applies.

 

We now have the same general case for this part of the number as the original starting case, except that the multiplier of b^b is now the numerical value of b - 1 and the numerical value of the multiplier of b^b + 1 has decreased by 1. Similarly, after finitely many iterations, the same general case for this part of the number as the original starting case is reached except that the multipliers of b^b and b^b + 1 are both zero. Similarly, after finitely many iterations, all multipliers of all the positions to the right of the leftmost position will reach zero and when that occurs the multiplier of the leftmost position decreases by 1. And after finitely many iterations, it decreases to zero, and we have the same general case for this part of the number as the original starting case, except that the original leftmost position has disappeared. Similarly, the multiplier of the new leftmost position will also reach zero after finitely many iterations, and so on, until all the multipliers of this part of the number disappear, leaving the number as in Case 2.

 

Case 4: Exponents b to 2b

This is similar to Case 2, with this part of a number as:

and after the change of base by Step 1 of an iteration we have:

and again, at each iteration, one position is added immediately to the right of the position b^2b and its multiplier is zero, while the expression for the hereditary base notation for that position remains unchanged except that the numerical value of the base is incremented.

 

And, as noted in Case 3, the part of the number covered by Case 3 must at Step 1 of some iteration have all its multipliers as zero, it follows that at Step 2 of the next iteration, the multiplier of that position b^2b must decrement by 1, and there must be a subsequent iteration where that multiplier decreases to zero.

 

The General case

By now, the reader will probably see how the above leads to the conclusion that every Goodstein sequence must terminate. To be more precise, we can now generalize the above; Case 2 and Case 4 are instances of segments between two consecutive “b‑exponents” positions P₁ and P₂ inclusive. (Footnote: A “b‑exponents” position was previously defined in Case 2: b‑exponents as a position where the exponent of b is a multiple of b, where 0 and 1 are included as such multiples. Such positions cannot be added at any iteration.)

 

Note that at Step 1 of an iteration multiple positions can be added to the immediate right of a b‑exponents position P. For example, the consecutive positions 3⁹, 3⁸, 3⁷ in hereditary base 3 notation are 3^3·3, 3^2·3 + 2, 3^2·3 + 1 so that by Step 1 they transform to 4^4·4, 4^2·4 + 2, 4^2·4 + 1 (or in decimal notation 4¹⁶, 4¹⁰, 4⁹ ) . And, as for Case 2 and Case 4, all the additional positions that are created at Step 1 of an iteration, here being 4^3·4 + 3, 4^3·4 + 2, 4^3·4 + 1, 4^3·4, 4^2·4 + 3  (or in decimal notation 4¹⁵, 4¹⁴, 4¹³, 4¹², 4¹¹  ) always have zero multipliers. As such, then there can only be a finite number of iterations before the multipliers to the right of these positions all become zero, and at the next iteration, the multiplier of the position immediately to the left of these zero multipliers must decrease by 1.

 

Hence Case 2 and Case 4 are specific instances of the general case, which is that the addition of any finite quantity of new positions with zero multipliers at any iteration to the immediate right of any position P with a non-zero multiplier cannot prevent the eventual decrement to zero of all multipliers to the right of that position P at some iteration, and so the multiplier of that position P must decrease by 1 after finitely many iterations. And after finitely many iterations, it must decrease to zero, and this can occur repeatedly. Now, while in general multipliers can also increase (at Step 2), this does not apply to the leftmost position - it cannot increase at any iteration, hence the leftmost position must always decrease to zero after finitely many iterations, leaving a new leftmost position that has a hereditary base notation that, in terms of b, is one less than the previous leftmost position.

 

In general, there are two situations, where the leftmost position P₁ is a b‑exponents position or else it is not a b‑exponents position. If P₁ is a b‑exponents position then it must decrement to zero after finitely many iterations, resulting in the situation that the new leftmost position is not a b‑exponents position and where there is a b‑exponents position P₂ to its right. Then no new positions can be added to the left of this leftmost b‑exponents position P₂ , and so all the non-b‑exponents positions to the left of P₂ must decrease to zero after finitely many iterations, leaving the new leftmost position as this b‑exponents position P₂. Then at some iteration, the multiplier of this P₂ must decrease to zero, and so on until the only remaining b‑exponents position is b⁰. Then this is Case 1 and the sequence must terminate.

 

Extended Goodstein sequences

The above only considered cases where the base b was only increased by 1 at each iteration. But since an increase by any finite natural number can only result in the creation of additional positions with zero multipliers, such additional positions do not prevent the eventual decrease of any multiplier to zero.

 

Conclusion

The straightforward non-choice reversible algorithmic nature of the definition of the Goodstein sequence allows for a purely mechanistic proof of termination by the principles of propositional logic applied to the numerical properties of a sequence of numbers. It is of course the case that, for any system that can actually evaluate algorithms and which has a finite maximal number of variables, there can always be some initial number where such a system cannot hold all the values needed to calculate the value of every multiplier at every position for every iteration. However, such information is not required to prove that the general case that such a sequence must terminate. In the above, only a finite number of assertions of existence were required, and the proof does not require the calculation of any specific values, only the assertion that for some variables there exists a natural number that satisfies certain conditions pertaining to that variable, and these assertions follow from fundamental numerical properties.

 

As noted in the introduction, it is claimed that there is a proposition that is an expression of Peano arithmetic that asserts that a Goodstein sequence must terminate, and that this proposition cannot be proved within Peano arithmetic. This has given rise in some quarters to a belief that there are some statements about natural numbers that are true but can only be proven by the use of transfinite number theory, and that the proposition that every Goodstein sequence terminates is one such statement (Footnote: For example, in Chapter 10 of An Outline of Set Theory by James M Henle, Courier Corporation, 2007:
“…37 years after Goodstein’s proof appeared, L. Kirby and J. Paris proved that the use of infinite sets is actually necessary. That is, this is a theorem of arithmetic that can't be proved arithmetically, but only by using the extra powers of set theory!”) - but the above demonstrates that this is not the case.

 

In summary, we can note that not only is it the case that, as Solomon Feferman remarked:

“The necessary use of higher set theory in mathematics of the finite has yet to be established. Furthermore, a case can be made that higher set theory is dispensable in scientifically applicable mathematics … Put in other terms: the actual infinite is not required for the mathematics of the physical world.” (Footnote: As in ‘Infinity in Mathematics: Is Cantor Necessary?’, in Philosophical Topics 17.2 (1989): 23-45.)

and neither is it required to prove that all Goodstein sequences terminate.

Footnotes: